Sorting/PointerBased/invertedInsertionQsort.c File Reference

Novel variation of Quicksort (which fails badly)

Variation to Quicksort (which fails badly) which considers just using the base Quicksort cases to partition the relevant subarrays, without actually sorting the smaller cases. More...

#include "report.h"

Functions

int selectPivotIndex (void **vals, int left, int right)
 Determined elsewhere.
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)
 Actual SelectionSort implementation, provided as counterpoint to 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 *))

Variables

int minSize
 Problem size below which to use insertion sort.


Detailed Description

Novel variation of Quicksort (which fails badly)

Variation to Quicksort (which fails badly) which considers just using the base Quicksort cases to partition the relevant subarrays, without actually sorting the smaller cases.

Then, once the entire array is partitioned, perform an Insertion Sort over the entire array.

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 
)

Actual SelectionSort implementation, provided as counterpoint to Insertion Sort.

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

Determined elsewhere.

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 
)


Variable Documentation

int minSize

Problem size below which to use insertion sort.

Algorithm Development Kit 1.0