Language C++ (Please include a short description & Screenshot of output)
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 the code below.
#include <iostream>
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(test, 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++) {
/* If you want to sort the list in the other order, change "" */ 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; }
--------------------------------------------------------------------------------------------------------------------------
Create a class called Node: Have a Name and Priority.
Data set - 10 is the highest priority, 1 is lowest priority.
Enqueue and dequeue in the following order.
Function Name, Priority
Enqueue Joe, 3
Enqueue Fred, 1
Enqueue Tuyet, 9
Enqueue Jose, 6
Dequeue
Enqueue Jing, 2
Enqueue Xi, 5
Enqueue Moe, 3
Dequeue
Enqueue Miko, 7
Enqueue Vlady, 8
Enqueue Frank, 9
Enqueue Anny, 3
Dequeue
Enqueue Xi, 2
Enqueue Wali, 2
Enqueue xChe, 6
Enqueue xVerra, 8
Dequeue
Dequeue
Dequeue
Dequeue
Dequeue
Dequeue
Dequeue
Dequeue
Dequeue
Dequeue
Dequeue
At first, a class called node is created whose data members are name and priority. The object of this class denotes each element of the priority queue. Then a class queue is created which contains the node array of objects. Here the functions like enqueue(), dequeue() and show are defined. After adding each element in the queue, the queue is sorted using quicksort algorithm in ascending order of priority. Finally, the main() contains a menu-driven list of choices and an object of queue class is created to call enqueue(), dequeue() and show() when needed/
Source code:
#include<iostream>
using namespace std;
class node
{
public:
string name;
int priority;
void input(string n,int p)
{
name=n;
priority=p;
}
void display()
{
cout<<"\n"<<name<<"\t"<<priority<<endl;
}
};
void swap(node *a,node *b)
{
node t;
t=*a;
*a=*b;
*b=t;
}
class queue
{
public:
node *a=NULL;
int size,f,r;
queue(int n)
{
size=n;
a=new
node[size];
f=r=-1;
}
void enqueue()
{
string nm;
int p;
cout<<"\nEnter name: ";
cin>>nm;
cout<<"\nEnter priority: ";
cin>>p;
node x;
x.input(nm,p);
if(r==size-1)
cout<<"\nQueue is full"<<endl;
else
if((f==-1)&&(r==-1))
{
f=r=0;
a[r]=x;
}
else
{
r++;
a[r]=x;
}
quicksort(f,r);
}
void quicksort(int l,int r)
{
int loc;
if(l<r)
{
loc=pivot(l,r);
quicksort(l,loc-1);
quicksort(loc+1,r);
}
}
int pivot(int l,int r)
{
int
p=a[r].priority;
node t;
int i=l-1;
for(int
j=l;j<=r-1;j++)
{
if(a[j].priority<p)
{
i++;
swap(&a[i],&a[j]);
}
}
swap(&a[i+1],&a[r]);
return
(i+1);
}
void dequeue()
{
if((f==-1)||(f>r))
cout<<"\nQueue is
empty"<<endl;
else
{
cout<<"Deleted element: ";
a[f++].display();
}
}
void show()
{
if((f==-1)||(f>r))
{
cout<<"\nQueue is
empty"<<endl;
return;
}
for(int
i=f;i<=r;i++)
{
a[i].display();
}
cout<<endl;
}
};
int main()
{
int ch,size;
cout<<"\nEnter size of queue: ";
cin>>size;
queue ob(size);
while(1)
{
cout<<"\nPriority queue
operations";
cout<<"\n1.Enqueue";
cout<<"\n2.Dequeue";
cout<<"\n3.Display";
cout<<"\n4.Exit";
cout<<"\nEnter your choice:
";
cin>>ch;
switch(ch)
{
case 1:
ob.enqueue();
break;
case 2:
ob.dequeue();
break;
case 3:
ob.show();
break;
case 4:
exit(0);
default:
cout<<"\nInvalid choice.\n";
}
}
return 0;
}
output:
Language C++ (Please include a short description & Screenshot of output) Implement a Priority...
C++. Difficulty with quickSort function. Code will not run quickSort function. The code I'm having trouble with is in bold. -------------------------------------------------------------------------------------------------driverProgram.cpp #include #include #include #include #include "quickSort.cpp" using namespace std; int main() { const int MIN_SIZE = 4; //Array size const int SIZE = 25; int theArray[SIZE] = {11, 22, 33, 44, 55, 66, 77, 88, 99, 12, 13, 14, 15, 16, 17, 18, 19, 18, 19, 20, 21, 22, 23, 24, 25}; cout << "List of 25 items: ";...
C++ Time the sequential search and the binary search methods several times each for randomly generated values, then record the results in a table. Do not time individual searches, but groups of them. For example, time 100 searches together or 1,000 searches together. Compare the running times of these two search methods that are obtained during the experiment. Regarding the efficiency of both search methods, what conclusion can be reached from this experiment? Both the table and your conclusions should...
c++ please read all question edit the program to test different random sizes of the array and give me the time in a file will be like random size of the array and next to it the time it took for each size Im trying to do time analysis for Quick sort but i keep getting time = 0 also i want edit the program to test different random sizes of the array and give me the time in a...
I want to compare the runtimes and swap operations times among quick Sort, selection Sort and shell Sort here is my code: But when I create a 1000,000 size array, I can't get the result of the operations times and runtime. what's wrong with my code? and I also want to copy the array. Because I want to use same array for three sort. And for the shell Sort, I haven't learn it in my class. Can anyone help me...
Language: C++ (Please include simple explanation & Screenshot of the output) Implement a Priority Queue with a Binary HEAP. Use a Max Heap. Create a class called Node: Have a Name and Priority. Data set - 10 is the highest priority, 1 is lowest priority. Enqueue and dequeue in the following order. Function Name, Priority Enqueue Joe, 3 Enqueue Fred, 1 Enqueue Tuyet, 9 Enqueue Jose, 6 Dequeue Enqueue Jing, 2 Enqueue Xi, 5 Enqueue Moe, 3 Dequeue Enqueue Miko,...
Modify the sorts (selection sort, insertion sort, bubble sort, quick sort, and merge sort) by adding code to each to tally the total number of comparisons and total execution time of each algorithm. Execute the sort algorithms against the same list, recording information for the total number of comparisons and total execution time for each algorithm. Try several different lists, including at least one that is already in sorted order. ---------------------------------------------------------------------------------------------------------------- /** * Sorting demonstrates sorting and searching on an...
quickSort function. Calling previous functions already implemented. This is a bit different type of quicksort function where my partition function has 3 parameters instead of 4. So I need to write a function quicksort that actually puts all 3 of my functions together and finalizes the sorting process "There should be almost nothing done besides calling the other 3 functions and recursively calling itself (except to check for basecase) class quicksort { private: int left; int right; int* array; ...
I am currently using eclipse to write in java. A snapshot of the output would be greatly appreciated to verify that the program is indeed working. Thanks in advance for both your time and effort. Here is the previous exercise code: /////////////////////////////////////////////////////Main /******************************************* * Week 5 lab - exercise 1 and exercise 2: * * ArrayList class with search algorithms * ********************************************/ import java.util.*; /** * Class to test sequential search, sorted search, and binary search algorithms * implemented in...
How can i make a counter for the number of exchanges made in the linear algorithm?? The binary counter works but the linear doesn't. Here's my code. #include <iostream> using namespace std; void selectionSort(int[], int, int& ); void showSelection(int[], int); void sortArray(int[], int, int&); void showArray(const int[], int); int main() { int values[25] = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24...