Sorting/PointerBased/selectKthWorstLinearThree.c File Reference

Optimized implementation of BFPRT with groupingSize=3 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 3. More...


Defines

#define SWAP(a, p1, p2, type)
 Macro to swap two elements in the array.

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 medianOfThree (void **ar, int left, int gap, int(*cmp)(const void *, const void *))
 determine median of three elements in array ar[left], ar[left+gap], ar[left+gap*2] and ensure that ar[left+gap] contains thie median value once done.
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=3 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 3.

Author:
George Heineman
Date:
6/15/08

Define Documentation

#define SWAP ( a,
p1,
p2,
type   ) 

Value:

{ \
    type _tmp__ = a[p1];     \
    a[p1] = a[p2];           \
    a[p2] = _tmp__;          \
  }
Macro to swap two elements in the array.


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.

Goal is to consider groups of size b. In this code, b=3. In the original BFPRT algorithm b=5.

1. Divide the elements into floor(n/b) groups of b elements and find median value of each of these groups. Consider this set of all medians to be the set M.

2. If |M| > b, then recursively apply until <=b groups are left

3. In the base case of the recursion, simply use INSERTION SORT to sort remaining <=b median values and choose the median of this sorted set.

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

determine median of three elements in array ar[left], ar[left+gap], ar[left+gap*2] and ensure that ar[left+gap] contains thie median value once done.

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