Question: Language: C++ Program 1 Implement a Priority Queue( PQ) using an UNSORTED LIST . Use an array size of 10 elements. Use a circular array:
Language: C++
Program 1
Implement a Priority Queue(
PQ) using an UNSORTED LIST
.
Use an array size of 10 elements.
Use a circular array: Next index after last index is 0. Add the new node to next available index in the array
. When you add an element, add 1 to index (hit max index, go to index 0). Test if array in full before you add. When you remove an element, from the list, move the following elements to the left to fill in the blank, etc ( Like prior program done with LISTS )
Program 2
Implement a Priority queue using a SORTED list
. Use Quick sort after adding a new node.
Example of quick sort below. Adopt to your program.
#include
void
quickSort(int
a[], int
first, int
last);
int
pivot(int
a[], int
first, int
last);
void
swap(int& a, int& b);
void
swapNoTemp(int& a, int& b);
void
print(int
array[], const
int& N);
using
namespace
std;
int
main()
{
int
test[] = { 7,
-
13, 1, 3, 10, 5, 2, 4 };
int
N = sizeof(test)/sizeof(int);
cout << "Size of test array :"
<< N << endl;
cout << "Before sorting : "
<< endl;
print(tes
t, N);
quickSort(test, 0, N
-
1);
cout << endl << endl << "After sorting : "
<< endl;
print(test, N);
return
0;
}
/**
* Quicksort.
* @param a
-
The array to be sorted.
* @param first
-
The start of the sequence to be sorted.
*
@param last
-
The end of the sequence to be sorted.
*/
void
quickSort( int
a[], int
first, int
last )
{
int
pivotElement;
if(first < last)
{
pivotElement = pivot(a, first, last);
quickSort(a, first, pivotElement
-
1);
quickSort(a, pivotElement+1, last);
}
}
/**
* Find and return the index of pivot element.
* @param a
-
The array.
* @param first
-
The start of the sequence.
* @param last
-
The end of the sequence.
* @return
-
the pivot element
*/
int
pivot(int
a[], int
first, int
last)
{
int
p = first;
int
pivotElement = a[first];
for(int
i = first+1 ; i <= last ; i++)
{
/* If you want to sort the list in the other order, change "<=" to ">" */
if(a[i] <= pivotElement)
{
p++;
swap(a[i], a[p]);
}
}
swap(a[p], a[first]);
return
p;
}
/**
* Swap the parameters.
* @param a
-
The first parameter.
* @param b
-
The second parameter.
*/
void
swap(int& a, int& b)
{
int
temp = a;
a = b;
b = temp;
}
/**
* Swap the parameters without a temp variable.
* Warning! Prone to overflow/underflow.
* @param a
-
The first parameter.
* @param b
-
The second parameter.
*/
void
swapNoTemp(int& a, int& b)
{
a
-
= b;
b += a;// b gets the original value of a
a = (b
-
a);// a gets the original value of b
}
/**
* Print an array.
* @param a
-
The array.
* @param N
-
The size of the array.
*/
void
print(int
a[], const
int& N)
{
for(int
i = 0 ; i < N ; i++)
cout << "array["
<< i << "] = "
<< a[i] << endl;
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help