Page Contents
Quick Sort is also known as partition exchange sort which sorts elements using works a divide-and-conquer strategy to sort an array. In divide and conquer first divide an unsorted array into two smaller sub-arrays on the basic of pivot element and then further sub-array if possible. These sub-arrays are recursively called to sort the elements.
Quick Sort algorithm developed by C. A. R. Hoare which is a widely used sorting the elements of a list. In the average case, Quick Sort makes O(n log n) comparisons to sort an array of n elements. And in the worst case, it has a quadratic running time O(n2).
- Quick sort is a recursive algorithm that follows a divide-and-conquer strategy.
- The time complexity of the Quick Sort algorithm is O(nlogn) in the average case.
- The time complexity of the Quick Sort algorithm is O(n2) in the worst case.
- Quick Sort is an in-place sorting algorithm it means it takes an only a constant amount of memory to perform the sorting algorithm.
- Quick Sort is often the efficient sorting algorithm that is used by most of the language libraries to perform sorting.
So in this lesson we will see working of Quick Sort algorithm with an example.
How does quick sort algorithm works?
Suppose we have an array arr which contains list of integers and we want to re-arrange this list in increasing order. So in Quick Sort first we select one of the elements from the array as pivot and then we re-arrange the array in such a way all the elements lesser than the pivot element are at the left of it and all the
greater elements than the pivot elements are towards the right.
Lets consider we have an array
arr = {14,5,12,8,2,11,7}
So here first we will select right most element as pivot means in this example 7 is choosen as pivot.
Now after rearranging the array, array arr will look likes
{5,2,7,8,14,11,12}
- First pivot element is chosen from the array, 7 is chosen here as a pivot.
- Also we have two variable pindex and i.
- arr[i] is compared to pivot element, if arr[i] is smaller than the pivot and also greater than pindex then swap a[i] with pindex and increment pindex by 1.
- Else if arr[i] is greater than pivot then just move forward by an increment of i. This process will run till i < n.
- Now Pivot 7 is sorted so our array arr will be partitioned into sub array like
In this case now we have two pivot elements, one in each sub arrays.
Algorithm of quick sort
Quick Sort Pivot Algorithm
Step 1– Initialize an array arr
Step 2 − Choose the rightmost element as a pivot
Step 3 − Take two variables pIndex and i which is pointing to left most element excluding pivot
Step 4 − While value at arr[i] is less than pivot then swap arr[i] with pIndex, increase pIndex by 1
Step 5 − While value at arr[i] is greater than pivot increment i by 1
Step 6 − if both step 3 and step 4 does not match then swap pivot to pIndex
Step 7 − pIndex is now pivot
Step 8 – Follow step 2 to 6 to find a pivot for each sub array
Quick Sort Algorithm
Step 1 − Make the right-most index value pivot
Step 2 − partition the array using pivot value
Step 3 − quicksort left partition recursively
Step 4 − quicksort right partition recursively
Time complexity of Quick Sort
Best-case performance: O(nlogn)
Average performance: О(nlogn)
Worst-case performance: О(n2)
Space Complexity: O(1)
Pseudo Code of Quick Sort
function swap(int a, int b)
temp = a
a = b
b = temp
end of function
function partitionFunc(arr, start, end)
pivot=arr[end]
pindex=start
for i = start to end - 1
if(arr[i] <= pivot)
swap(arr[i], arr[pindex])
pindex + 1
end of if
end of for
swap(arr[pindex], arr[end])
end function
procedure quickSort(arr, start, end)
if(start<end)
pindex = partitionFunc(arr, start, end)
quickSort(arr,start,pindex-1)
quickSort(arr,pindex+1,end)
end if
end procedure
Quick Sort Program in C
#include<stdio.h> void swap(int *a, int *b ); void quickSort(int *arr, int start, int end); int partition(int *arr, int start, int end){ int pivot = arr[end]; int pIndex=start; for(int i=start; i<end; i++){ if(arr[i]<=pivot){ swap(&arr[i],&arr[pIndex]); pIndex++; } } swap(&arr[pIndex], &arr[end]); return pIndex; } void swap(int *a, int *b ){ int temp = *a; *a=*b; *b=temp; } void quickSort(int *arr, int start, int end){ if(start<end){ int pIndex = partition(arr, start, end); quickSort(arr, start, pIndex-1); quickSort(arr,pIndex+1,end); } } int main(){ int arr[100],i,j,n,key; printf("Enter the number of elements you want to sort:\n"); scanf("%d",&n); printf("Now enter the %d elements you want to sort: \n",n); for(i=0;i<n;i++){ scanf("%d",&arr[i]); } printf("before sorting:\n"); for(i=0;i<n;i++){ printf("%d \t",arr[i]); } quickSort(arr,0,n); printf("\n"); printf("after sorting:\n"); for(int i=0; i<n; i++) printf("%d \t",arr[i]); return 0; }
Output:
Share On :