Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
for working with vectors More...
Functions | |
template<class T > | |
int64_t | binary_search (std::vector< T > &arr, T val, int64_t low, int64_t high) |
Binary search function to find the most suitable pace for an element. | |
template<typename T > | |
void | insertionSort_binsrch (std::vector< T > &arr) |
Insertion sort function to sort the vector. | |
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. | |
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 | |
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 | |
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 | |
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 | |
template<std::size_t N> | |
std::array< int, N > | pigeonSort (std::array< int, N > arr) |
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 | recursive_bubble_sort (std::vector< T > *nums, uint64_t n) |
This is an implementation of the recursive_bubble_sort. A vector is passed to the function which is then dereferenced, so that the changes are reflected in the original vector. It also accepts a second parameter of type int and name n , which is the size of the array. | |
std::vector< uint64_t > | selectionSort (const std::vector< uint64_t > &arr, uint64_t len) |
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) |
for working with vectors
for io operations
for std::is_sorted
for returning multiple values form a function at once
Sorting Algorithms.
for std::vector
Sorting algorithms.
for algorithm functions for assert for IO operations
Sorting algorithms
for assert for typedef datatype uint64_t for IO operations
Sorting algorithms
for std::is_sorted, std::swap for assert for io operations
Sorting algorithms
for std::is_sorted for assert for std::swap and io operations
@breif Sorting algorithms
Sorting algorithms
for std::is_sorted for std::assert for std::time for IO operations
Sorting algorithms
header files for collection of functions for a macro called assert which can be used to verify assumptions for io operations
Sorting algorithms
for std::is_sorted(), std::swap() for std::array for assert for initializing random number generator for IO operations
Sorting algorithms
for assert for IO operations for std::vector for std::array
Sorting algorithms
for std::is_sorted for std::assert for IO operations
for std::is_sorted for assert for std::swap and io operations
Sorting algorithms
for std::is_sorted, std::swap for assert for IO operations
Sorting algorithms
int64_t sorting::binary_search | ( | std::vector< T > & | arr, |
T | val, | ||
int64_t | low, | ||
int64_t | high ) |
Binary search function to find the most suitable pace for an element.
T | The generic data type. |
arr | The actual vector in which we are searching a suitable place for the element. |
val | The value for which suitable place is to be found. |
low | The lower bound of the range we are searching in. |
high | The upper bound of the range we are searching in. |
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 ) |
Insertion Sort Function.
T | type of array |
[in,out] | arr | Array to be sorted |
n | Size of Array |
void sorting::insertionSort_binsrch | ( | std::vector< T > & | arr | ) |
Insertion sort function to sort the vector.
T | The generic data type. |
arr | The actual vector to sort. |
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 |
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 | ( | 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::recursive_bubble_sort | ( | std::vector< T > * | nums, |
uint64_t | n ) |
This is an implementation of the recursive_bubble_sort. A vector is passed to the function which is then dereferenced, so that the changes are reflected in the original vector. It also accepts a second parameter of type int
and name n
, which is the size of the array.
T | type of data variables in the array |
nums | our array of elements. |
n | size of the array |
< base case; when size of the array is 1
< iterating over the entire array
< if a larger number appears before the smaller one, swap them.
std::vector< uint64_t > sorting::selectionSort | ( | const std::vector< uint64_t > & | arr, |
uint64_t | len ) |
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 |