Implementation that uses dot.h interface to produce on stdout the DOT commands for a QuickSort execution. More...
#include <stdio.h>
#include <malloc.h>
#include "dot.h"
Functions | |
| int | selectPivotIndex (long *vals, int left, int right) |
| Code to select the pivot index is found elsewhere. | |
| int | partition (long *ar, int(*cmp)(const long, const long), int left, int right, int pivotIndex) |
| 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 (long *ar, int(*cmp)(const long, const long), int low, int high) |
| proper insertion sort, optimized | |
| void | selectionSort (long **ar, int(*cmp)(const void *, const void *), int low, int high) |
| perform a selection sort. | |
| void | do_qsort (int id, long *ar, int(*cmp)(const long, const long), int left, int right) |
| Sort array ar[left,right] using QuickSort method. | |
Variables | |
| int | minSize |
| Problem size below which to use insertion sort. | |
Implementation that uses dot.h interface to produce on stdout the DOT commands for a QuickSort execution.
This code is not intended to be used for sorting. Rather, it generates DOTTY output that shows the behavior of QuickSort. You have been warned.
| void do_qsort | ( | int | id, | |
| long * | ar, | |||
| int(*)(const long, const long) | 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 | ( | long * | ar, | |
| int(*)(const long, const long) | cmp, | |||
| int | low, | |||
| int | high | |||
| ) |
proper insertion sort, optimized
| int partition | ( | long * | ar, | |
| int(*)(const long, const long) | cmp, | |||
| int | left, | |||
| int | right, | |||
| int | pivotIndex | |||
| ) |
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.
| ar | array of values | |
| cmp | comparison function to use | |
| left | lower bound index position (inclusive) | |
| right | upper bound index position (exclusive) | |
| pivotIndex | index around which the partition is being made. |
| void selectionSort | ( | long ** | ar, | |
| int(*)(const void *, const void *) | cmp, | |||
| int | low, | |||
| int | high | |||
| ) |
perform a selection sort.
| int selectPivotIndex | ( | long * | vals, | |
| int | left, | |||
| int | right | |||
| ) |
Code to select the pivot index is found elsewhere.
| int minSize |
Problem size below which to use insertion sort.
Algorithm Development Kit 1.0