Sorting/PointerBased/selectKthRecursive.c File Reference

Recursive implementation to select the kth element of ar[left, right]

A recursive implementation to select the kth smallest element from the subarray ar[left, right]. More...


Functions

int selectPivotIndex (void **vals, int left, int right)
 Code to select a pivot index around which to partition ar[left, right].
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].
int selectKth (void **ar, int(*cmp)(const void *, const void *), int k, int left, int right)
 Externally provided method to select Kth element from subarray.


Detailed Description

Recursive implementation to select the kth element of ar[left, right]

A recursive implementation to select the kth smallest element from the subarray ar[left, right].

Author:
George Heineman
Date:
6/15/08

Function Documentation

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 selectKth ( void **  ar,
int(*)(const void *, const void *)  cmp,
int  k,
int  left,
int  right 
)

Externally provided method to select Kth element from subarray.

Note 1 <= k <= right-left+1. The comparison function, cmp, is needed to properly compare elements. Worst-case is quadratic, O(n^2).

int selectPivotIndex ( void **  vals,
int  left,
int  right 
)

Code to select a pivot index around which to partition ar[left, right].

Select a random index from [left,right].

Parameters:
vals the array of elements.
left the left end of the subarray range
right the right end of the subarray range
Returns:
int in the range [left, right] to use in partition.

This really needs to have the comparison method passed in! But I don't want to change the interface, so this will suffice in the short term since all we have are strings in the example.

Algorithm Development Kit 1.0