Sorting/PointerBased/medianMinSort.c File Reference

Contains Median Sort implementation with Min Size optimization

Contains Median Sort implementation that switches to Insertion Sort when the problem size is small enough. More...

#include "report.h"

Functions

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.
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 insertion (void **ar, int(*cmp)(const void *, const void *), int low, int high)
 Perform insertion sort over the given subarray.
void selectionSort (void **ar, int(*cmp)(const void *, const void *), int low, int high)
 By contrast, perform Selection Sort over subarray.
void mediansort (void **ar, int(*cmp)(const void *, const void *), int left, int right)
 Sort using medianSort method.
void sortPointers (void **vals, int total_elems, int(*cmp)(const void *, const void *))
 Sort the pointers via median sort.

Variables

int minSize
 Minimum size beyond which to use Insertion Sort.


Detailed Description

Contains Median Sort implementation with Min Size optimization

Contains Median Sort implementation that switches to Insertion Sort when the problem size is small enough.

Author:
George Heineman
Date:
6/15/08

Function Documentation

void insertion ( void **  ar,
int(*)(const void *, const void *)  cmp,
int  low,
int  high 
)

Perform insertion sort over the given subarray.

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 array of elements to be sorted.
cmp comparison function to order elements.
left lower bound index position (inclusive)
right upper bound index position (exclusive)
pivotIndex index around which the partition is being made.
Returns:
location of the pivot index properly positioned.

void selectionSort ( void **  ar,
int(*)(const void *, const void *)  cmp,
int  low,
int  high 
)

By contrast, perform Selection Sort over subarray.

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

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

Sort the pointers via median sort.


Variable Documentation

int minSize

Minimum size beyond which to use Insertion Sort.

Algorithm Development Kit 1.0