next up previous
Next: Quicksort: Partitioning II Up: SORTING BY SPLITING Previous: SORTING BY SPLITING

Quicksort: Partitioning

Partition I. 


   $x:=A[p]$; $i:=p-1$; $j:=r+1$

while (TRUE) do 


  Repeat Decrement j until $A[j] \leq x$

  Repeat Increment i until $A[i] \geq x$

  if $i<j$

     then exchange $A[i]$ and $A[j]$

    else return $j$

endwhile
$x=15$
15 7 23 5 20 3


















Why do $i$ and $j$ never get out of array bounds?
$W(n) = n + 2$ comparisons

$W(n)=O(n^{2})=O(n)+W(n-1)$









$B(n)=O(n)+2B(n/2)=O(n \log n)$

Balance Partitioning:

Quicksort Improvements
- random x
- median of first, middle and last items
- insertion sort for $n \leq 15$
$S(n)=O(n)$
(See 7-4; reduces $S(n)$ to $O(\log n)$)

next up previous
Next: Quicksort: Partitioning II Up: SORTING BY SPLITING Previous: SORTING BY SPLITING
Sushil_Prasad 2014-09-25