Algorithms_in_C++
1.0.0
Set of algorithms implemented in C++.
|
Sorting algorithms. More...
Functions | |
template<typename T , size_t N> | |
std::array< T, N > | shuffle (std::array< T, N > arr) |
template<typename T , size_t N> | |
std::array< T, N > | randomized_bogosort (std::array< T, N > arr) |
template<typename T > | |
void | gnomeSort (T *arr, int size) |
template<typename T , size_t size> | |
std::array< T, size > | gnomeSort (std::array< T, size > arr) |
template<typename T > | |
void | insertionSort (T *arr, int n) |
Insertion Sort Function. More... | |
template<typename T > | |
void | insertionSort (std::vector< T > *arr) |
template<class Iterator > | |
void | merge (Iterator l, Iterator r, const Iterator e, char b[]) |
merges 2 sorted adjacent segments into a larger sorted segment More... | |
template<class Iterator > | |
void | non_recursive_merge_sort (const Iterator first, const Iterator last, const size_t n) |
bottom-up merge sort which sorts elements in a non-decreasing order More... | |
template<class Iterator > | |
void | non_recursive_merge_sort (const Iterator first, const size_t n) |
bottom-up merge sort which sorts elements in a non-decreasing order More... | |
template<class Iterator > | |
void | non_recursive_merge_sort (const Iterator first, const Iterator last) |
bottom-up merge sort which sorts elements in a non-decreasing order More... | |
template<std::size_t N> | |
std::array< int, N > | pigeonSort (std::array< int, N > arr) |
int | partition (int arr[], int low, int high) |
void | quickSort (int arr[], int low, int high) |
template<typename T > | |
void | quicksort (std::vector< T > *arr, int32_t low, int32_t high) |
template<typename T > | |
std::vector< T > | quicksort (std::vector< T > arr, int32_t low, int32_t high) |
template<typename T > | |
void | shell_sort (T *arr, size_t LEN) |
template<typename T , size_t N> | |
void | shell_sort (T(&arr)[N]) |
template<typename T > | |
void | shell_sort (std::vector< T > *arr) |
Sorting algorithms.
Sorting Algorithms.
Sorting algorithms
std::array<T, size> sorting::gnomeSort | ( | std::array< T, size > | arr | ) |
This implementation is for a C++-style array input. The function argument is a pass-by-value and hence a copy of the array gets created which is then modified by the function and returned.
T | type of data variables in the array |
size | size of the array |
[in] | arr | our array of elements. |
void sorting::gnomeSort | ( | T * | arr, |
int | size | ||
) |
This implementation is for a C-style array input that gets modified in place.
[in,out] | arr | our array of elements. |
size | size of given array |
void sorting::insertionSort | ( | std::vector< T > * | arr | ) |
Insertion Sort Function
T | type of array |
[in,out] | arr | pointer to array to be sorted |
void sorting::insertionSort | ( | T * | arr, |
int | n | ||
) |
void sorting::merge | ( | Iterator | l, |
Iterator | r, | ||
const Iterator | e, | ||
char | b[] | ||
) |
merges 2 sorted adjacent segments into a larger sorted segment
best-case = worst-case = O(n)
l | points to the left part |
r | points to the right part, end of left part |
e | points to end of right part |
b | points at the buffer |
void sorting::non_recursive_merge_sort | ( | const Iterator | first, |
const Iterator | last | ||
) |
bottom-up merge sort which sorts elements in a non-decreasing order
first | points to the first element |
last | points to 1-step past the last element |
void sorting::non_recursive_merge_sort | ( | const Iterator | first, |
const Iterator | last, | ||
const size_t | n | ||
) |
bottom-up merge sort which sorts elements in a non-decreasing order
sorts elements non-recursively by breaking them into small segments, merging adjacent segments into larger sorted segments, then increasing the sizes of segments by factors of 2 and repeating the same process. best-case = worst-case = O(n log(n))
first | points to the first element |
last | points to 1-step past the last element |
n | the number of elements |
void sorting::non_recursive_merge_sort | ( | const Iterator | first, |
const size_t | n | ||
) |
bottom-up merge sort which sorts elements in a non-decreasing order
first | points to the first element |
n | the number of elements |
int sorting::partition | ( | int | arr[], |
int | low, | ||
int | high | ||
) |
This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot
std::array<int, N> sorting::pigeonSort | ( | std::array< int, N > | arr | ) |
Pigeonhole sorting of array of size n The function will sort the array through Pigeonhole algorithm and print
arr | unsorted array of elements |
void sorting::quickSort | ( | int | arr[], |
int | low, | ||
int | high | ||
) |
void sorting::quicksort | ( | std::vector< T > * | arr, |
int32_t | low, | ||
int32_t | high | ||
) |
3-way partition based quick sort. This function accepts array pointer and modified the input array.
T | type of data in the vector array |
[in,out] | arr | vector array to sort |
[in] | low | lower limit of window to partition |
[in] | high | upper limit of window to partition |
std::vector<T> sorting::quicksort | ( | std::vector< T > | arr, |
int32_t | low, | ||
int32_t | high | ||
) |
3-way partition based quick sort. This function accepts array by value and creates a copy of it. The array copy gets sorted and returned by the function.
T | type of data in the vector array |
[in] | arr | vector array to sort |
[in] | low | lower limit of window to partition |
[in] | high | upper limit of window to partition |
std::array<T, N> sorting::randomized_bogosort | ( | std::array< T, N > | arr | ) |
Implement randomized Bogosort algorithm and sort the elements of a given array.
T | typename of the array |
N | length of array |
arr | array to sort |
void sorting::shell_sort | ( | std::vector< T > * | arr | ) |
function overload - when input array is of type std::vector, simply send the data content and the data length to the above function.
void sorting::shell_sort | ( | T * | arr, |
size_t | LEN | ||
) |
Optimized algorithm - takes half the time by utilizing Mar
void sorting::shell_sort | ( | T(&) | arr[N] | ) |
function overload - when input array is of a known length array type
std::array<T, N> sorting::shuffle | ( | std::array< T, N > | arr | ) |
Function to shuffle the elements of an array. (for reference)
T | typename of the array |
N | length of array |
arr | array to shuffle |