Merge pull request thuva4#93 from srpurwaha201/master

thuva4 · web-flow · commit a14f92bb07a1 · 2017-10-05T19:31:34.000+05:30
add mergeSort algo for c++
diff --git a/HeapSort/C++/HeapSort.cpp b/HeapSort/C++/HeapSort.cpp
@@ -0,0 +1,67 @@
+// C++ program for implementation of Heap Sort
+#include <iostream>
+using namespace std;
+
+// To heapify a subtree rooted with node i which is
+// an index in arr[]. n is size of heap
+void heapify(int arr[], int n, int i)
+{
+	int largest = i; // Initialize largest as root
+	int l = 2*i + 1; // left = 2*i + 1
+	int r = 2*i + 2; // right = 2*i + 2
+
+	// If left child is larger than root
+	if (l < n && arr[l] > arr[largest])
+		largest = l;
+
+	// If right child is larger than largest so far
+	if (r < n && arr[r] > arr[largest])
+		largest = r;
+
+	// If largest is not root
+	if (largest != i)
+	{
+		swap(arr[i], arr[largest]);
+
+		// Recursively heapify the affected sub-tree
+		heapify(arr, n, largest);
+	}
+}
+
+// main function to do heap sort
+void heapSort(int arr[], int n)
+{
+	// Build heap (rearrange array)
+	for (int i = n / 2 - 1; i >= 0; i--)
+		heapify(arr, n, i);
+
+	// One by one extract an element from heap
+	for (int i=n-1; i>=0; i--)
+	{
+		// Move current root to end
+		swap(arr[0], arr[i]);
+
+		// call max heapify on the reduced heap
+		heapify(arr, i, 0);
+	}
+}
+
+/* A utility function to print array of size n */
+void printArray(int arr[], int n)
+{
+	for (int i=0; i<n; ++i)
+		cout << arr[i] << " ";
+	cout << "\n";
+}
+
+// Driver program
+int main()
+{
+	int arr[] = {12, 11, 13, 5, 6, 7};
+	int n = sizeof(arr)/sizeof(arr[0]);
+
+	heapSort(arr, n);
+
+	cout << "Sorted array is \n";
+	printArray(arr, n);
+}
diff --git a/MergeSort/C++/MergeSort.cpp b/MergeSort/C++/MergeSort.cpp
@@ -0,0 +1,92 @@
+#include <iostream>
+
+using namespace std;
+
+// A function to merge the two half into a sorted data.
+void Merge(int *a, int low, int high, int mid)
+{
+	// We have low to mid and mid+1 to high already sorted.
+	int i, j, k, temp[high-low+1];
+	i = low;
+	k = 0;
+	j = mid + 1;
+
+	// Merge the two parts into temp[].
+	while (i <= mid && j <= high)
+	{
+		if (a[i] < a[j])
+		{
+			temp[k] = a[i];
+			k++;
+			i++;
+		}
+		else
+		{
+			temp[k] = a[j];
+			k++;
+			j++;
+		}
+	}
+
+	// Insert all the remaining values from i to mid into temp[].
+	while (i <= mid)
+	{
+		temp[k] = a[i];
+		k++;
+		i++;
+	}
+
+	// Insert all the remaining values from j to high into temp[].
+	while (j <= high)
+	{
+		temp[k] = a[j];
+		k++;
+		j++;
+	}
+
+
+	// Assign sorted data stored in temp[] to a[].
+	for (i = low; i <= high; i++)
+	{
+		a[i] = temp[i-low];
+	}
+}
+
+// A function to split array into two parts.
+void MergeSort(int *a, int low, int high)
+{
+	int mid;
+	if (low < high)
+	{
+		mid=(low+high)/2;
+		// Split the data into two half.
+		MergeSort(a, low, mid);
+		MergeSort(a, mid+1, high);
+
+		// Merge them to get sorted output.
+		Merge(a, low, high, mid);
+	}
+}
+
+int main()
+{
+	int n, i;
+	cout<<"\nEnter the number of data element to be sorted: ";
+	cin>>n;
+
+	int arr[n];
+	for(i = 0; i < n; i++)
+	{
+		cout<<"Enter element "<<i+1<<": ";
+		cin>>arr[i];
+	}
+
+	MergeSort(arr, 0, n-1);
+
+	// Printing the sorted data.
+	cout<<"\nSorted Data ";
+	for (i = 0; i < n; i++)
+        cout<<"->"<<arr[i];
+
+	return 0;
+}
