Sorting/Longs/dot_baseQsort.c File Reference

Generate QuickSort DOT graph

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.


Detailed Description

Generate QuickSort DOT graph

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.

Author:
George Heineman
Date:
6/15/08

Function Documentation

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.

Parameters:
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.
Returns:
location of the pivot index properly positioned.

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.


Variable Documentation

int minSize

Problem size below which to use insertion sort.

Algorithm Development Kit 1.0