2.2 Quick sort Please implement the quick sort within the following class. The i
ID: 3588407 • Letter: 2
Question
2.2 Quick sort Please implement the quick sort within the following class. The input parameter, nums, is a vector of unsorted integers; after calling the quickSort method, the numbers in nums are sorted. You cannot use any other libraries except for the standard libraries for C++. class Solution { protect *Your own methods to be called by the public method; you can define the interface of these methods.*/ int yourOwnMethod(int n) public: /*Your quick sort implementation/ void quickSort (vectorint>&nums; , int low, int high) {Explanation / Answer
CODE:
quickSort.cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution{
protect:
// this method sorts in ascending order..
// it starts by placing all smaller elements to left of pivot
// and greater elements to right of pivot.
int partition (vector<int>&arr, int low, int high)
{
int i = (low - 1); // Smaller element index
int pivot = arr[high]; // pivot
for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot)
{
i++;
// swap the elements
int t = arr[i];
arr[i] = arr[j];
arr[j] = arr[i];
}
}
// swap the elements
int t = arr[i+1];
arr[i+1] = arr[high];
arr[high] = arr[t];
return (i + 1);
}
public:
/* Parameters -
num - Vector of integers to be sorted,
low - Starting index
high - Ending index
*/
void quickSort(vector<int>&num, int low, int high)
{
if (low < high)
{
/* pi is partitioning index, num[p] is now
at right place */
int pi = partition(num, low, high);
// Separately sort elements before
// partition and after partition
quickSort(num, low, pi - 1);
quickSort(num, pi + 1, high);
}
}
};
int main(){
Solution s;
vector <int> num;
num.push_back(20);
num.push_back(10);
num.push_back(5);
num.push_back(30);
num.push_back(60);
int len = num.size();
s.quickSort(num,0,len-1);
cout << "Sorted vector is " << endl;
for(int i=0;i<len;i++){
cout << num[i] << endl;
}
}
OUTPUT:
$g++ quickSort.cpp
$./a.out
Sorted vector is
5
10
20
30
60
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.