sorting Namespace Reference

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)
	Insertion Sort for a vector.
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)
int	partition (std::vector< int > &arr, int start, int end)
	The partition function sorts the array from start to end and uses the last element as the pivot.
void	iterativeQuickSort (std::vector< int > &arr)
	The main sorting function.
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)

Detailed Description

for working with vectors

for io operations

for returning multiple values form a function at once

header files

Sorting Algorithms.

for std::assert

for using std::vector

for assert

for std::vector

Sorting algorithms.

for algorithm functions for assert for IO operations

Sorting algorithms

for std::is_sorted for assert for IO implementations for std::string for std::pair, std::swap for std::vector, std::vector::push_back, std::vector::size

for assert for typedef datatype uint64_t for IO operations

Sorting algorithms

for std::is_sorted, std::swap for io operations for std::vector

Sorting algorithms

for std::is_sorted for std::swap and io operations for std::vector

@breif Sorting algorithms

Sorting algorithms

for std::is_sorted for assert function in testing for std::cout and std::endl

Contains sorting algorithms

for std::is_sorted for std::time for IO operations for std::vector

Sorting algorithms

for std::cout for std::vector for std::stack for std::is_sorted for assert

for collection of functions for a macro called assert which can be used to verify assumptions for io operations for std::vector

Sorting algorithms

for std::is_sorted(), std::swap() for std::array for assert for initializing random number generator for IO operations

Sorting algorithms

for std::is_sorted for std::array for IO operations for std::vector

Sorting algorithms

for std::is_sorted for IO operations for std::vector

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

Function Documentation

binary_search()

template<class T >

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.

Template Parameters

T	The generic data type.

Parameters

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.

Returns

the index of most suitable position of val.

Definition at line 63 of file binary_insertion_sort.cpp.

                                                                           {
    if (high <= low) {
        return (val > arr[low]) ? (low + 1) : low;
    }
    int64_t mid = low + (high - low) / 2;
    if (arr[mid] > val) {
        return binary_search(arr, val, low, mid - 1);
    } else if (arr[mid] < val) {
        return binary_search(arr, val, mid + 1, high);
    } else {
        return mid + 1;
    }
}

gnomeSort() [1/2]

template<typename T , size_t size>

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.

Template Parameters

T	type of data variables in the array
size	size of the array

Parameters

[in]

arr

our array of elements.

Returns

array with elements sorted

Definition at line 62 of file gnome_sort.cpp.

                                                   {
    // few easy cases
    if (size <= 1) {
        return arr;
    }
 
    int index = 0;  // initialize loop index
    while (index < size) {
        // check for swap
        if ((index == 0) || (arr[index] >= arr[index - 1])) {
            index++;
        } else {
            std::swap(arr[index], arr[index - 1]);  // swap
            index--;
        }
    }
    return arr;
}

gnomeSort() [2/2]

template<typename T >

void sorting::gnomeSort	(	T *	arr,
		int	size )

This implementation is for a C-style array input that gets modified in place.

Parameters

[in,out]	arr	our array of elements.
	size	size of given array

Definition at line 34 of file gnome_sort.cpp.

                                 {
    // few easy cases
    if (size <= 1) {
        return;
    }
 
    int index = 0;  // initialize some variables.
    while (index < size) {
        // check for swap
        if ((index == 0) || (arr[index] >= arr[index - 1])) {
            index++;
        } else {
            std::swap(arr[index], arr[index - 1]);  // swap
            index--;
        }
    }
}

insertionSort() [1/2]

template<typename T >

void sorting::insertionSort

(

std::vector< T > *

arr

)

Insertion Sort for a vector.

Insertion Sort Function

Template Parameters

T	type of array

Parameters

[in,out]

arr

pointer to array to be sorted

Template Parameters

T	Type of the vector elements

Parameters

[in,out]

arr

Pointer to the vector to be sorted

Definition at line 77 of file insertion_sort.cpp.

                                      {
    size_t n = arr->size();
 
    for (size_t i = 1; i < n; i++) {
        T temp = arr[0][i];
        int32_t j = i - 1;
        while (j >= 0 && temp < arr[0][j]) {
            arr[0][j + 1] = arr[0][j];
            j--;
        }
        arr[0][j + 1] = temp;
    }
}

insertionSort() [2/2]

template<typename T >

void sorting::insertionSort	(	T *	arr,
		int	n )

Insertion Sort Function.

Template Parameters

T	type of array

Parameters

[in,out]	arr	Array to be sorted
	n	Size of Array

Template Parameters

T	Type of the array elements

Parameters

[in,out]	arr	Array to be sorted
	n	Size of the array

Definition at line 59 of file insertion_sort.cpp.

                                  {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int j = i - 1;
        while (j >= 0 && temp < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

insertionSort_binsrch()

template<typename T >

void sorting::insertionSort_binsrch

(

std::vector< T > &

arr

)

Insertion sort function to sort the vector.

Template Parameters

T	The generic data type.

Parameters

arr	The actual vector to sort.

Returns

Void.

Definition at line 84 of file binary_insertion_sort.cpp.

                                              {
    int64_t n = arr.size();
 
    for (int64_t i = 1; i < n; i++) {
        T key = arr[i];
        int64_t j = i - 1;
        int64_t loc = sorting::binary_search(arr, key, 0, j);
        while (j >= loc) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

iterativeQuickSort()

void sorting::iterativeQuickSort

(

std::vector< int > &

arr

)

The main sorting function.

The iterative quick sort uses the stack instead of recursion for saving and restoring the environment between calls. It does not need the end and start params, because it is not recursive.

Parameters

arr	array to be sorted

Returns

void

Definition at line 58 of file quick_sort_iterative.cpp.

{
    std::stack<int> stack;
    int start = 0;
    int end = arr.size()-1;
    stack.push(start);
    stack.push(end);
 
    while(!stack.empty())
    {
        end = stack.top();
        stack.pop();
        start = stack.top();
        stack.pop();
 
        int pivotIndex = partition(arr,start,end);
 
        if(pivotIndex -1 > start)
        {
            stack.push(start);
            stack.push(pivotIndex-1);
        }
 
        if(pivotIndex+1<end)
        {
            stack.push(pivotIndex+1);
            stack.push(end);
        }
    }
}

merge()

template<class Iterator >

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)

Parameters

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

Definition at line 57 of file non_recursive_merge_sort.cpp.

                                                               {
    // create 2 pointers to point at the buffer
    auto p(reinterpret_cast<std::remove_reference_t<decltype(*l)>*>(b)), c(p);
    // move the left part of the segment
    for (Iterator t(l); r != t; ++t) *p++ = std::move(*t);
    // while neither the buffer nor the right part has been exhausted
    // move the smallest element of the two back to the container
    while (e != r && c != p) *l++ = std::move(*r < *c ? *r++ : *c++);
    // notice only one of the two following loops will be executed
    // while the right part hasn't bee exhausted, move it back
    while (e != r) *l++ = std::move(*r++);
    // while the buffer hasn't bee exhausted, move it back
    while (c != p) *l++ = std::move(*c++);
}

non_recursive_merge_sort() [1/3]

template<class Iterator >

void sorting::non_recursive_merge_sort	(	const Iterator	first,
		const Iterator	last )

bottom-up merge sort which sorts elements in a non-decreasing order

Parameters

first	points to the first element
last	points to 1-step past the last element

Definition at line 86 of file non_recursive_merge_sort.cpp.

                                                                         {
    non_recursive_merge_sort(first, last, last - first);
}

non_recursive_merge_sort() [2/3]

template<class Iterator >

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))

Parameters

first	points to the first element
last	points to 1-step past the last element
n	the number of elements

Definition at line 25 of file non_recursive_merge_sort.cpp.

                                              {
    // create a buffer large enough to store all elements
    // dynamically allocated to comply with cpplint
    char* buffer = new char[n * sizeof(*first)];
    // buffer size can be optimized to largest power of 2 less than n
    // elements divide the container into equally-sized segments whose
    // length start at 1 and keeps increasing by factors of 2
    for (size_t length(1); length < n; length <<= 1) {
        // merge adjacent segments whose number is n / (length * 2)
        Iterator left(first);
        for (size_t counter(n / (length << 1)); counter; --counter) {
            Iterator right(left + length), end(right + length);
            merge(left, right, end, buffer);
            left = end;
        }
        // if the number of remaining elements (n * 2 % length) is longer
        // than a segment, merge the remaining elements
        if ((n & ((length << 1) - 1)) > length)
            merge(left, left + length, last, buffer);
    }
    delete[] buffer;
}

non_recursive_merge_sort() [3/3]

template<class Iterator >

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

Parameters

first	points to the first element
n	the number of elements

Definition at line 77 of file non_recursive_merge_sort.cpp.

                                                                    {
    non_recursive_merge_sort(first, first + n, n);
}

partition()

int sorting::partition	(	std::vector< int > &	arr,
		int	start,
		int	end )

The partition function sorts the array from start to end and uses the last element as the pivot.

Parameters

arr	the array to be sorted
start	starting index
end	ending index

Returns

int next index of the pivot

Definition at line 33 of file quick_sort_iterative.cpp.

{
    int pivot = arr[end];
    int index = start - 1;
 
    for (int j = start; j < end; j++) {
        if (arr[j] <= pivot) {
            std::swap(arr[++index], arr[j]);
        }
    }
 
    std::swap(arr[index + 1], arr[end]);
    return index + 1;
}

pigeonSort()

template<std::size_t N>

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

Parameters

arr	unsorted array of elements

Returns

sorted array of elements

Definition at line 34 of file pigeonhole_sort.cpp.

                                                  {
    // Finding min and max*
    auto min = std::min_element(std::begin(arr), std::end(arr));
    auto max = std::max_element(std::begin(arr), std::end(arr));
 
    // Range refers to the number of holes required
    int range = *max - *min + 1;
    int *hole = new int[range]();
 
    // Copying all array values to pigeonhole
    for (int i = 0; i < N; i++) {
        hole[arr[i] - *min] = arr[i];
    }
 
    // Deleting elements from list and storing to original array
    int count = 0;
    for (int i = 0; i < range; i++) {
        while (hole[i] != '\0') {
            arr[count] = hole[i];
            hole[i] = {};
            count++;
        }
    }
    delete[] hole;
 
    return arr;
}

quicksort() [1/2]

template<typename T >

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.

Template Parameters

T	type of data in the vector array

Parameters

[in,out]	arr	vector array to sort
[in]	low	lower limit of window to partition
[in]	high	upper limit of window to partition

Definition at line 94 of file quick_sort_3.cpp.

                                                             {
    if (low >= high) {  // 1 or 0 elements
        return;
    }
 
    int32_t i = 0, j = 0;
 
    // i and j are passed as reference
    partition3(arr, low, high, &i, &j);
 
    // Recur two halves
    quicksort(arr, low, i);
    quicksort(arr, j, high);
}

quicksort() [2/2]

template<typename T >

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.

Template Parameters

T	type of data in the vector array

Parameters

[in]	arr	vector array to sort
[in]	low	lower limit of window to partition
[in]	high	upper limit of window to partition

Returns

sorted array vector

Definition at line 119 of file quick_sort_3.cpp.

                                                                    {
    if (low >= high) {  // 1 or 0 elements
        return arr;
    }
 
    int32_t i = 0, j = 0;
 
    // i and j are passed as reference
    partition3(&arr, low, high, &i, &j);
 
    // Recur two halves
    quicksort(&arr, low, i);
    quicksort(&arr, j, high);
 
    return arr;
}

randomized_bogosort()

template<typename T , size_t N>

std::array< T, N > sorting::randomized_bogosort

(

std::array< T, N >

arr

)

Implement randomized Bogosort algorithm and sort the elements of a given array.

Template Parameters

T	typename of the array
N	length of array

Parameters

arr	array to sort

Returns

new array with elements sorted from a given array

Definition at line 52 of file bogo_sort.cpp.

                                                          {
    // Untill array is not sorted
    std::random_device random_device;
    std::mt19937 generator(random_device());
    while (!std::is_sorted(arr.begin(), arr.end())) {
        std::shuffle(arr.begin(), arr.end(), generator);// Shuffle the array
    }
    return arr;
}

recursive_bubble_sort()

template<typename T >

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.

Template Parameters

T	type of data variables in the array

Parameters

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.

Definition at line 84 of file recursive_bubble_sort.cpp.

                                                           {
    if (n == 1) {  
        return;
    }
 
    for (uint64_t i = 0; i < n - 1; i++) {  
        if ((*nums)[i] > (*nums)[i + 1]) {
            std::swap((*nums)[i], (*nums)[i + 1]);
        }
    }
 
    recursive_bubble_sort(nums, n - 1);
}

selectionSort()

std::vector< uint64_t > sorting::selectionSort	(	const std::vector< uint64_t > &	arr,
		uint64_t	len )

Definition at line 48 of file selection_sort_iterative.cpp.

                                                  {
    std::vector<uint64_t> array(
        arr.begin(),
        arr.end());  // declare a vector in which result will be stored
    for (uint64_t it = 0; it < len; ++it) {
        uint64_t min = it;  // set min value
        for (uint64_t it2 = it + 1; it2 < len; ++it2) {
            if (array[it2] < array[min]) {  // check which element is smaller
                min = it2;  // store index of smallest element to min
            }
        }
 
        if (min != it) {  // swap if min does not match to i
            uint64_t tmp = array[min];
            array[min] = array[it];
            array[it] = tmp;
        }
    }
 
    return array;  // return sorted vector
}

shell_sort() [1/3]

template<typename T >

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.

Definition at line 75 of file shell_sort2.cpp.

                                   {
    shell_sort(arr->data(), arr->size());
}

shell_sort() [2/3]

template<typename T >

void sorting::shell_sort	(	T *	arr,
		size_t	LEN )

Optimized algorithm - takes half the time by utilizing Mar

Definition at line 45 of file shell_sort2.cpp.

                                    {
    const unsigned int gaps[] = {701, 301, 132, 57, 23, 10, 4, 1};
    const unsigned int gap_len = 8;
    size_t i, j, g;
 
    for (g = 0; g < gap_len; g++) {
        unsigned int gap = gaps[g];
        for (i = gap; i < LEN; i++) {
            T tmp = arr[i];
 
            for (j = i; j >= gap && (arr[j - gap] - tmp) > 0; j -= gap) {
                arr[j] = arr[j - gap];
            }
 
            arr[j] = tmp;
        }
    }
}

shell_sort() [3/3]

template<typename T , size_t N>

void sorting::shell_sort

(

T(&)

arr[N]

)

function overload - when input array is of a known length array type

Definition at line 67 of file shell_sort2.cpp.

                             {
    shell_sort(arr, N);
}

shuffle()

template<typename T , size_t N>

std::array< T, N > sorting::shuffle

(

std::array< T, N >

arr

)

Function to shuffle the elements of an array. (for reference)

Template Parameters

T	typename of the array
N	length of array

Parameters

arr	array to shuffle

Returns

new array with elements shuffled from a given array

Definition at line 37 of file bogo_sort.cpp.

                                              {
    for (int i = 0; i < N; i++) {
        // Swaps i'th  index with random index (less than array size)
        std::swap(arr[i], arr[std::rand() % N]);
    }
    return arr;
}