Quick Sort

Quick Sort Algorithm 

Problem Statement: Given an array of n integers, sort the array using the Quicksort method.

Quick Sort, like Merge Sort, follows the divide-and-conquer approach. However, unlike Merge Sort, Quick Sort doesn't rely on an additional array for sorting (though it does require some auxiliary stack space). From this standpoint, Quick Sort is somewhat more efficient than Merge Sort.

Example 1:

Input:

N = 6,

Arr[] = {12, 5, 8, 3, 15, 7}

Output:

3 5 7 8 12 15

Explanation:

After applying Quick Sort, the array is sorted in ascending order: {3, 5, 7, 8, 12, 15}.

Example 2:

Input:

N = 7,

Arr[] = {9, 2, 14, 11, 6, 3, 10}

Output:

2 3 6 9 10 11 14

Explanation:

After sorting with Quick Sort, the array becomes: {2, 3, 6, 9, 10, 11, 14}.

Solution

Disclaimer: Don't jump directly to the solution, try it out yourself first. 

Quick Sort follows a divide-and-conquer approach, similar to Merge Sort. However, unlike Merge Sort, Quick Sort does not rely on an additional array for sorting (though it does make use of auxiliary stack space). From this viewpoint, Quick Sort offers a slight advantage over Merge Sort.

The algorithm primarily revolves around two straightforward actions repeated until the array is sorted:

1. Select a pivot and position it in its correct spot within the sorted array.
2. Move elements smaller than the pivot to its left, and larger ones to its right.

Now, let's break down the steps with an example using the array {4, 6, 2, 5, 7, 9, 1, 3}:

Step 1:
The first task is to choose a pivot. A pivot is any selected element in the array. You have various options to choose the pivot:

• The first element of the array
• The last element
• The median of the array
• A random element from the array

Once a pivot is chosen, it needs to be placed in the position where it belongs in the fully sorted array. For instance, in the array {4, 6, 2, 5, 7, 9, 1, 3}, the correct final position of 4 would be the 4th position.

Note: In this explanation, we've picked the first element (4) as the pivot, though you can choose any element according to your preference.

Step 2:
In this step, you shift elements smaller than the pivot to its left, while larger elements are moved to its right. For example, if the pivot is 4, after this step, the array becomes {3, 2, 1, 4, 6, 5, 7, 9}.

As we can observe, after completing these two steps, the pivot (4) is placed in its correct position, though the subarrays to the left and right of it remain unsorted. We now apply these two steps recursively to the left and right subarrays, continuing the process until the remaining subarrays contain only one element (since an array with one element is already sorted).

From this, we can understand that recursion is an essential part of this sorting process.

To summarize, the key objective of Quick Sort is to position the pivot correctly after each recursive call, such that the pivot will be in its final place in the fully sorted array.

Approach:

Let’s break down how to implement the logic based on the steps discussed earlier. As explained, the array will be divided into subarrays, but instead of physically splitting the array or creating new ones, we will define the subarrays by maintaining two pointers or indices (a low pointer and a high pointer) to represent the current range.

The key steps for the quickSort() function are as follows:

1. Initially, the low pointer will reference the first index, and the high pointer will reference the last index (since the range covers the entire array).
2. We will then determine the correct position for the pivot (where it should be placed in the sorted array) by moving smaller elements to the left and larger ones to the right, using a partition() function (which we will explain later).
3. This position is called the partition index because it divides the array into two unsorted parts: one on the left of the pivot and one on the right.
4. Once the pivot is placed at the partition index (as done inside the partition()function), we will recursively call quickSort() on the left and right subarrays. The left subarray will cover the range [low to partition index - 1], and the right subarray will cover the range [partition index + 1 to high].
5. This recursive process continues until the size of the subarray being considered is 1, at which point the recursion will stop.

Pseudo Code

function quickSort(arr, low, high):

if low < high:

// Find the partition index

partition_index = partition(arr, low, high)

// Recursively sort the left subarray

quickSort(arr, low, partition_index - 1)

// Recursively sort the right subarray

quickSort(arr, partition_index + 1, high)

function partition(arr, low, high):

// Pivot selection and rearrangement logic goes here

// Return the final position of the pivot

Let's explore how to implement the partition() function to determine the partition index.

In this function, the first task is to choose the pivot element, which will be arr[low] in our case.

Next, we will introduce two pointers, i and >j. The i pointer will be initialized to low, and the j pointer will be set to high.

The pointer i will advance forward to find the first element greater than the pivot, while the pointer j will move backward to locate the first element smaller than the pivot.

To prevent boundary issues, we need to add conditions like i <= high - 1 and j >= low + 1, ensuring that i doesn't move past the high index and j doesn't go below the low index.

Once we identify arr[i] > pivot and arr[j] < pivot, and if i is still less than j, we swap the values at arr[i] and arr[j].

We continue these steps until j is less than i.

Finally, we swap the pivot element (arr[low]) with arr[j], and return j, which is the partition index.

Pseudo Code

function partition(arr, low, high): 

 // Select the pivot
pivot = arr[low]

// Initialize pointers

i = low,j = high

while i < j:

// Move i forward until an element greater than pivot is found
while i <= high - 1 and arr[i] <= pivot:
i = i + 1

// Move j backward until an element smaller than pivot is found
while j >= low + 1 and arr[j] >= pivot:
j = j - 1

// If i is still less than j, swap elements
if i < j:
swap(arr[i], arr[j])

// Swap the pivot with arr[j]
swap(arr[low], arr[j])

// Return the partition index
return j

Note: In this function, we have arranged the elements equal to the pivot on the left side. If you prefer to place them on the right, the first condition will check if arr[i] < pivot, and the second condition will check if arr[j] >= pivot.

Let's explore how to implement the partition() function to determine the partition index.

In this function, the first task is to choose the pivot element, which will be arr[low] in our case.

Next, we will introduce two pointers, i and >j. The i pointer will be initialized to low, and the j pointer will be set to high.

The pointer i will advance forward to find the first element greater than the pivot, while the pointer j will move backward to locate the first element smaller than the pivot.

To prevent boundary issues, we need to add conditions like i <= high - 1 and j >= low + 1, ensuring that i doesn't move past the high index and j doesn't go below the low index.

Once we identify arr[i] > pivot and arr[j] < pivot, and if i is still less than j, we swap the values at arr[i] and arr[j].

We continue these steps until j is less than i.

Finally, we swap the pivot element (arr[low]) with arr[j], and return j, which is the partition index.

Answer

#include<bits/stdc++.h>
using namespace std;
int partition(vector<int> &arr, int low, int high) {
int pivot = arr[low];
int i = low;
int j = high;
while (i < j) {
while (arr[i] <= pivot && i <= high - 1) {
i++;
}
while (arr[j] > pivot && j >= low + 1) {
j--;
}
if (i < j) swap(arr[i], arr[j]);
}
swap(arr[low], arr[j]);
return j;
}
void qs(vector <int>&arr, int low, int high) {
if (low < high) {
int pIndex = partition(arr, low, high);
qs(arr, low, pIndex - 1);
qs(arr, pIndex + 1, high);
}
}
vector <int>quickSort(vector<int> arr) {
qs(arr, 0, arr.size() - 1);
return arr;
}
int main()
{ vector<int> arr = {4, 6, 2, 5, 7, 9, 1, 3};
int n = arr.size();
cout << "Before Using quick Sort: " << endl;
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
arr = quickSort(arr);
cout << "After Using quick sort: " << "\n";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
return 0;
} 

Output:
Before Using quick Sort:
4 6 2 5 7 9 1 3
After Using quick sort:
1 2 3 4 5 6 7 9
Time Complexity: O(N*logN), where N = size of the array.
Reason: At each step, we divide the whole array, for that logN and n steps are taken for the partition() function, so overall time complexity will be N*logN.
The following recurrence relation can be written for Quick sort :
F(n) = F(k) + F(n-1-k)
Here k is the number of elements smaller or equal to the pivot and n-1-k denotes elements greater than the pivot.
There can be 2 cases :
Worst Case – This case occurs when the pivot is the greatest or smallest element of the array. If the partition is done and the last element is the pivot, then the worst case would be either in the increasing order of the array or in the decreasing order of the array.
Recurrence: