Quick Sort with first element as pivot

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

place the pindex point to the last index in the array.Compare each and every element with pivot if the element is greater the pivot swap with pindex and decrement the pindex..The Following code helps you for the implementation of partition

def partioning(a,s,e):
pivot=a[s]
pi=e
for i in range(1,e):
 if(a[i]>=pivot):
   a[i],a[pi]=a[pi],a[i]
   pi-=1
a[pi],a[s]=a[s],a[pi]
return pi