In this Quicksort algorithm, it uses the pivot in the first location of each list. I am having difficulty understanding how to do this algorithm. When I look at examples online, and work out the problem(s) myself, it seems like the book does it differently, and I'm not sure what is the problem. I am unable to get the first pass correct that matches in the text. I added my first pass attemps below. Any help appreciated. Thanks.


First Example:

Original List: [6,2,4,7,1,3,8,5]
First pass in the text: [5,2,4,1,3,6,8,7]
Second pass in the text: [3,2,4,1,5,6,8,7]

My first pass attempt: [3,2,4,5,1,6,8,7]


Second Example:

Original List: [15,4,10,8,6,9,16,1,7,3,11,14,2,5,12,13]

First pass in the text: [13,4,10,8,6,9,1,7,3,11,14,2,5,12,15,16]
Second pass in the text: [12,4,10,8,6,9,1,7,3,11,2,5,13,14,15,16]

My first pass attempt: [12,4,10,8,6,9,13,1,7,3,11,14,2,5,15,16]

The textbook is called "Analysis of Algorithms: An Active Learning Approach:" 2nd Edition. I got those two problems at the back of the book in Appendix C. The book discusses Quicksort in Chapter 4.

But isn't your algorithm working? It picks a pivot and throws all lower elements to the left of it and all higher elements to the right of it. Apply it recursevly on the "lower" sublist and the "higher" sublist and I think it should work.

Just a note: Don't use the first item as pivot. If the list is already sorted it will reach the worst case scenerio O(n^2) instead of O(nlog(n)). I got recommended to use either the middle element or random element as it is less likely to reach the worst case O(n^2)

Thanks. I just thought it was a certain way you have to rearrange the sublists after the pivot location. As long as numbers that are lower than the pivot, it doesn't matter what order they are in right? Likewise, with the larger numbers in the other sublist.

This article has been dead for over six months. Start a new discussion instead.