CODEWITHSUNDEEP
algorithmsortingquicksort
Jackson F
Jackson F

Reputation: 48

Quicksort - Worst case condition

I see similar questions to this have been asked before, but I've been searching for a while and can't seem to find an answer.

The assignment I have right now is to use the quicksort algorithm to sort a simple array of 7 letters. We need to show each step of the sort, underlining the pivot each time. Our instructor asked that we use the rightmost value as the pivot for each step. Based on this video, https://www.youtube.com/watch?v=aQiWF4E8flQ ,this is what I have so far (pivot in bold):

GACEFBD

A|GCEFBD

AC|GEFBD

ACB|EFGD

ACBD|FGE

But I'm unsure of where to go from here. On the left side of the partition, D is the pivot, but there are no values larger than D. So where does the pivot go? Every tutorial I've seen uses the median of three as a pivot, or the leftmost, and I'm not the best at algorithms.

Part B has us showing every step of sorting ABCDEFG, with the same rules. Not sure where to begin there, since I have the same problem. Sorry if this is a dumb question.

Upvotes: 2

Views: 798

Answers (1)

Barranka
Barranka

Reputation: 21047

Consider what happens on each iteration.

Remember, quick sort works like this:

  1. If the array is empty, return an empty array and exit
  2. If the array has only one entry, return the entry and exit
  3. Choose a pivot
  4. Split the array in three sub-arrays:
    • Values smaller than the pivot
    • The pivot
    • Values larger than the pivot
  5. For each non-empty array, apply quick sort again and concatenate the resulting arrays

(I know I'm using the word "array" vaguely... but I think the idea is clear)

I think that you're missing a simple fact: Once you choose the pivot, you put it in it's right place, and apply quick sort to the other arrays... you don't apply quick sort to the pivot again.

Let's say you have a function called QuickSort(Array, Pivot), and let's assume you always take the left-most entry of the array as pivot:

  • Start: QuickSort(GACEFBD , D)
  • 1st. iteration:

    [QuickSort(ACB, B), D, QuickSort(GEF, F)]

    As you can see, the right-most value can be a "good" pivot.

    After the first iteration, D is already in its right place

  • 2nd. iteration:

    [[QuickSort(A,A), B, QuickSort(C,C)], D, [QuickSort(E,E), F, QuickSort(G,G)]]

  • Result:

    [A, B, C, D, E, F, G]

Punch line: Even if you take the right-most entry of the array, there may be cases where that entry is a "good" pivot value.

The real worst case would be applying quick sort on an already sorted array. But the same rules apply. Try to apply the above process to something like this: QuickSort(ABCDEFG, G)

Upvotes: 1

Related Questions