A RetroSearch Logo

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Search Query:

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/de/d7b/merge__insertion__sort_8cpp.html below:

TheAlgorithms/C++: sorting/merge_insertion_sort.cpp File Reference

Loading...

Searching...

No Matches

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

#include <algorithm>
#include <array>
#include <cassert>
#include <ctime>
#include <iostream>
#include <memory>

Go to the source code of this file.

namespace   sorting   for working with vectors
namespace   merge_insertion   Combined Intersion-Merge sorting algorithm.
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.

Algorithm that combines insertion sort and merge sort. Wiki link

See also
Individual algorithms: insertion_sort.cpp and merge_sort.cpp

Definition in file merge_insertion_sort.cpp.

◆ InsertionSort()

template<typename T, size_t N>

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
T array data type N length of array
Parameters
A pointer to array to sort start start index of sorting window end end index of sorting window

Definition at line 37 of file merge_insertion_sort.cpp.

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

49

50

51

52 ptr[j] = temp;

53 }

54}

◆ main()

Main function.

Returns
0 on exit

Definition at line 159 of file merge_insertion_sort.cpp.

159 {

160 std::srand(std::time(nullptr));

162 return 0;

163}

static void test()

Function to test code using random arrays.

◆ merge()

template<typename T, size_t N>

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
T array data type N length of array
Parameters
A pointer to array to sort min start index of window max end index of window mid mid-point of window

Definition at line 67 of file merge_insertion_sort.cpp.

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

75 for (size_t index = min; index <= max; index++) {

76

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

88 memcpy(ptr + min, tempArray.data() + min, (max - min) * sizeof(T));

89

90

91}

◆ 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
T array data type N length of array
Parameters
A pointer to array to sort min start index of sort window max end index of sort window threshold window length threshold

Definition at line 107 of file merge_insertion_sort.cpp.

108 {

109

110 if ((max - min) <= threshold) {

112 } else {

113

114 size_t mid = (max + min) >> 1;

115

116

119

120

121 merge

(array, min, max, mid);

122 }

123}

void mergeSort(int *arr, int l, int r)

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

Insertion merge algorithm.

void merge(Iterator, Iterator, const Iterator, char[])

merges 2 sorted adjacent segments into a larger sorted segment

◆ test()

Function to test code using random arrays.

Returns
none

Definition at line 132 of file merge_insertion_sort.cpp.

132 {

133 constexpr size_t size = 30;

134 std::array<int, size> array{0};

135

136 for (int i = 0; i < size; i++) {

137 array[i] = std::rand() % 100 - 50;

138 std::cout << array[i] << " ";

139 }

140 std::cout << std::endl;

141

143

144

145

146 for (int i = 0; i < size; ++i) {

147 std::cout << array[i] << " ";

148 }

149 std::cout << std::endl;

150

151 assert(std::is_sorted(std::begin(array), std::end(array)));

152 std::cout << "Test passed\n";

153}

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4