Sorting/PointerBased/revisedPartition_baseQsort.c File Reference

Base implementation of Quicksort with leftmost pivot selection and all subcases sorted by do_qsort. Straight Quicksort implementation with no optimizations. More...

#include "report.h"

Functions

int partition (void **ar, int(*cmp)(const void *, const void *), int left, int right)
 In linear time, group the sub-array ar[left, right) around a pivot element pivot=ar[pivotIndex] by storing pivot into its proper location, store, within the sub-array (whose location is returned by this function) and ensuring that all ar[left,store) <= pivot and all ar[store+1,right) > pivot.
void insertion (void **ar, int(*cmp)(const void *, const void *), int low, int high)
 proper insertion sort, optimized
void selectionSort (void **ar, int(*cmp)(const void *, const void *), int low, int high)
 To show worse performance, consider using selectionSort instead of InsertionSort!
void do_qsort (void **ar, int(*cmp)(const void *, const void *), int left, int right)
 Sort array ar[left,right] using Quicksort method.
void sortPointers (void **vals, int total_elems, int(*cmp)(const void *, const void *))
 invoke qsort.

Variables

int minSize
 Problem size below which to use insertion sort.


Detailed Description

Base implementation of Quicksort with leftmost pivot selection and all subcases sorted by do_qsort. Straight Quicksort implementation with no optimizations.

Author:
George Heineman
Date:
6/15/08

Function Documentation

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

Sort array ar[left,right] using Quicksort method.

The comparison function, cmp, is needed to properly compare elements.

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

proper insertion sort, optimized

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

In linear time, group the sub-array ar[left, right) around a pivot element pivot=ar[pivotIndex] by storing pivot into its proper location, store, within the sub-array (whose location is returned by this function) and ensuring that all ar[left,store) <= pivot and all ar[store+1,right) > pivot.

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)
Returns:
location of the pivot index properly positioned.

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

To show worse performance, consider using selectionSort instead of InsertionSort!

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

invoke qsort.


Variable Documentation

int minSize

Problem size below which to use insertion sort.

Algorithm Development Kit 1.0