4. Implement a randomized version of quicksort that uses the in-place par tionin

Question

4. Implement a randomized version of quicksort that uses the in-place par tioning algorithm described in Sect. 3.6. 5. The goal of this step is to create a class of Integer objects that count how many times they are compared or copied. This will allow you (in the next step to measure the performance of sorting algorithms by observing how many times they compare or copy elements. When elements are large, these are the most expensive operations performed by the algorithms. The Integer objects will allow you to count these operations without having to modify the sorting algorithms. You can do this step in one of two ways, as described below. The original way is the one that was in the first version of this project description. De- pending on the standard library implementation that your compiler uses, it may give you compilation problems. The preferred way avoids those problems. As a bonus, it also gives you more accurate results. (Because it allows you to count operations performed on all Integer objects, in cluding temporary objects created by the sorting algorithms. The original way only allows you to retrieve the number of operations performed on Integer objects you create yourself.) Do this step the preferred way unless you had already done it the original way and didn't have compilation problems.

Explanation / Answer

4) Answer for question no. 4

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

// swap function for assisting in partitioning
template <class T>
void swap(T *a, T *b) {
T temp;
temp = *a;
*a = *b;
*b = temp;
}

//randomized partition
template <typename T>
int partion(T arr[], int p, int r) {
int pivotIndex = p + rand()%(r - p + 1); // this is the point where the pivot is randomized
int i = p - 1;
int j;
T pivot = arr[pivotIndex];
swap(&arr[pivotIndex], &arr[r]);
for (j=p;j<r;j++) {
if (arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i+1], &arr[r]);
return i + 1;
}

//quick sort function
template <typename T>
void quickSort(T arr[], int p, int q) {
int j;
if (p<q) {
j = partion(arr, p, q);
quickSort(arr, p, j-1);
quickSort(arr, j+1, q);
}
}

int main() {
   srand(unsigned(time(NULL)));
   int n;
   cin>>n;
   int arr[n];
   for(int i=0;i<n;++i) {
       cin>>arr[i];
   }
  
   quickSort(arr,0,n-1);
   for(int i=0;i<n;++i) {
       cout<<arr[i]<<" ";
   }
   cout<<endl;
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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