Quick Sort Program with Algorithm #8 by Md Farrukh Asif

 

QUICK SORT

Program – 1

 

// Quick sort in C

#include <stdio.h>

// function to swap elements

void swap(int *a, int *b) {

int t = *a;

*a = *b;

*b = t;

}

// function to find the partition position

int partition(int array[], int low, int high) {

// select the rightmost element as pivot

int pivot = array[high];

// pointer for greater element

int i = (low - 1);

// traverse each element of the array

// compare them with the pivot

for (int j = low; j < high; j++) {

if (array[j] <= pivot) {

// if element smaller than pivot is found

// swap it with the greater element pointed by i

i++;

// swap element at i with element at j

swap(&array[i], &array[j]);

}

}

// swap the pivot element with the greater element at i

swap(&array[i + 1], &array[high]);

// return the partition point

return (i + 1);

}

void quickSort(int array[], int low, int high) {

if (low < high) {

// find the pivot element such that

// elements smaller than pivot are on left of pivot

// elements greater than pivot are on right of pivot

int pi = partition(array, low, high);

// recursive call on the left of pivot

quickSort(array, low, pi - 1);

// recursive call on the right of pivot

quickSort(array, pi + 1, high);

}

}

// function to print array elements

void printArray(int array[], int size) {

for (int i = 0; i < size; ++i) {

printf("%d  ", array[i]);

}

printf("\n");

}

// main function

int main() {

int data[] = {8, 7, 2, 1, 0, 9, 6};

int n = sizeof(data) / sizeof(data[0]);

printf("Unsorted Array\n");

printArray(data, n);

// perform quicksort on data

quickSort(data, 0, n - 1);

printf("Sorted array in ascending order: \n");

printArray(data, n);

}

========

 

ALGORITHM

 

Let A be a linear array of n elements A (1), A (2), A (3)......A (n), low represents the

 

lower bound pointer and up represents the upper bound pointer. Key represents the first element of the array, which is going to become the middle element of the sub-arrays.

 

1.     Input n number of elements in an array A

 2.     Initialize low = 2, up = n , key = A[(low + up)/2]

 3.     Repeat through step 8 while (low < = up)

 4.     Repeat step 5 while(A [low] > key)

 5.     low = low + 1

 6.     Repeat step 7 while(A [up] < key)

 7.     up = up–1

 8.     If (low < = up)

 (a)  Swap = A [low]

 (b)  A [low] = A [up]

 (c)   A [up] = swap

 (d)  low=low+1

 (e)  up=up–1

 9.     If (1 < up) Quick sort (A, 1, up)

 10.If (low < n) Quick sort (A, low, n)

 11. Exit

==========

 

PROGRAM-2 

//PROGRAM TO IMPLEMENT QUICK SORT

//USING ARRAYS RECURSIVELY

//CODED AND COMPILED IN TURBO C

#include<conio.h>

#include<stdio.h>

#define MAX 30

enum bool {FALSE,TRUE};

//Function display the array

void display(int arr[],int low,int up)

{

int i;

for(i=low;i<=up;i++)

printf (“%d ”,arr[i]);

}

//This function will sort the array using Quick sort algorithm void quick(int arr[],int low,int up) {

int piv,temp,left,right;

enum bool pivot_placed=FALSE;

//setting the pointers

left=low;

right=up;

piv=low; /*Take the first element of sublist as piv */

if (low>=up)

return;

printf (“\nSublist : ”);

display(arr,low,up);

/*Loop till pivot is placed at proper place in the sublist*/

while(pivot_placed==FALSE)

{

/*Compare from right to left  */

while( arr[piv]<=arr[right] && piv!=right )

right=right–1;

if ( piv==right )

pivot_placed=TRUE;

if ( arr[piv] > arr[right] )

{

temp=arr[piv];

arr[piv]=arr[right];

arr[right]=temp;

piv=right;

}

/*Compare from left to right */

while( arr[piv]>=arr[left] && left!=piv )

left=left+1;

if (piv==left)

pivot_placed=TRUE;

if ( arr[piv] < arr[left] )

{

temp=arr[piv];

arr[piv]=arr[left];

arr[left]=temp;

piv=left;

}

}/*End of while */

printf (“-> Pivot Placed is %d -> ”,arr[piv]);

display(arr,low,up);

printf ("\n");

quick(arr,low,piv–1);

quick(arr,piv+1,up);

}/*End of quick()*/

void main()

{

int array[MAX],n,i;

clrscr();

printf (“\nEnter the number of elements : ”);

scanf (“%d”,&n);

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

{

printf (“\nEnter element %d : ”,i+1);

scanf (“%d”,&array[i]);

}

printf (“\nUnsorted list is :\n”);

display(array,0,n–1);

printf (“\n”);

quick (array,0,n–1);

printf (“\nSorted list is :\n”);

display(array,0,n–1);

getch();

}/*End of main() */

=====

 

TIME COMPLEXITY

 

The time complexity of quick sort can be calculated for any of the following case. It is usually measured by the number f (n) of comparisons required to sort n elements.

 WORST CASE

 The worst case occurs when the list is already sorted. In this case the given array is partitioned into two sub arrays. One of them is an empty array and another one is an array. After partition, when the first element is checked with other element, it will take n comparison to recognize that it remain in the position so as (n – 1) comparisons for the second position.

 

f (n) = n + (n –  +2 +1

(n (n + 1))/2

 O(n2)

 AVERAGE CASE

 In this case, each reduction step of the algorithm produces two sub-arrays. 

Accordingly :

 (a) Reducing the array by placing one element and producing two sub-arrays.

 (b) Reducing the two sub-arrays by placing two elements and producing four sub-arrays.

 (c) Reducing the four sub-arrays by placing four elements and producing eight sub-arrays.

 And so on. The reduction step in the kth level finds the location at 2k–1 elements; how-ever there will be approximately log2 n levels at reduction steps. Furthermore each level uses at most n comparisons,

 so        f (n) = O(n log n)

 

 

 

BEST CASE

 

The base case analysis occurs when the array is always partitioned in half, That key = A [(low+up)/2]

 

f (n) = Cn +f (n/2) + f (n/2)

 

= Cn + 2f (n/2)

 

= O(n) where C is a constant.

=====================