Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
merge_insertion_sort.cpp File Reference

Algorithm that combines insertion sort and merge sort. Wiki link More...

#include <algorithm>
#include <array>
#include <cassert>
#include <ctime>
#include <iostream>
#include <memory>
Include dependency graph for merge_insertion_sort.cpp:

Namespaces

namespace  sorting
 for working with vectors
 
namespace  merge_insertion
 Combined Intersion-Merge sorting algorithm.
 

Functions

template<typename T , size_t N>
static void sorting::merge_insertion::InsertionSort (std::array< T, N > *A, size_t start, size_t end)
 Insertion merge algorithm.
 
template<typename T , size_t N>
static void sorting::merge_insertion::merge (std::array< T, N > *array, size_t min, size_t max, size_t mid)
 Perform merge of data in a window.
 
template<typename T , size_t N>
void sorting::merge_insertion::mergeSort (std::array< T, N > *array, size_t min, size_t max, size_t threshold)
 Final combined algorithm. Algorithm utilizes sorting::merge_insertion::InsertionSort if window length is less than threshold, else performs merge sort recursively using sorting::merge_insertion::mergeSort.
 
static void test ()
 Function to test code using random arrays.
 
int main ()
 Main function.
 

Detailed Description

Algorithm that combines insertion sort and merge sort. Wiki link

Author
@sinkyoungdeok
Krishna Vedala
See also
Individual algorithms: insertion_sort.cpp and merge_sort.cpp

Function Documentation

◆ InsertionSort()

template<typename T , size_t N>
static void sorting::merge_insertion::InsertionSort ( std::array< T, N > * A,
size_t start,
size_t end )
static

Insertion merge algorithm.

See also
insertion_sort.cpp
Template Parameters
Tarray data type
Nlength of array
Parameters
Apointer to array to sort
startstart index of sorting window
endend index of sorting window
37 {
38 size_t i = 0, j = 0;
39 T *ptr = A->data();
40
41 for (i = start; i < end; i++) {
42 T temp = ptr[i];
43 j = i;
44 while (j > start && temp < ptr[j - 1]) {
45 ptr[j] = ptr[j - 1];
46 j--;
47 }
48 // for (j = i; j > start && temp < ptr[j - 1]; --j) {
49 // ptr[j] = ptr[j - 1];
50 // }
51
52 ptr[j] = temp;
53 }
54}
T data(T... args)
T end(T... args)
Here is the call graph for this function:

◆ main()

int main ( void )

Main function.

Returns
0 on exit
159 {
160 std::srand(std::time(nullptr));
161 test();
162 return 0;
163}
static void test()
Function to test code using random arrays.
Definition merge_insertion_sort.cpp:132
T srand(T... args)
T time(T... args)
Here is the call graph for this function:

◆ merge()

template<typename T , size_t N>
static void sorting::merge_insertion::merge ( std::array< T, N > * array,
size_t min,
size_t max,
size_t mid )
static

Perform merge of data in a window.

Template Parameters
Tarray data type
Nlength of array
Parameters
Apointer to array to sort
minstart index of window
maxend index of window
midmid-point of window
67 {
68 size_t firstIndex = min;
69 size_t secondIndex = mid + 1;
70
71 auto ptr = array->data();
72 std::array<T, N + 1> tempArray{0};
73
74 // While there are elements in the left or right runs
75 for (size_t index = min; index <= max; index++) {
76 // If left run head exists and is <= existing right run head.
77 if (firstIndex <= mid &&
78 (secondIndex > max || ptr[firstIndex] <= ptr[secondIndex])) {
79 tempArray[index] = ptr[firstIndex];
80 firstIndex++;
81 } else {
82 tempArray[index] = ptr[secondIndex];
83 secondIndex++;
84 }
85 }
86
87 // transfer to the initial array
88 memcpy(ptr + min, tempArray.data() + min, (max - min) * sizeof(T));
89 // for (int index = min; index <= max; index++) ptr[index] =
90 // tempArray[index];
91}
T max(T... args)
T memcpy(T... args)
T min(T... args)
Here is the call graph for this function:

◆ mergeSort()

template<typename T , size_t N>
void sorting::merge_insertion::mergeSort ( std::array< T, N > * array,
size_t min,
size_t max,
size_t threshold )

Final combined algorithm. Algorithm utilizes sorting::merge_insertion::InsertionSort if window length is less than threshold, else performs merge sort recursively using sorting::merge_insertion::mergeSort.

Template Parameters
Tarray data type
Nlength of array
Parameters
Apointer to array to sort
minstart index of sort window
maxend index of sort window
thresholdwindow length threshold
108 {
109 // prerequisite
110 if ((max - min) <= threshold) {
111 InsertionSort(array, min, max);
112 } else {
113 // get the middle point
114 size_t mid = (max + min) >> 1;
115
116 // apply merge sort to both parts of this
117 mergeSort(array, min, mid, threshold);
118 mergeSort(array, mid, max, threshold);
119
120 // and finally merge all that sorted stuff
121 merge(array, min, max, mid);
122 }
123}
void merge(int *arr, int l, int m, int r)
Definition merge_sort.cpp:33
void mergeSort(int *arr, int l, int r)
Definition merge_sort.cpp:71
static void InsertionSort(std::array< T, N > *A, size_t start, size_t end)
Insertion merge algorithm.
Definition merge_insertion_sort.cpp:37
Here is the call graph for this function:

◆ test()

static void test ( )
static

Function to test code using random arrays.

Returns
none
132 {
133 constexpr size_t size = 30;
134 std::array<int, size> array{0};
135 // input
136 for (int i = 0; i < size; i++) {
137 array[i] = std::rand() % 100 - 50;
138 std::cout << array[i] << " ";
139 }
141
143 // sorting::merge_insertion::mergeSort(&array, 0, size, 10);
144
145 // output
146 for (int i = 0; i < size; ++i) {
147 std::cout << array[i] << " ";
148 }
150
151 assert(std::is_sorted(std::begin(array), std::end(array)));
152 std::cout << "Test passed\n";
153}
T begin(T... args)
T endl(T... args)
T is_sorted(T... args)
T rand(T... args)
Here is the call graph for this function: