Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
Sorting Algorithm

Files

file  merge_sort.cpp
 Merege Sort Algorithm (MEREGE SORT) implementation
 

Functions

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 ()
 

Detailed Description

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
arrarray to be sorted
nsize of array
inode position in Binary Tress or element position in Array to be compared with it's childern

Function Documentation

◆ heapSort()

template<typename T >
void heapSort ( T *  arr,
int  n 
)

Utilizes heapify procedure to sort the array

Parameters
arrarray to be sorted
nsize 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--) {
88  std::swap(arr[0], arr[i]);
89  heapify(arr, i, 0);
90  }
91 }

◆ main()

int main ( void  )

Main function

102  {
103  int size;
104  std::cout << "Enter the number of elements : ";
105  std::cin >> size;
106  int *arr = new int[size];
107  std::cout << "Enter the unsorted elements : ";
108  for (int i = 0; i < size; ++i) {
109  std::cin >> arr[i];
110  }
111  mergeSort(arr, 0, size - 1);
112  std::cout << "Sorted array : ";
113  show(arr, size);
114  delete[] arr;
115  return 0;
116 }

◆ 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
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 (L[i] <= R[j]) {
48  arr[k] = L[i];
49  i++;
50  } else {
51  arr[k] = R[j];
52  j++;
53  }
54  k++;
55  }
56 
57  while (i < n1) {
58  arr[k] = L[i];
59  i++;
60  k++;
61  }
62 
63  while (j < n2) {
64  arr[k] = R[j];
65  j++;
66  k++;
67  }
68 
69  delete[] L;
70  delete[] R;
71 }

◆ 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
83  {
84  if (l < r) {
85  int m = l + (r - l) / 2;
86  mergeSort(arr, l, m);
87  mergeSort(arr, m + 1, r);
88  merge(arr, l, m, r);
89  }
90 }
Here is the call graph for this function:

◆ show()

void show ( int *  arr,
int  size 
)

Utility function used to print the array after sorting

96  {
97  for (int i = 0; i < size; i++) std::cout << arr[i] << " ";
98  std::cout << "\n";
99 }
show
void show(int *arr, int size)
Definition: merge_sort.cpp:96
mergeSort
void mergeSort(int *arr, int l, int r)
Definition: merge_sort.cpp:83
std::cout
merge
void merge(int *arr, int l, int m, int r)
Definition: merge_sort.cpp:33
std::swap
T swap(T... args)
std::cin