Sorting/PointerBased/medianSort.c File Reference

Contains Median Sort implementation

Contains Median Sort implementation. More...

#include "report.h"

Functions

int selectKth (void **vals, int(*cmp)(const void *, const void *), int k, int left, int right)
 Externally provided method to select Kth element from subarray.
int selectMedian (void **ar, int(*cmp)(const void *, const void *), int left, int right)
 Code to select median is externally provided.
int partition (void **ar, int(*cmp)(const void *, const void *), int left, int right, int pivotIndex)
 Partition ar[left, right] around the value stored in ar[idx].
void mediansort (void **ar, int(*cmp)(const void *, const void *), int left, int right)
 Sort using mediansort method.
void sortPointers (void **vals, int n, int(*cmp)(const void *, const void *))
 Apply median sort.


Detailed Description

Contains Median Sort implementation

Contains Median Sort implementation.

If compiled with -DMEDIAN set, then this relies on a selectMedian externally provided function to select the median; otherwise, it falls back on using an externally provided selectKth.

Author:
George Heineman
Date:
6/15/08

Function Documentation

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

Sort using mediansort method.

Parameters:
ar array of elements to be sorted.
cmp comparison function to order elements.
left The left-bounds within which to sort (0 <= left < ar.length)
right The right-bounds within which to sort (0 <= right < ar.length)

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

Code to select median is externally provided.

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].

void sortPointers ( void **  vals,
int  n,
int(*)(const void *, const void *)  cmp 
)

Apply median sort.

Algorithm Development Kit 1.0