Please implement the quick sort within the following class. The input parameter,
ID: 3587057 • Letter: P
Question
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 (vector& nums, int low, int high)Explanation / Answer
Hi,
Quick sort is one of the most common sorting methods used, the logic behind it as follows,
choose a pivot randomly, like we do it in middle in case of merge sort, and then recursively sort both the halves,
here is the code for the same,
in the code below, i have chosen the pivot as last element
int partition (vector<int>&nums, int low, int high)
{
int p= arr[high]; // choosing pivot
int i = (low - 1);
for (int j = low; j <= high- 1; j++)
{
if (nums[j] <= p)//if current element is less than pivot, swap
{
i++;
int t =nums[i];
nums[i]= nums[j];
nums[j]= t;
}
}
//put the pivot in its correct postion by swapping with high
int t =nums[i+1];
nums[i+1]= nums[high];
nums[high]= t;
return (i + 1);
}
void quickSort(vector<int>&nums , int low, int high)
{
if (low < high)
{
int x = partition(nums, low, high);//getting the pivot from partition function
quickSort(nums, low, x - 1);//sort the first half of pivot
quickSort(nums, x + 1, high);//sort the second half
}
}
The quick sort function is to recursively sort the two halves,
The partition function divies the array like, it places pivot in correct place and place all element less than pivot to left and greater than pivot to right of array,
Thumbs up if this was helpful, otherwise let me know in comments