Sorting::detail Namespace Reference

This is a namespace with some under the hood functions. More...

Functions
void	maxHeapify (std::vector< double > &array, size_t heap_size, size_t current_index)
	Converts an array to have the heap property. More...
std::vector< double >	buildMaxHeap (const std::vector< double > &input)
	Build a heap-like array for sorting via Heap sort. More...
void	merge (std::vector< double > &input, size_t p, size_t q, size_t r)
	The helper function that performs the actual merge of mergesort. More...
void	mergeSort (std::vector< double > &input, size_t start_index, size_t end_index)
	A helper function for merge sort that divides the problem. More...
size_t	quickPartition (std::vector< double > &input, size_t start_index, size_t end_index)
	Perform the partition operation for quick sort. More...
void	quickSort (std::vector< double > &input, size_t start_index, size_t end_index)
	A helper function for the quicksort divide and conquer. More...
std::vector< unsigned int >	radixCountSort (const std::vector< unsigned int > &input, unsigned int digit)
	A modified counting sort that operates on a single digit for each number. More...

Detailed Description

This is a namespace with some under the hood functions.

These should generally not be called by the user unless you are very sure what you are doing and have a very good reason for doing so.

Function Documentation

buildMaxHeap()

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

inline

Build a heap-like array for sorting via Heap sort.

This puts the array in such an order that its heap property is maintained. It does this by inserting elements and calling maxHeapify to ensure compliance with the heap property.

Parameters

input

The array to heapify.

Returns

The array in heap structure.

maxHeapify()

void Sorting::detail::maxHeapify ( std::vector< double > &  array, size_t  heap_size, size_t  current_index  )

inline

Converts an array to have the heap property.

This recursively ensures that a given vector satisfies the heap property with the first, root element being the maximum. This is called recursively and assumes that all elements lower than lowest_index already meet the heap property. It takes the target index and moves it into the correct spot down the array to maintain the heap property.

Parameters

array	The array to make into a heap.
heap_size	The maximum element that is considered part of the heap.
current_index	The current index to consider. It assumes all larger then this are already in heap order.

merge()

void Sorting::detail::merge ( std::vector< double > &  input, size_t  p, size_t  q, size_t  r  )

inline

The helper function that performs the actual merge of mergesort.

This creates the two stacks, which are already in sorted order, and pops whichever value off the top is smaller. This leads to a single array that is completely sorted.

Parameters

input	The array to sort. This will be operated on in-place.
p	The smallest index to include in the sort.
q	The midpoint of the sorting selection. It is assumed that and values from [p, q] are already sorted as well as all values from [q+1, r].
r	The largest index to include in the sort.

mergeSort()

void Sorting::detail::mergeSort ( std::vector< double > &  input, size_t  start_index, size_t  end_index  )

inline

A helper function for merge sort that divides the problem.

This method recursively divides up the array into half. Eventually, the problem is broken down into individual elements, which are by definition sorted. This then uses merge to combine the elements back together in sorted order.

Parameters

input	The vector to operate on. This will be modified in place.
start_index	The smallest index to consider in sorting.
end_index	The largest index to consider in sorting.

quickPartition()

size_t Sorting::detail::quickPartition ( std::vector< double > &  input, size_t  start_index, size_t  end_index  )

inline

Perform the partition operation for quick sort.

This function takes the last value in the supplied range and uses it as a pivot. It then walks through the array and ensures that each value less then the pivot is on the left and greater than on the right. It will then put the pivot in the middle of the array.

Parameters

input	The array to partition.
start_index	The first index to include in the partition.
end_index	The last index to include in the partition.

Returns

The index around which the array is partitioned.

quickSort()

void Sorting::detail::quickSort ( std::vector< double > &  input, size_t  start_index, size_t  end_index  )

inline

A helper function for the quicksort divide and conquer.

This part partitions each array, then calls itself for each partition.

Parameters

input	The array to sort.
start_index	The first index to include in the sort.
end_index	The last index to include in the sort. @

radixCountSort()

std::vector<unsigned int> Sorting::detail::radixCountSort ( const std::vector< unsigned int > &  input, unsigned int  digit  )

inline

A modified counting sort that operates on a single digit for each number.

This uses the same algorithm as countingSort, but only compares a single digit for each number, rather than the whole number. Because of that, it only needs to allocate 10 spaces for the count.

Parameters

input	The vector to sort.
digit	The digit index to sort on. 0 = ones place, 1 = tens place, etc.

Returns

The array sorted on the select digit.