[go: up one dir, main page]
Scribd
Upload
29 views8 pages

Quick Sort

Uploaded by

praveen tummalacharla
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
29 views8 pages

Quick Sort

Uploaded by

praveen tummalacharla
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 8

Quick sort (1 of 8)

• Quick sort algorithm was developed by C.A.R Hoare in 1962.


• Like bubble sort quick sort is an exchange sort ,i.e. , items swap positions till the entire array is
sorted.
• The quick sort is more efficient because it requires fewer exchanges to correctly position an
element.
• The basic principle underlying the quick sort algorithm is to pick one element in the array and
rearrange the remaining elements around it.
• The chosen element is called the pivot(usually first element of list).
• Once the pivot is chosen , all the elements lesser than the pivot are moved to the left of the pivot,
and all elements equal to or greater than the pivot are moved to the right of the pivot.
• The pivot acts as a partition dividing the original lists into two sub lists, and after the partitioning,
the pivot is in its correct position in the sorted list.
• This procedure of choosing the pivot and partitioning the list is recursively applied to the sub lists
till the subsequent sub lists consists of only one element and entire list is sorted.

1 1
Quick sort (2 of 8)

1 2
Quick sort Algorithm (3 of 8)
1.Start

2.Read the no of elements to sort(n).

3.Read elements to be sorted in array a


a[0]………a[n-1]

4.Call quick sort function


quicksort(a,0,n-1)

5.Print the sorted array a[0]…..a[n-1]

6.Stop

1 3
Quick sort (4 of 8)
Algorithm quicksort(int a[10],int first,int last)
{
i=first; j=last; pivot=first;
if(first<last)
{
while(i<j)
{
while(x[i]<=x[pivot]&&i<last)
Complexity of quick sort: i++;
while(x[j]>x[pivot])
Best case: O(n logn) j--;
if(i<j)
{
Average case:O(n logn) t=x[i]; x[i]=x[j]; x[j]=t;
}
2
Worst case: O(n ) }
t=x[pivot]; x[pivot]=x[j]; x[j]=t;
}
qsort(x,first,j-1);
qsort(x,j+1,last);
1 4
}
Quick sort example (5 of 8)

1 5
Quick sort (6 of 8)

1 6
Quick sort (7 of 8)

1 7
Quick sort (8 of 8)

1 8

You might also like