Sorting/PointerBased/selectKthWorstLinearFive.c File Reference

Optimized implementation of BFPRT with groupingSize=5 to select kth smallest from an array in worst-case linear time. A recursive implementation of BFPRT to select the kth smallest element within ar[left, right] in worst-case linear time. Customized to group the elements in groups of 5. More...


Functions

int partition (void **ar, int(*cmp)(const void *, const void *), int left, int right, int idx)
 Partition ar[left, right] around the value stored in ar[idx].
static void _insertion (void **ar, int(*cmp)(const void *, const void *), int low, int right, int gap)
 specialized insertion sort up to five elements with spaced gap.
static int medianOfMedians (void **ar, int(*cmp)(const void *, const void *), int left, int right, int gap)
 Find suitable pivotIndex to use for ar[left,right] with closed bound on both sides.
int selectMedian (void **ar, int(*cmp)(const void *, const void *), int left, int right)
 Provided externally for selecting median as based on BFPRT algorithm.


Detailed Description

Optimized implementation of BFPRT with groupingSize=5 to select kth smallest from an array in worst-case linear time. A recursive implementation of BFPRT to select the kth smallest element within ar[left, right] in worst-case linear time. Customized to group the elements in groups of 5.

Author:
George Heineman
Date:
6/15/08

Function Documentation

static void _insertion ( void **  ar,
int(*)(const void *, const void *)  cmp,
int  low,
int  right,
int  gap 
) [static]

specialized insertion sort up to five elements with spaced gap.

static int medianOfMedians ( void **  ar,
int(*)(const void *, const void *)  cmp,
int  left,
int  right,
int  gap 
) [static]

Find suitable pivotIndex to use for ar[left,right] with closed bound on both sides.

1. Divide the elements into floor(n/4) groups of 4 elements and use _insertion on each group 2. Pick median from each sorted groups (3rd element). 3. Use select recursively to find median x of floor(n/4) medians found in step 2. This is known as the median-of-medians.

int partition ( void **  ar,
int(*)(const void *, const void *)  cmp,
int  left,
int  right,
int  pivotIndex 
)

Partition ar[left, right] around the value stored in ar[idx].

Parameters:
ar contents of array
cmp comparison function
left lower bound index position (inclusive)
right upper bound index position (inclusive)
pivotIndex index around which the partition is being made.
Returns:
location of the pivot index properly positioned.

int selectMedian ( void **  ar,
int(*)(const void *, const void *)  cmp,
int  left,
int  right 
)

Provided externally for selecting median as based on BFPRT algorithm.

The comparison function, cmp, is needed to compare elements.

Partition input array around the median of medians x. If kth largest is found, return absolute index; otherwise narrow to find kth smallest in A[left,pivotIndex-1] or (k-p)-th in A[pivotIndex+1,right].

Algorithm Development Kit 1.0