Sorting/PointerBased/selectKthWorstLinear.c File Reference

Generic implementation of BFPRT 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. 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 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.

Variables

int groupingSize
 The size of the grouping is determined elsewhere.


Detailed Description

Generic implementation of BFPRT 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.

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 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/size) groups of size elements and use _insertion on each group 2. Pick median from each sorted groups (size/2 element). 3. Use select recursively to find median x of floor(n/size) 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].


Variable Documentation

int groupingSize

The size of the grouping is determined elsewhere.

Algorithm Development Kit 1.0