Question

Quicksort is an efficient sorting algorithm.

Question:

For the non-randomized version of Quicksort, what are the best and the worst initial arrangements of the elements to be sorted? Justify your answer

Answer 1

I believe you are learning quick sort.

Before i start to answer lets look at few insights,

Quicksort, select a pivot and pivot is the last element in the array,

Now, this pivot needs to be placed, at its right position, this means if we follow this procedure for every array value, array gets sorted.

Now lets look at,

BEST CASE

1 2 3 6 7 8 4

Now see, the pivot is 4, and its right position is 3 in the array that means after PARTITION we will have array like this,

1 2 3 4 6 7 8, now as you can see, pivot 4 has divided array into 2 equal arrays,

1 2 3 and 6 7 8

So we have n-1/2 and n-1/2, sizes of 2 arrays

Thus, this takes us to time complexity of

NlogN, best case

WORST CASE

1 2 3 4 5 6 7 8

If pivot is 8, it will divide array like

1 2 3 4 5 6 7 and 8

Which is n-1 and 1

This gives us time complexity of

N*N,

Now as you can see, if array is sorted in

Desc or Asc order, it will give you the WORST CASE.

Hope i helped you.

Happy Learning.