Quick Sort.pptx

Quick Sort

1. Quick Sort Dr. G. Jasmine Beulah, Assistant Professor, Kristu Jayanti College, Bengaluru

2. What is Quick Sort Most widely used sorting algorithm It follows Dive and Conquer paradigm Recursion is used in quicksort implementation In each recursive call, a pivot is chosen then the array is partitioned in such a way that all the elements less than pivot lie to the left and all the elements greater than pivot lie to the right. After every call, the chosen pivot occupies its correct position in the array which it is supposed to as in sorted array So with each step, our problem gets reduced by 2 which leads to quick sorting Pivot can be last element of current array, first element of current array or any random element.

3. //program to sort a list of N integers using quicksort #include< stdio.h > void main() { int i,n,a [50]; void quicksort( int a[], int,int ); clrscr (); printf ("\ nEnter the size of the array : "); scanf ("% d",&n ); printf ("Enter the elements of the arry \n\t"); for( i =0;i< n;i ++) { scanf ("% d",&a [ i ]); } printf ("\ nThe entered unsorted array\n");

4. for( i =0;i< n;i ++) { printf ("\ t%d ",a[ i ]); } quicksort(a,0,n-1); printf ("\ nSorted Array\n"); for( i =0;i< n;i ++) { printf ("\ t%d ",a[ i ]); } getch (); }

5. void quicksort( int a[], int low,int high) { int pivot,down,up,key,temp ; if(low<high) { down=low; pivot=low; up=high; key=a[pivot]; while(down<up) { while((a[down]<=key)&&(down<=high)) down++; while((a[up]>key)&&(up>=low)) up--;

6. if(down<up) { temp=a[up]; a[up]=a[down]; a[down]=temp; } } temp=a[up]; a[up]=a[pivot]; a[pivot]=temp; quicksort(a,low,up-1); quicksort(a,up+1,high); } return; }

7. Algorithm for mainegg A is an array of n elements. Step 1: Start Step 2: Read the size of the array into n Step 3: Read the array elements Step 4: Print unsorted list Step 5: Call the function quicksort(a,0,n-1) Step 6: Print the sorted list Step 7 : Stop

8. Algorithm for Quicksort Quicksort(a[], lb , ub ) Step1: if( lb < ub )           up= lb ; down= ub ; key=a[ lb ];    Step 2: while( lb <= ub )  Step 3: while(a[up] < key) up++;             [End of while]  Step 4: while(a[down] > key) down--;             [End of while]  Step 5 : if(up<down)             [Interchange a[up] with a[down]]             temp=a[up]; a[up]=a[down]; a[down]=temp;             [End of if]             [End of while loop in step 2]

9. Step 6: if(up>down)             [Interchange the key element a[ lb ] with a[down]]             temp=a[ lb ];a[ lb ]=a[down];a[down]=temp;             [End of if]  Step 7: Call quicksort(a, lb , down-1);  Step 8: Call quicksort(a, down+1,ub);               [End of if in step 1]