CPS 6, Ramm - Spring 2000 - 4/7/00, #31
- Announce
- No Quiz Today
- Guest Instructor: Prof. Robert Duvall
11. Sorting, Templates, and Generic Programming
- Quicksort
- A pivot element of the vector being sorted is chosen. Elements
of the vector are rearranged so that elements less than or equal to the
pivot are moved before the pivot. Elements greater than the pivot
are moved after the pivot. This is called the partition step.
- Quick sort (recursively) the elements before the pivot.
- Quick sort (recursively) the elements after the pivot.
<![CDATA[
void Quick(tvector<int> & a,int first,int last)
// postcondition: a[first] <= ... <= a[list]
{
int piv;
if (first < last)
{
piv = Pivot(a,first,last);
Quick(a,first,piv-1);
Quick(a,piv+1,last);
}
}
]]>
- The Partition Function
- Desired outcome:
- +-------------------+---+------------------+
- |...elements <= X...| X |...elements > X...|
- +-------------------+---+------------------+
- first...............pivot..............last
- Initially:
- +---+--------------------------------------+
- | X |............ ? ? ? ...................|
- +---+--------------------------------------+
- ..p..k.................................last
- first
- After several iterations:
- +---+------------+-----------+-------------+
- | X |... <= X ...|... > X ...|... ? ? ? ...|
- +---+------------+-----------+-------------+
- first...........p.............k........last
- All elements processed:
- +---+----------------+---------------------+
- | X |..... <= X .....|........ > X ........|
- +---+----------------+---------------------+
- first...............p..................last.k
- After swapping 1st element to pivot loc:
- +----------------+---+---------------------+
- |..... <= X .....| X |........ > X ........|
- +----------------+---+---------------------+
- first............pivot.................last
- Note Invariant: 3rd diagram true after every iteration
- first...p: values <= pivot value
- p+1...k-1: values > pivot value
- k...last1: values not yet examined
<![CDATA[
int Pivot(tvector<int> & a,int first,int last)
{
int piv, k, p=first;
piv = a[first];
for(k=first+1; k <= last; k++)
{
if (a[k] <= piv)
{
p++;
Swap(a[k],a[p]);
}
}
Swap(a[p],a[first]);
return p;
}
]]>
- Looking at the Code
timesort.cpp