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. |
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.
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].
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. |
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].
vals | the array of elements. | |
left | the left end of the subarray range | |
right | the right end of the subarray range |
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 | |||
) |
int minSize |
Problem size below which to use insertion sort.
Algorithm Development Kit 1.0