(^70) | Chapter 4: Sorting Algorithms
How can we usepartitionto select the median efficiently? First, let’s review the
results of this method, as shown on a sample unsorted array of 16 elements. The
first step is to swap thepivotwith the rightmost element. As the loop inpartition
executes, the key variables from the implementation are shown in Figure 4-10.
storeis the location identified by the circle. Each successive row in Figure 4-10
shows when the loop inpartitionidentifies, from left to right, an elementA[idx]
that is smaller than or equal to thepivot(which in this case is the element “06”).
Once there are no more elements smaller than or equal topivot, the element in the
last computedstoreis swapped with the rightmost element, thus safely placing
thepivot in place.
Afterpartition(0,15,9)executes and returns the locationp=5 of thepivotvalue,
you can see thatA[left,p) are all less than or equal topivot, whereasA[p+1,right]
Example 4-3. C implementation to partition ar[left,right] around a given pivot
element
/**
- In linear time, group the subarray ar[left, right] around a pivot
- element pivot=ar[pivotIndex] by storing pivot into its proper
- location, store, within the subarray (whose location is returned
- by this function) and ensuring that all ar[left,store) <= pivot and
- all ar[store+1,right] > pivot.
*/
int partition (void *ar, int(cmp)(const void ,const void ),
int left, int right, int pivotIndex) {
int idx, store;
void pivot = ar[pivotIndex];
/ move pivot to the end of the array /
void tmp = ar[right];
ar[right] = ar[pivotIndex];
ar[pivotIndex] = tmp;
/* all values <= pivot are moved to front of array and pivot inserted - just after them. */
store = left;
for (idx = left; idx < right; idx++) {
if (cmp(ar[idx], pivot) <= 0) {
tmp = ar[idx];
ar[idx] = ar[store];
ar[store] = tmp;
store++;
}
}
tmp = ar[right];
ar[right] = ar[store];
ar[store] = tmp;
return store;
}
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use