|
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 () |
|
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 |
◆ 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 |
85 for (
int i = n - 1; i >= 0; i--) heapify(arr, n, i);
87 for (
int i = n - 1; i >= 0; i--) {
◆ main()
Main function
104 std::cout <<
"Enter the number of elements : ";
106 int *arr =
new int[size];
107 std::cout <<
"Enter the unsorted elements : ";
108 for (
int i = 0; i < size; ++i) {
◆ 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...l] |
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 l)
- Parameters
-
l | - end index or right index of second half array |
38 int *L =
new int[n1], *R =
new int[n2];
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];
46 while (i < n1 && j < n2) {
◆ 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 |
85 int m = l + (r - l) / 2;
◆ show()
void show |
( |
int * |
arr, |
|
|
int |
size |
|
) |
| |
Utility function used to print the array after sorting
97 for (
int i = 0; i < size; i++)
std::cout << arr[i] <<
" ";