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. | |
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.
| 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 | |||
| ) |
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].
| 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 | |||
| ) |
Sort by using Quicksort.
| int minSize |
Problem size below which to use insertion sort.
Algorithm Development Kit 1.0