0
$\begingroup$

I'm studying Quick-Sort and I am confused as to how it works when the first element is chosen as the pivot point.

I am trying to trace the first step in the Quick-Sort algorithm, to move the pivot S[1] (17) into its appropriate position.

Example: [17, -10, 7, 19, 21, 23, -13, 31, 59].

^# = pivot
^ pointer

My understanding:

17, -10, 7, 19, 21, 23, -13, 31, 59
^#                               ^

Comparison 1. No swap.

17, -10, 7, 19, 21, 23, -13, 31, 59
^#                           ^

Comparison 2. No swap.

17, -10, 7, 19, 21, 23, -13, 31, 59
^#                      ^

Comparison 3. Swap.

-13, -10, 7, 19, 21, 23, 17, 31, 59
                     ^   ^#  

Comparison 4. Swap.

-13, -10, 7, 19, 21, 17, 23, 31, 59
                 ^   ^#  

Comparison 5. Swap.

-13, -10, 7, 19, 17, 21, 23, 31, 59
             ^   ^# 

Comparison 6. Swap.

-13, -10, 7, 17, 19, 21, 23, 31, 59
          ^  ^# 

Comparison 7. No swap.

 -13, -10, 7, 17, 19, 21, 23, 31, 59
       ^      ^# 

Comparison 9. No swap.

-13, -10, 7, 17, 19, 21, 23, 31, 59
  ^          ^# 

Comparison 10. No swap.

Is this how it works? Would it take 10 comparisons and 4 swaps to move pivot S[1] (17) into the correct position?

$\endgroup$
0
$\begingroup$

You only need to compare each elemnt with the pivot once.

You can do so by keeping the pivot in place and then swapping elements in the remainder of the array.

17, -10, 7, 19, 21, 23, -13, 31, 59
 #   ^                           ^

start

17, -10, 7, 19, 21, 23, -13, 31, 59
 #           ^                    ^

move left pointer to first element larger than pivot. 3 compares

17, -10, 7, 19, 21, 23, -13, 31, 59
 #           ^           ^

move right pointer to first element smaller than pivot. 3 compares

17, -10, 7, -13, 21, 23, 19, 31, 59
 #           ^           ^

swap elements at pointer

17, -10, 7, -13, 21, 23, 19, 31, 59
 #                ^      ^

move left pointer to first element larger than pivot. 1 compare

17, -10, 7, -13, 21, 23, 19, 31, 59
 #               ^^      

move right pointer to first element smaller than pivot (but not past left pointer. 1 compare

-13, -10, 7, 17, 21, 23, 19, 31, 59
             #      

swap pivot with last element smaller than it. 1 swap

total = 8 compares and up to n/2 swaps per partition.

$\endgroup$
0
$\begingroup$

Quicksort doesn't swap the pivot into its correct position in that way, but it lies on the hypothesis that each recursive call sorts the sub-array and then merging sorted sub-arrays would provide a completely sorted array:

  • let $V$ be the array to sort

  • $pivot \leftarrow pick()$ picks a pivot, in your case it's always the first element in $V$

  • let $V_{\lt}$ be a list $s.t. \forall a \in V_{\lt} \ a \in V \ \wedge \ a \lt pivot$

  • let $V_{=}$ be a list $s.t. \forall a \in V_{=} \ a \in V \ \wedge \ a = pivot$

  • let $V_{\gt}$ be a list $s.t. \forall a \in V_{\gt} \ a \in V \ \wedge \ a \gt pivot$

Quicksort then proceeds recursively calling itself on $V_{\lt}$ and $V_{\gt}$, thus assuming to get those two back with their values sorted.

The final step is then to return the concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$, in this order.

Providing a numerical example:

$V = [17, -10, 7, 19, 21, 23, -13, 31, 59]$

Steps:

  1. Initial run

    $pivot = 17$

    $V_{\lt} = [-10, 7, -13] $

    $V_{=} = [17] $

    $V_{\gt} = [19, 21, 23, 31, 59] $

  2. Recursion on $V_{\lt} = [-10, 7, -13] $

    $pivot = -10$

    $V_{\lt} = [-13] $

    $V_{=} = [-10] $

    $V_{\gt} = [7] $

    skips recursion on $V_{\lt}$ and $V_{\gt}$ since they're of size 1, thus already sorted

    returns $V_{sort}$ = concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$ = $[-13, -10, 7]$

  3. Recursion on $V_{\gt} = [19, 21, 23, 31, 59] $

    $pivot = 19$

    $V_{\lt} = [] $

    $V_{=} = [19] $

    $V_{\gt} = [21, 23, 31, 59] $

  4. Recursion on $V_{\gt} = [21, 23, 31, 59] $

    $pivot = 21$

    $V_{\lt} = [] $

    $V_{=} = [21] $

    $V_{\gt} = [23, 31, 59] $

  5. Recursion on $V_{\gt} = [23, 31, 59] $

    $pivot = 23$

    $V_{\lt} = [] $

    $V_{=} = [23] $

    $V_{\gt} = [31, 59] $

  6. Recursion on $V_{\gt} = [31, 59] $

    $pivot = 31$

    $V_{\lt} = [] $

    $V_{=} = [31] $

    $V_{\gt} = [59] $

    returns $V_{sort}$ = concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$ = $[31, 59]$

  7. Back from recursion in 5.

    returns $V_{sort}$ = concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$ = $[23, 31, 59]$

  8. Back from recursion in 4.

    returns $V_{sort}$ = concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$ = $[21, 23, 31, 59]$

  9. Back from recursion in 3.

    returns $V_{sort}$ = concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$ = $[19, 21, 23, 31, 59]$

  10. Back from recursion in 2.

    returns $V_{sort}$ = concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$ = $[-13, -10, 7, 21, 23, 31, 59]$

As you can see, from the step 3 and onwards, the chosen pivot isn't an optimal one, since there only are elements at its right, preventing the algorithm to run in optimal time of $\mathcal{O}(n log_2 n)$

EDIT: following Kai's comment, I fixed the definitions of $V_{\lt}$, $V_{=}$ and $V_{\gt}$. I also acknowledge this is the simpler and less efficient Lomuto's partition.

$\endgroup$
  • 1
    $\begingroup$ Thanks for attempting an explanation. In my view, your presentation could be improved by not conflating set notation (as e.g. for $V_<$) with list representation (which is what you use later when you talk about examples). Finally, there's a difference between Hoare's original quicksort and the one you describe (I think) in that yours is Lomuto's simpler but less efficient version. $\endgroup$ – Kai Nov 9 '18 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.