Question

How much time it will take to sort n numbers by quick sort if some arbitrary algorithm takes (n2) time to choose pivot?

Answer 1

Explanation:

partition(arr[], lo, hi)

pivot = arr[hi]

i = lo // place for swapping

for j := lo to hi – 1 do

if arr[j] <= pivot then

swap arr[i] with arr[j]

i = i + 1

swap arr[i] with arr[hi]

return i

partition_r(arr[], lo, hi)

r = Random Number from lo to hi

Swap arr[r] and arr[hi]

return partition(arr, lo, hi)

quicksort(arr[], lo, hi)

if lo < hi

p = partition_r(arr, lo, hi)

quicksort(arr, p-1, hi)

quicksort(arr, p+1, hi)

Algorithm for random pivoting using Hoare Partitioning

partition(arr[], lo, hi)

pivot = arr[lo]

i = lo - 1 // Initialize left index

j = hi + 1 // Initialize right index

// Find a value in left side greater

// than pivot

do

i = i + 1

while arr[i] pivot

if i >= j then

return j

swap arr[i] with arr[j]

partition_r(arr[], lo, hi)

r = Random number from lo to hi

Swap arr[r] and arr[lo]

return partition(arr, lo, hi)

quicksort(arr[], lo, hi)

if lo < hi

p = partition_r(arr, lo, hi)

quicksort(arr, p, hi)

quicksort(arr, p+1, hi)