Sorting Namespace Reference

A collection of sorting algorithms discussed in class. More...

Namespaces
	detail
	This is a namespace with some under the hood functions.

Functions
std::vector< double >	insertionSort (const std::vector< double > &input)
	Perform sort via insertion. More...
std::vector< double >	mergeSort (const std::vector< double > &input)
	Perform sorting via merge sort. More...
std::vector< double >	heapSort (const std::vector< double > &input)
	Perform sorting via heap sort. More...
std::vector< double >	quickSort (const std::vector< double > &input)
	Perform sorting via quicksort. More...
std::vector< uint8_t >	countingSort (const std::vector< uint8_t > &input)
	Perform sorting via counting sort. More...
std::vector< unsigned int >	radixSort (const std::vector< unsigned int > &input)
	Perform sorting via radix sort. More...
std::vector< double >	bucketSort (const std::vector< double > &input)
	Perform sorting via bucket sort. More...

Detailed Description

A collection of sorting algorithms discussed in class.

This includes the following algorithms and the types of inputs the handle (stored within std::vector):

algorithm	input type
insertion	double
merge	double
heap	double
quick	double
counting	uint8_t
radix	unsigned int
bucket	double in the range [0, 1)

Function Documentation

bucketSort()

std::vector<double> Sorting::bucketSort ( const std::vector< double > &  input )

inline

Perform sorting via bucket sort.

This algorithm divides the valid range for the sort into n uniform buckets. It then places each number into the appropriate bucket. These buckets are then sorted via insertion sort. The buckets are then reassembled. Because the buckets contain only a few items, the insertion sort is fast.

Note

This can be expanded to any nonnegative value by normalizing the values when placing into buckets. However, this will stick with the method shown in the book.

Parameters

input

A vector of unsorted numbers in the range [0, 1).

Returns

Those numbers sorted from smallest to largest.

Exceptions

std::out_of_range

Thrown if a number is outside the range [0, 1)

countingSort()

std::vector<uint8_t> Sorting::countingSort ( const std::vector< uint8_t > &  input )

inline

Perform sorting via counting sort.

This method assumes the input is all nonnegative integers. It sorts by counting up the number of instances of each possible integer and using that to determine where that integer should be placed within the ouput array.

Parameters

input

A vector of unsorted integers >= 0.

Returns

Those numbers sorted from smallest to largest.

heapSort()

std::vector<double> Sorting::heapSort ( const std::vector< double > &  input )

inline

Perform sorting via heap sort.

This method builds a heap out of the data then reads it in printed order. The heap is a max heap, meaning each element is greater than its parents. Therefore, it is easy to traverse to get an ordered array. Various subfunctions ensure that the heap property is maintained. Unlike mergeSort, this sorts in place.

Parameters

input

A vector of numbers in any order.

Returns

Those numbers sorted from smallest to largest.

insertionSort()

std::vector<double> Sorting::insertionSort ( const std::vector< double > &  input )

inline

Perform sort via insertion.

This is the simplist code, but also the most costly in terms of performance. It does operate in place though, so there are only fixed memory costs.

Parameters

input

The unsorted array.

Returns

The provided array, sorted from least to greatest.

mergeSort()

std::vector<double> Sorting::mergeSort ( const std::vector< double > &  input )

inline

Perform sorting via merge sort.

This method is faster than insertion sort, but does take up additional memory, due to the temporary arrays created.

Parameters

input

A vector of numbers in any order.

Returns

Those numbers sorted from smallest to largest.

quickSort()

std::vector<double> Sorting::quickSort ( const std::vector< double > &  input )

inline

Perform sorting via quicksort.

This method uses quicksort, which recursively partitions the data into halves that are greater or less than a selected pivot value. Eventually, the halves are small enough that they are automatically sorted. This is the same asymptotic complexity as some oft the other algorithms, but often performs faster. There is a randomized version that avoids the worst case. This is not that version.

Parameters

input

A vector of unsorted numbers.

Returns

Those numbers sorted from smallest to largest.

radixSort()

std::vector<unsigned int> Sorting::radixSort ( const std::vector< unsigned int > &  input )

inline

Perform sorting via radix sort.

This uses a radix sort to sort on each digit from least to most significant digit. It then uses a modified counting sort algorithm under the hood for the actual sort.

Parameters

input

A vector of unsorted integers >= 0.

Returns

Those numbers sorted from smallest to largest.