Quick Sort is a Divide and Conquer Algorithm. and a sort in place sorting algorithm.
So since it’s a Divide and Conquer algorithm it has three steps as we said before :-
Divide : which means partitioning the array into two sub arrays around a Pivot from right and left as Figure.
Second Step is
Conquer : as you may expect , it recursively sort the sub arrays
but we don’t Combine….
Actually the Quick Sort depends mainly of partitioning (you will see what it means in code)
before i explain what is partitioning i prefer showing some figures of how it works, try to know what those figures mean before u skip it.
After u saw the figures, it’s now safe to illustrate what is that partitioning. in our array as we said before divide it to two sub-arrays that are around the pivot. but we don’t just pick a pivot and then divide the arrays around it. yea we pick a pivot but the right sub array’s elements should be greater than the pivot and the left sub-array’s elements should be less than the pivot. so what partitioning do is modify the big array to look the way we want ( left sub array less than pivot – pivot – right sub array greater than pivot )
So what happens in those figures or the partitioning process is that we pick the first element as a pivot and loop the array from two directions with two iterators (i, j). i determines the smaller elements. j determines the greater elements. the partitioning process is a loop while i is not bigger than j.Well, let’s check what those iterators do in the partitioning process.
i assigned to 2nd element , j assigned to last element
i begins iterating skipping elements that are smaller than the pivot (6) and then meets (12)
i says : Oh!! this (12) is bigger than the pivot, (i)’s loop breaks
then j start iterating skip elements that are greater than the pivot(6) and then meets(2)
j says : Umm, 2 is less that the pivot , (j)’s loop breaks
then we check if i is bigger than j ?? – No!! – then continue to the exchange.
then we exchange the element at (i) and the element at (j).
the big loop goes on…
i continues iterating from where it stopped skipping elements smaller than the pivot and then it meets (9)
i says : Come on!! 9 is bigger than the pivot , I wanna get the hell out of this loop!! and (i)’s loop breaks..
j continues iterting from where it stopped skipping elements greater than the pivot and then it meet’s (1)
j says : Woah!! There is (1) in there which is less than the pivot, and (j)’s loop breaks
then we check if (i) is bigger than (j)?? – No – Well, continue to the exchange
we exchange element at (i) with the element at (j)
the big loop goes on…
i continues iterating from where it stopped Bla Bla Bla, then it meet’s (9)
i says : 9 is greater than the pivot , (i)’s loop breaks..
j continues iterating from where it stopped Bla Bla Bla , then it meet’s (1)
j says : 1 is less than the pivot , (j)’s loop breaks
then we check if (i) is greater than (j)?? – YEA!!! – big loop breaks
then we exchange the element at the pivot with the element at j
As you can see after all these loops and conversations we have our big array the way we want ( smaller elements – pivot – greater elements)
and then we do the partitioning recursively on the two sub-arrays till we have one big sorted array.
but before i show u the code there are some stuff u need to know :).
Picking a pivot is actually a critical matter because you might pick 1 as a pivot and then end up having totally unbalanced recursion tree, which will cost you more time. and if u pick 6 u will have a balanced recursion tree. this is actually a big matter and lots of researches are being done over that point. so we just ignore all that 😉 , and pick the first element as a pivot.
but what if the array was already sorted??
Some might say : Woah, that must be my lucky day!!
Sorry to shock you but it’s not ur lucky day. Quick sort’s worst case is when the array is sorted or reverse sorted because while you are doing recursion you will end up having a big unbalanced one way tree!! which is totally catastrophic.
Now Let’s see the code
Java Code :-
Python Code :-
Feel free to Ask any question 🙂