|
namespace | sorting |
| for working with vectors
|
|
|
template<typename T > |
void | heapify (T *arr, int n, int i) |
|
template<typename T > |
void | heapSort (T *arr, int n) |
|
void | merge (int *arr, int l, int m, int r) |
|
void | mergeSort (int *arr, int l, int r) |
|
void | show (int *arr, int size) |
|
int | main () |
|
template<typename T > |
static void | displayElements (const std::vector< T > &arr) |
| Utility function used for printing the elements. Prints elements of the array after they're sorted using wiggle sort algorithm.
|
|
static void | test () |
|
The heapify procedure can be thought of as building a heap from the bottom up by successively sifting downward to establish the heap property.
- Parameters
-
arr | array to be sorted |
n | size of array |
i | node position in Binary Tress or element position in Array to be compared with it's childern |
◆ displayElements()
template<typename T >
static void displayElements |
( |
const std::vector< T > & | arr | ) |
|
|
static |
Utility function used for printing the elements. Prints elements of the array after they're sorted using wiggle sort algorithm.
- Parameters
-
arr | array containing the sorted elements |
- Examples
- /Users/runner/work/C-Plus-Plus/C-Plus-Plus/sorting/wiggle_sort.cpp.
85 {
86 uint32_t size = arr.
size();
87
88 std::cout <<
"Sorted elements are as follows: ";
89
91
92 for (int i = 0; i < size; i++) {
94 if (i != size - 1) {
96 }
97 }
98
100}
◆ heapify()
template<typename T >
void heapify |
( |
T * | arr, |
|
|
int | n, |
|
|
int | i ) |
58 {
59 int largest = i;
60 int l = 2 * i + 1;
61 int r = 2 * i + 2;
62
63 if (l < n && arr[l] > arr[largest])
64 largest = l;
65
66 if (r < n && arr[r] > arr[largest])
67 largest = r;
68
69 if (largest != i) {
71 heapify(arr, n, largest);
72 }
73}
◆ heapSort()
template<typename T >
void heapSort |
( |
T * | arr, |
|
|
int | n ) |
Utilizes heapify procedure to sort the array
- Parameters
-
arr | array to be sorted |
n | size of array |
84 {
85 for (int i = n - 1; i >= 0; i--) heapify(arr, n, i);
86
87 for (int i = n - 1; i >= 0; i--) {
89 heapify(arr, i, 0);
90 }
91}
◆ main()
Main function
Driver Code
90 {
91 int size;
92 std::cout <<
"Enter the number of elements : ";
94 int *arr = new int[size];
95 std::cout <<
"Enter the unsorted elements : ";
96 for (int i = 0; i < size; ++i) {
98 }
101 show(arr, size);
102 delete[] arr;
103 return 0;
104}
void mergeSort(int *arr, int l, int r)
Definition merge_sort.cpp:71
◆ merge()
void merge |
( |
int * | arr, |
|
|
int | l, |
|
|
int | m, |
|
|
int | r ) |
The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.
- Parameters
-
arr | - array with two halves arr[l...m] and arr[m+1...r] |
l | - left index or start index of first half array |
m | - right index or end index of first half array |
(The second array starts form m+1 and goes till r)
- Parameters
-
r | - end index or right index of second half array |
33 {
34 int i, j, k;
35 int n1 = m - l + 1;
36 int n2 = r - m;
37
38 int *L = new int[n1], *R = new int[n2];
39
40 for (i = 0; i < n1; i++) L[i] = arr[l + i];
41 for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
42
43 i = 0;
44 j = 0;
45 k = l;
46 while (i < n1 || j < n2) {
47 if (j >= n2 || (i < n1 && L[i] <= R[j])) {
48 arr[k] = L[i];
49 i++;
50 } else {
51 arr[k] = R[j];
52 j++;
53 }
55 }
56
57 delete[] L;
58 delete[] R;
59}
double k(double x)
Another test function.
Definition composite_simpson_rule.cpp:117
◆ mergeSort()
void mergeSort |
( |
int * | arr, |
|
|
int | l, |
|
|
int | r ) |
Merge sort is a divide and conquer algorithm, it divides the input array into two halves and calls itself for the two halves and then calls merge() to merge the two halves
- Parameters
-
arr | - array to be sorted |
l | - left index or start index of array |
r | - right index or end index of array |
71 {
72 if (l < r) {
73 int m = l + (r - l) / 2;
77 }
78}
void merge(int *arr, int l, int m, int r)
Definition merge_sort.cpp:33
◆ show()
void show |
( |
int * | arr, |
|
|
int | size ) |
Utility function used to print the array after sorting
84 {
85 for (
int i = 0; i < size; i++)
std::cout << arr[i] <<
" ";
87}
◆ test()
Test function
- Returns
- void
106 {
108
110 for (auto &d : data1) {
111 d = float(
std::rand() % 1000 - 500) / 100.f;
112 }
113
115
117
118 for (uint32_t j = 0; j < data1.size(); j += 2) {
119 assert(data1[j] <= data1[j + 1] &&
120 data1[j + 1] >= data1[j + 2]);
121 }
122
124}
static void displayElements(const std::vector< T > &arr)
Utility function used for printing the elements. Prints elements of the array after they're sorted us...
Definition wiggle_sort.cpp:85