Mumbai University > Information Technology > Sem 3 > Data Structure and Algorithm analysis

Marks: 10 M

Year: Dec 2014, May 2015

• The quick sort algorithm is a widely used algorithm developed by C. A. R Hoare.
• It is a fast method of sorting as compared to many other similar sorting algorithms.
• The main role in a quick sort is done by the pivot element. The pivot element is an element among the given data that is chosen for the current iteration cycle.
• At the end of the iteration, the pivot element will be at its final position as in a sorted list.
• The element to left of pivot will be less than the pivot element and to the right of it will be greater than the pivot element. (But not sorted!)
• Let us consider an example

We set the pivot element to the left-most number as well as the left pointer. Also we set the right pointer to the rightmost value.

Now compare if a[pivot]>a[right].No.

So decrease the Right pointer by 1.

Now compare if a[pivot]>a[right].Yes.

Swap them. Also set the right pointer as pivot.

Increase Left pointer by 1.

Now compare if a[left]>a[pivot].No

Increase left pointer by 1.

Now compare if a[left]>a[pivot].Yes

Swap them. Also set left pointer as pivot.

Decrease right pointer by 1.

Since Left and Right are now the same, the pivot element is in its correct position.

Here the elements to the left are less than the pivot. Similarly the element to the right of pivot is greater than it.

So the search area is reduced. Apply a quicksort on the left part and right part separately. Algorithm:

QuickSort(array,begin,end)

i. If (begin<end)< p="">

a. divide(array,begin,end,pivot)

b. quickSort(array,begin,pivot-1)

c. quicksort(array,pivot+1,end)

d. END IF ii. STOP

Divide(array,begin,end,pivot)

i. Set Left=Begin , Right=End, pivot=begin

ii. Initialize flag to false.

iii. While Flag=false.

a. While array[pivot]<=array[right] and pivot≠right.

Decrement right by 1.

b. If pivot=right

Set Flag=True.

c. Else if array[pivot]>array[right]

Swap array[pivot] and array[right].

Set right pointer as pivot.

d. If flag=false

1. While array[pivot]>=array[left] and pivot≠left

Increment left pointer by 1.

1. IF pivot=left

   Set Flag=false.

2. Else if array[pivot]<array[left]< p="">

Swap array[pivot] and array[left].

Set left pointer as pivot.

iv. Return pivot position.

• Let us assume that T(n) be the complexity and that all elements are distinct. Recurrence for T(n) depends only on two subproblem sizes which depend on partition element. If pivot is ith smallest element, then exactly (i-1) items will be in the left part and (n-i) in the right part. Since each element has equal probability of being selected as pivot, the probability of selecting ith element is 1/n.

• In best case: each partition splits array in halves.

$T(n) = 2T(n/2) + Θ(n) = Θ(n logn)$

• In worst case: Each partition gives unbalanced spilt.

$T(n) = T(n-1) + Θ(n) = Θ(n2)$

• In average case: $T(n) = O(n logn)$

So, quicksort ranges from O(n log n) with the best pivots, to O(n) with the worst pivots, where n is the number of elements in the array.