Quick Sort

Quick Sort

• Quick sort is a technique in which the array is divided into two sub arrays based on the element called pivot.

• The left subarray is having the elements less than pivot and right subarray is having the elements greater than pivot.

• Thus array is partitioned repeatedly and the elements in subarray are sorted.

• Finally these subarrays are combined to get a final sorted list.

• In merge sort the division of array is based on the positions of array elements, but in quick sort this division is based on actual value of the element. Consider an array A[i] where i is ranging from 0 to n-1 then we can formulize the division of array elements as

Let us understand this algorithm with the help of some example.

Example

Step 1:

Algorithm

The quick sort algorithm is performed using following two important functions –

Quick and partition. Let us see them -

Algorithm Quick(A[0...n-1],low,high)

//Problem Description: This algorithm performs sorting of

//the elements given in Array A[0...n-1]

//Input: An array A[0...n-1] in which unsorted elements are

//given. The low indicates the leftmost element in the list

//and high indicates the rightmost element in the list

//Output: Creates a sub array which is sorted in ascending

//order

if(low<high)then

//split the array into two sub arrays

m ← partition(Allow...high])// m is mid of the array

Quick(Allow...m-1])

Quick (A[mid+1...high])

In above algorithm call to partition algorithm is given. The partition performs arrangement of the elements in ascending order. The recursive quick routine is for dividing the list in two sub lists. The pseudo code for Partition is as given below -

Algorithm Partition (Allow...high])

//Problem Description: This algorithm partitions the

//subarray using the first element as pivot element

//Input: A subarray A with low as left most index of the

//array and high as the rightmost index of the array.

//Output: The partitioning of array A is done and pivot

//occupies its proper position. And the rightmost index of

//the list is returned

pivot ←  A[low]

i ← low

j ← high+1

while(i<=j) do

{

while(A[i] <= pivot) do

i ← i+1

while(A[j] >= pivot) do

j ← j-1;

if(i<=j) then

swap(A[i],A[j])//swaps A[i] and A[j]

}

swap(A[low],A[j])//when i crosses j swap A[low] and A[j]

return j//rightmost index of the list

The partition function is called to arrange the elements such that all the elements that are less than pivot are at the left side of pivot and all the elements that are greater than pivot are all at the right of pivot. In other words pivot is occupying its proper position and the partitioned list is obtained in an ordered manner.

C Program

/**************************************************

Program to sort the elements in ascending order using Quick Sort.

**************************************************/

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#define SIZE 10

void Quick(int A[SIZE], int, int);

int partition(int A[SIZE], int, int);

void swap(int A[SIZE], int *,int *);

int n;

int main()

{

int i;

int A[SIZE];

clrscr();

printf("\n\t\t Quick Sort Method \n");

printf("\n Enter Total numbers to sort: ");

scanf("%d", &n);

for(i=0;i<n;i++)

{

printf("\nEnter %dth number: ",i+1);

scanf("%d", &A[i]);

}

Quick (A,0,n-1);

printf("\n\n\t Sorted Array Is: \n");

for(i=0;i<n;i++)

printf("\t%d ",A[i]);

getch();

return 0;

}

/*

This function is to sort the elements in a sublist

*/

void Quick(int A[SIZE], int low,int high)

{

int m,i;

if(low<high)

{

m=Partition (A,low,high);//setting pivot element

Quick(A,low,m-1);//splitting of list

Quick (A,m+1,high);//splitting of list

}

}

/*

This function is to partition a list and decide the pivot

element

*/

int Partition(int A[SIZE], int low,int high)

{

int pivot =A[low],i=low,j=high;

while(i<=j)

{

while(A[i] <= pivot)

i++;

while(Alj]>pivot)

j--;

if(i<j)

swap(A,&i,&j);

}

swap(A,&low,&j);

return j;

}

void swap(int A[SIZE], int *i,int *j)

{

int temp;

temp=A[*i];

A[*i]=A[*j];

inom A[*j]=temp;

}

Output

Quick Sort Method

Enter Total numbers to sort : 8

Enter 1th number: 50

Enter 2th number: 30

Enter 3th number: 10

Enter 4th number: 90

Enter 5th number: 80

Enter 6th number: 20

Enter 7th number: 40

Enter 8th number: 70

Sorted Array Is:

10 20 30 40 50 70 80 90

 

Ex. 7.3.1 Consider following numbers, sort them using quick sort. Show all passes to sort the values in ascending order

25, 57, 48, 37, 12, 92, 86, 33

Sol. : Consider the first element as a pivot element.

Now, if A[i] < Pivot element then increment i. And if A[j] > Pivot element then decrement j. When we get these above conditions to be false, Swap A[i] and A[j]

After pass 1:

Ex. 7.3.2 Sort the following data to ascending order using quick sort. Show all passes with Pivot: 17, 8, -9, 2, 0, -5, 7, 20, 11, 15

Sol. : Consider the first element as pivot.

17        8        -9        2         0       -5        7       20        11      15

Pivot     i                                                                                    j

If A [i] < A [pivot] increment i. Similarly if A [j] > A [pivot] decrement j.

When we get these above conditions to be false, Swap A [i] and and A [j].

17        8        -9        2         0       -5        7       15        11      20

                                                                                       j

Swap A [Pivot] and A[j]