Quick Sort in C++

Quick sort is an efficient, in-place, comparison-based sorting algorithm that uses a divide-and-conquer strategy to sort an array or list of elements. First a pivot element is selected from the array and it partitions the other elements into two sub-arrays, doesn’t whether they are less or greater than the pivot. The pivot element is then in its final position in the sorted array. The sub-arrays are then recursively sorted using the same algorithm.

Following steps are used for quick sort:

1. Define a partition function that takes three arguments: the array, the low index, and the high index.
2. Within the partition function, choose the pivot element as the last element of the array.
3. Using two pointers, i and j, in order to iterate through the array.
4. If the current element is less than or equal to the pivot, swap it with the element at the pointer i and increment both i and j.
5. When the iteration is complete, swap the pivot element with the element at the pointer i+1. This places the pivot element in its final position in the sorted array.
6. Return the pivot index i+1.
7. Define a quickSort function that takes three arguments: the array, the low index, and the high index.
8. Inside the quickSort function, check if the low index is lesser than the high index.
9. If the low index is less than the high index, call the partition function to get the pivot index.
10. Recursively call the quickSort function for the sub-array to the left of the pivot index and the sub-array to the right of the pivot index.
11. Repeat steps 8-10 until the sub-array has only one element.
12. The array is now sorted.

In the main function, create an array of integers and call the quickSort function to sort the array. Finally, print the sorted array.

Here is an example of Quick Sort implemented in C++:

Example:

// C++ Implementation of the Quick Sort Algorithm.
#include <iostream>
using namespace std;
int partition(int arr[], int start, int end)
{


	int pivot = arr[start];


	int count = 0;
	for (int i = start + 1; i <= end; i++) {
		if (arr[i] <= pivot)
			count++;
	}


	// Giving pivot element its correct position
	int pivotIndex = start + count;
	swap(arr[pivotIndex], arr[start]);


	// Sorting left and right parts of the pivot element
	int i = start, j = end;


	while (i < pivotIndex && j > pivotIndex) {


		while (arr[i] <= pivot) {
			i++;
		}


		while (arr[j] > pivot) {
			j--;
		}


		if (i < pivotIndex && j > pivotIndex) {
			swap(arr[i++], arr[j--]);
		}
	}


	return pivotIndex;
}


void quickSort(int arr[], int start, int end)
{


	// base case
	if (start >= end)
		return;


	// partitioning the array
	int p = partition(arr, start, end);


	// Sorting the left part
	quickSort(arr, start, p - 1);


	// Sorting the right part
	quickSort(arr, p + 1, end);
}


int main()
{


	int arr[] = { 90, 32, 46, 21, 18, 88 };
	int n = 6;


	quickSort(arr, 0, n - 1);


	for (int i = 0; i < n; i++) {
		cout << arr[i] << " ";
	}


	return 0;
}

Output:

18 21 32 46 88 90

Now, you can see that input array [90, 32, 46, 21, 18, 88] is sorted now to 18 21 32 46 88 90.

Program Explanation:

The function partition() is used to find the pivot element and partition the array around it. The quickSort() function is then used to recursively sort the sub-arrays on either side of the pivot. In this example, the pivot element is the last element of the array.

In the example of Quick Sort in C++ provided above, the function partition() is used to find the pivot element and partition the array around it. It takes three arguments: the array, the start index, and the end index. The pivot element is chosen as the last element of the array. The function uses two pointers, i and j, to iterate through the array. If the current element is less than or equal to the pivot, it is swapped with the element at the pointer i and both i and j are incremented. This way, elements less than pivot are moved towards the left and element greater than pivot towards the right.

The quickSort() function is then used to recursively sort the sub-arrays on either side of the pivot. The partition index (pi) is obtained by calling the partition function. The function then recursively calls itself for the sub-array to the left of the partition index and the sub-array to the right of the partition index. It does this until the low index is less than the high index.

In the main function, it creates an array of integers and calls the quickSort() function to sort the array. It then prints the sorted array.

Conclusion:

Overall, Quick Sort is a very efficient sorting algorithm with an average time complexity of O(nlogn) and a worst-case time complexity of O(n^2) (if pivot is not chosen optimally). It is also efficient in its best case.