Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
sorting Namespace Reference

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)
 

Detailed Description

Sorting algorithms.

Sorting Algorithms.

Sorting algorithms

Function Documentation

◆ 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
Ttype of data variables in the array
sizesize of the array
Parameters
[in]arrour array of elements.
Returns
array with elements sorted
62  {
63  // few easy cases
64  if (size <= 1) {
65  return arr;
66  }
67 
68  int index = 0; // initialize loop index
69  while (index < size) {
70  // check for swap
71  if ((index == 0) || (arr[index] >= arr[index - 1])) {
72  index++;
73  } else {
74  std::swap(arr[index], arr[index - 1]); // swap
75  index--;
76  }
77  }
78  return arr;
79 }

◆ 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]arrour array of elements.
sizesize of given array
34  {
35  // few easy cases
36  if (size <= 1) {
37  return;
38  }
39 
40  int index = 0; // initialize some variables.
41  while (index < size) {
42  // check for swap
43  if ((index == 0) || (arr[index] >= arr[index - 1])) {
44  index++;
45  } else {
46  std::swap(arr[index], arr[index - 1]); // swap
47  index--;
48  }
49  }
50 }

◆ insertionSort() [1/2]

template<typename T >
void sorting::insertionSort ( std::vector< T > *  arr)

Insertion Sort Function

Template Parameters
Ttype of array
Parameters
[in,out]arrpointer to array to be sorted
77  {
78  size_t n = arr->size();
79 
80  for (size_t i = 1; i < n; i++) {
81  T temp = arr[0][i];
82  int32_t j = i - 1;
83  while (j >= 0 && temp < arr[0][j]) {
84  arr[0][j + 1] = arr[0][j];
85  j--;
86  }
87  arr[0][j + 1] = temp;
88  }
89 }
Here is the call graph for this function:

◆ insertionSort() [2/2]

template<typename T >
void sorting::insertionSort ( T *  arr,
int  n 
)

Insertion Sort Function.

Template Parameters
Ttype of array
Parameters
[in,out]arrArray to be sorted
nSize of Array
59  {
60  for (int i = 1; i < n; i++) {
61  T temp = arr[i];
62  int j = i - 1;
63  while (j >= 0 && temp < arr[j]) {
64  arr[j + 1] = arr[j];
65  j--;
66  }
67  arr[j + 1] = temp;
68  }
69 }

◆ 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
lpoints to the left part
rpoints to the right part, end of left part
epoints to end of right part
bpoints at the buffer
57  {
58  // create 2 pointers to point at the buffer
59  auto p(reinterpret_cast<std::remove_reference_t<decltype(*l)>*>(b)), c(p);
60  // move the left part of the segment
61  for (Iterator t(l); r != t; ++t) *p++ = std::move(*t);
62  // while neither the buffer nor the right part has been exhausted
63  // move the smallest element of the two back to the container
64  while (e != r && c != p) *l++ = std::move(*r < *c ? *r++ : *c++);
65  // notice only one of the two following loops will be executed
66  // while the right part hasn't bee exhausted, move it back
67  while (e != r) *l++ = std::move(*r++);
68  // while the buffer hasn't bee exhausted, move it back
69  while (c != p) *l++ = std::move(*c++);
70 }
Here is the call graph for this function:

◆ 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
firstpoints to the first element
lastpoints to 1-step past the last element
86  {
87  non_recursive_merge_sort(first, last, last - first);
88 }
Here is the call graph for this function:

◆ 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
firstpoints to the first element
lastpoints to 1-step past the last element
nthe number of elements
26  {
27  // create a buffer large enough to store all elements
28  // dynamically allocated to comply with cpplint
29  char* buffer = new char[n * sizeof(*first)];
30  // buffer size can be optimized to largest power of 2 less than n
31  // elements divide the container into equally-sized segments whose
32  // length start at 1 and keeps increasing by factors of 2
33  for (size_t length(1); length < n; length <<= 1) {
34  // merge adjacent segments whose number is n / (length * 2)
35  Iterator left(first);
36  for (size_t counter(n / (length << 1)); counter; --counter) {
37  Iterator right(left + length), end(right + length);
38  merge(left, right, end, buffer);
39  left = end;
40  }
41  // if the number of remaining elements (n * 2 % length) is longer
42  // than a segment, merge the remaining elements
43  if ((n & ((length << 1) - 1)) > length)
44  merge(left, left + length, last, buffer);
45  }
46  delete[] buffer;
47 }
Here is the call graph for this function:

◆ 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
firstpoints to the first element
nthe number of elements
77  {
78  non_recursive_merge_sort(first, first + n, n);
79 }
Here is the call graph for this function:

◆ partition()

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

37  {
38  int pivot = arr[high]; // taking the last element as pivot
39  int i = (low - 1); // Index of smaller element
40 
41  for (int j = low; j < high; j++) {
42  // If current element is smaller than or
43  // equal to pivot
44  if (arr[j] <= pivot) {
45  i++; // increment index of smaller element
46  int temp = arr[i];
47  arr[i] = arr[j];
48  arr[j] = temp;
49  }
50  }
51  int temp = arr[i + 1];
52  arr[i + 1] = arr[high];
53  arr[high] = temp;
54  return (i + 1);
55 }

◆ 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
arrunsorted array of elements
Returns
sorted array of elements
34  {
35  // Finding min and max*
36  auto min = std::min_element(std::begin(arr), std::end(arr));
37  auto max = std::max_element(std::begin(arr), std::end(arr));
38 
39  // Range refers to the number of holes required
40  int range = *max - *min + 1;
41  int *hole = new int[range]();
42 
43  // Copying all array values to pigeonhole
44  for (int i = 0; i < N; i++) {
45  hole[arr[i] - *min] = arr[i];
46  }
47 
48  // Deleting elements from list and storing to original array
49  int count = 0;
50  for (int i = 0; i < range; i++) {
51  while (hole[i] != '\0') {
52  arr[count] = hole[i];
53  hole[i] = {};
54  count++;
55  }
56  }
57  delete[] hole;
58 
59  return arr;
60 }
Here is the call graph for this function:

◆ quickSort()

void sorting::quickSort ( int  arr[],
int  low,
int  high 
)

The main function that implements QuickSort arr[] --> Array to be sorted, low --> Starting index, high --> Ending index

63  {
64  if (low < high) {
65  int p = partition(arr, low, high);
66  quickSort(arr, low, p - 1);
67  quickSort(arr, p + 1, high);
68  }
69 }
Here is the call graph for this function:

◆ 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
Ttype of data in the vector array
Parameters
[in,out]arrvector array to sort
[in]lowlower limit of window to partition
[in]highupper limit of window to partition
94  {
95  if (low >= high) { // 1 or 0 elements
96  return;
97  }
98 
99  int32_t i = 0, j = 0;
100 
101  // i and j are passed as reference
102  partition3(arr, low, high, &i, &j);
103 
104  // Recur two halves
105  quicksort(arr, low, i);
106  quicksort(arr, j, high);
107 }

◆ 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
Ttype of data in the vector array
Parameters
[in]arrvector array to sort
[in]lowlower limit of window to partition
[in]highupper limit of window to partition
Returns
sorted array vector
119  {
120  if (low >= high) { // 1 or 0 elements
121  return arr;
122  }
123 
124  int32_t i = 0, j = 0;
125 
126  // i and j are passed as reference
127  partition3(&arr, low, high, &i, &j);
128 
129  // Recur two halves
130  quicksort(&arr, low, i);
131  quicksort(&arr, j, high);
132 
133  return arr;
134 }
Here is the call graph for this function:

◆ 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
Ttypename of the array
Nlength of array
Parameters
arrarray to sort
Returns
new array with elements sorted from a given array
51  {
52  // Untill array is not sorted
53  while (!std::is_sorted(arr.begin(), arr.end())) {
54  std::random_shuffle(arr.begin(), arr.end());// Shuffle the array
55  }
56  return arr;
57 }
Here is the call graph for this function:

◆ 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.

75  {
76  shell_sort(arr->data(), arr->size());
77 }
Here is the call graph for this function:

◆ 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

45  {
46  const unsigned int gaps[] = {701, 301, 132, 57, 23, 10, 4, 1};
47  const unsigned int gap_len = 8;
48  size_t i, j, g;
49 
50  for (g = 0; g < gap_len; g++) {
51  unsigned int gap = gaps[g];
52  for (i = gap; i < LEN; i++) {
53  T tmp = arr[i];
54 
55  for (j = i; j >= gap && (arr[j - gap] - tmp) > 0; j -= gap) {
56  arr[j] = arr[j - gap];
57  }
58 
59  arr[j] = tmp;
60  }
61  }
62 }

◆ 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

67  {
68  shell_sort(arr, N);
69 }
Here is the call graph for this function:

◆ 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
Ttypename of the array
Nlength of array
Parameters
arrarray to shuffle
Returns
new array with elements shuffled from a given array
36  {
37  for (int i = 0; i < N; i++) {
38  // Swaps i'th index with random index (less than array size)
39  std::swap(arr[i], arr[std::rand() % N]);
40  }
41  return arr;
42 }
Here is the call graph for this function:
std::max_element
T max_element(T... args)
sorting::quicksort
std::vector< T > quicksort(std::vector< T > arr, int32_t low, int32_t high)
Definition: quick_sort_3.cpp:119
std::move
T move(T... args)
std::vector::size
T size(T... args)
sorting::partition
int partition(int arr[], int low, int high)
Definition: quick_sort.cpp:37
std::is_sorted
T is_sorted(T... args)
merge
void merge(int *arr, int l, int m, int r)
Definition: merge_sort.cpp:33
sorting::non_recursive_merge_sort
void non_recursive_merge_sort(const Iterator first, const Iterator last)
bottom-up merge sort which sorts elements in a non-decreasing order
Definition: non_recursive_merge_sort.cpp:86
std::min_element
T min_element(T... args)
std::rand
T rand(T... args)
std::swap
T swap(T... args)
std::min
T min(T... args)
std::left
T left(T... args)
std::begin
T begin(T... args)
std::end
T end(T... args)
std::max
T max(T... args)
std::random_shuffle
T random_shuffle(T... args)
sorting::quickSort
void quickSort(int arr[], int low, int high)
Definition: quick_sort.cpp:63
std::vector::data
T data(T... args)
sorting::shell_sort
void shell_sort(std::vector< T > *arr)
Definition: shell_sort2.cpp:75