Quick Sort was invented by Charles Antony Richard Hoare (Tony Hoare or C. A. R. Hoare) in the year 1959. His paper, "Quicksort", published in 1961, introduced the algorithm and its key properties, highlighting its efficient sorting capabilities.
Quick Sort is a highly efficient sorting algorithm and is based on a divide and conquer strategy. Algorithm consider a sorting method that performs very well on larger arrays and lists. At each step in the method, the goal is to place a particular (pivot) element in its final position within the array. In so doing, "all elements to the left of pivot are smaller than the pivot and all elements to the right of pivot are greater than or equal to the pivot". This technique essentially partitions the array into two sub-arrays. The same process can then be applied to each of these sub-arrays and repeated until all elements are placed in their final positions.
This quick sort method of sorting is also called partition-exchange procedure. Each time a sub-array is divided into two smaller sub-arrays; these can be processed in turn using either an iterative or recursive.
function quickSort(arr, low, high)
if low < high then
// pi is partitioning index, arr[pi] is now at right place
pi := partition(arr, low, high)
// Separately sort elements before partition and after partition
quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
function partition(arr, low, high)
// pivot (Element to be placed at right position)
pivot := arr[high]
i := (low - 1) // Index of smaller element
for j = low to high - 1 do
// If current element is smaller than the pivot
if arr[j] < pivot then
i := i + 1
swap arr[i] with arr[j]
// swap arr[i+1] and arr[high] (or pivot)
swap arr[i + 1] with arr[high]
return (i + 1)
// Utility function to swap two elements in an array
function swap(a, b)
temp = a
a = b
b = temp
#include <stdio.h>
// Function to swap two elements
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++)
{
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main()
{
int list[20],size,i;
printf("Enter size of the list: ");
scanf("%d",&size);
printf("Enter %d integer values: ",size);
for(i = 0; i < size; i++)
scanf("%d",&list[i]);
quickSort(list,0,size-1);
printf("List after sorting is: ");
for(i = 0; i < size; i++)
printf(" %d",list[i]);
return 0;
}