Sorting/PointerBased/baseQsort.c File Reference

Quicksort implementation

Complete Quicksort implementation optimized to switch to Insertion Sort when problem sizes are less than or equal to minSize in length. More...

#include <sys/types.h>
#include "report.h"

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 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)
 proper insertion sort, optimized
void selectionSort (void **ar, int(*cmp)(const void *, const void *), int low, int high)
 Implement SelectionSort if one wants to see timing difference if this is used instead of Insertion Sort.
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 *))
 Sort by using Quicksort.

Variables

int minSize
 Problem size below which to use insertion sort.


Detailed Description

Quicksort implementation

Complete Quicksort implementation optimized to switch to Insertion Sort when problem sizes are less than or equal to minSize in length.

For pure QuickSort, set minSize to 0.

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

Implement SelectionSort if one wants to see timing difference if this is used instead of Insertion Sort.

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.

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

Sort by using Quicksort.


Variable Documentation

int minSize

Problem size below which to use insertion sort.

Algorithm Development Kit 1.0