I want to write a C++ code that compares the number of comparisons done by these

Question

I want to write a C++ code that compares the number of comparisons done by these four different sorting algorithms:

1) The standard C++ STL sort function (not the C qsort function!). Of course, this sort is already pre-made, so you don’t need to implement it. But you do need to find a way to count the number of comparisons it does.

2) Selection sort, implemented as a priority queue based on an unordered vector.

3) Insertion sort, implemented as a priority queue based on a sorted vector.

4) Heapsort, implemented as a priority queue based on a heap.

this is what each sort has to do :

Write code that counts the number of comparisons done by the 4 different sorts for n = 5000, 10000, 15000, ..., 100000. When this is done, we should have exactly 4*20 = 80 different numbers, one for each sort and value of n.

The challenge is that I can't use a traditional implementation (which is not based on a priority queue). I need to use a priority queue implementation.

This has to be done only using simple C++ functions. like I can only use new and delete to allocate and de-allocate memory. NOT malloc and free, NOT  C++ smart pointer, NOT any pre-defined data structures (such as arrays or vectors) or algorithms.

A bing Thank you in advance to all you experts!

Explanation / Answer

Selection sort:

Insertion Sort:

Heap Sort:

#include < iostream.h >
#include < conio.h >
int heapSize = 10;
void print(int a[]) {
for (int i = 0; i <= 9; i++) {
cout << a[i] << "-";
}
cout << endl;
}

int parent(int i) {
if(i==1)
return 0;

if(i%2==0)
return ( (i / 2)-1);
else
return ( (i / 2));
}

int left(int i) {
return (2 * i) + 1;
}

int right(int i) {
return (2 * i) + 2;
}

void heapify(int a[], int i) {
int l = left(i), great;
int r = right(i);
if ( (a[l] > a[i]) && (l < heapSize)) {
great = l;
}
else {
great = i;
}
if ( (a[r] > a[great]) && (r < heapSize)) {
great = r;
}
if (great != i) {
int temp = a[i];
a[i] = a[great];
a[great] = temp;
heapify(a, great);
}
}

void BuildMaxHeap(int a[]) {
for (int i = (heapSize - 1) / 2; i >= 0; i--) {
heapify(a, i);
print(a);
}
}

void HeapSort(int a[]) {
BuildMaxHeap(a);
for (int i = heapSize; i > 0; i--) {
int temp = a[0];
a[0] = a[heapSize - 1];
a[heapSize - 1] = temp;
heapSize = heapSize - 1;
heapify(a, 0);
}

}

void main() {

int arr[] = {
2, 9, 3, 6, 1, 4, 5, 7, 0, 8};
HeapSort(arr);
print(arr);
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.