Quick Sort

Sorting Algorithm

Share

About Quick Sort

This sorting algorithm uses the idea of divide and conquer. It finds the element called pivot which divides the array into two halves in such a way that elements in the left half are smaller than pivot and elements in the right half are greater than pivot.
We follow three steps recursively:

  • Find pivot that divides the array into two halves.
  • Quick sort the left half.
  • Quick sort the right half.

Algorithm


/*
a[0:n-1] is an array of n elements.
beg = first index of array
end = last index of array
*/
QuickSort(a, beg, end)
Begin
    if beg < end then
        Call PartitionArray(a, beg, end, pivotLoc);    //this will find pivot location
        Call QuickSort(a, beg, pivotLoc - 1 );   //Quick sort left sub array
        Call QuickSort(a, pivotLoc + 1, end);    //Quick sort right sub array
    endif
End

Code in C


#include <stdio.h>
#define SIZE 6	//array size


void partitionArray(int *a, int beg, int end, int *pivotLoc);
void quickSort(int *a, int beg, int end);

int main(){
	int a[SIZE] = {5,2,6,1,3,4};	//unsorted array
	int i;

	quickSort(a, 0, SIZE-1);	//beg = 0 start index of array end = 5 last index of array

	//printing sorted element of array
	for(i = 0; i < SIZE; i++){
		printf("%d\t", a[i]);
	}
	return 0;
}//main() ends here

void quickSort(int *a, int beg, int end){
	int pivotLoc;
	if(beg < end){
		partitionArray(a, beg, end, &pivotLoc);	//this will find the pivot location and partition the array
		quickSort(a, beg, pivotLoc - 1);	//quick sort the left sub array
		quickSort(a, pivotLoc + 1, end);	//quick sort the right sub array
	}
}//quickSort() ends here

void partitionArray(int *a, int beg, int end, int *pivotLoc){
	int left = beg;		//initially left point to the first element of the array
	int right = end;	//initially right point to the last element of the array
	*pivotLoc = left;	//initially pivot point to first element of the array
	int tmp;	//used for swapping values

	while(1){

		//pivot pointing at left
		while(a[*pivotLoc] <= a[right] && *pivotLoc != right){	//pivot element <= right element
			right--;	//move right one position towards left
		}

		if(*pivotLoc == right){	//both left and right pointing at same element of the array
			break;
		}else if(a[*pivotLoc] > a[right]){
			//pivot element greater than right element. swap pivot and right element.
			tmp = a[right];
			a[right] = a[*pivotLoc];
			a[*pivotLoc] = tmp;
			*pivotLoc = right;	//pivot is now pointing to right
		}

		//pivot pointing to right
		while(a[*pivotLoc] >= a[left] && *pivotLoc != left){	//pivot element >= left element
			left++;		//move left one position towards right
		}

		if(*pivotLoc == left){	//both left and right pointing at the same element of the array
			break;
		}else if(a[*pivotLoc] < a[left]){
			//pivot element smaller than left element. swap pivot and left element.
			tmp = a[left];
			a[left] = a[*pivotLoc];
			a[*pivotLoc] = tmp;
			*pivotLoc = left;	//pivot is now pointing to left
		}
	}
}//partitionArray() ends here

Time Complexity

For an array of n elements order of Quick Sort is O(nlog2n)

Recently Added