Examples of Insertion and Merge Sorts in C++
Since the lectures in this unit use Python, review these examples of Insertion and Merge sorts in C++.
Insertion Sort:
/* insertion sort ascending order */ #includeint main() { int n, array[1000], c, d, t; printf("Enter number of elements\n"); scanf("%d", &n); printf("Enter %d integers\n", n); for (c = 0; c < n; c++) { scanf("%d", &array[c]); } for (c = 1 ; c <= n - 1; c++) { d = c; while ( d > 0 && array[d] < array[d-1]) { t = array[d]; array[d] = array[d-1]; array[d-1] = t; d--; } } printf("Sorted list in ascending order:\n"); for (c = 0; c <= n - 1; c++) { printf("%d\n", array[c]); } return 0; }
Merge Sort:
// Declare/initialize any useful variables here, including the temporary array // to merge values into and then copy back into the parameter array. /* while the temporary array is not filled if there are no more values in the left part of a, move next value from right part of a into next index of the temporary array otherwise, if there are no more values in the right part of a, move next value from left part of a into next index of the temporary array otherwise (values in each part) compare the first value in each part move smallest value from a into next index of the temporary array Copy all values from the temporary array back into a, starting at left_low */ void merge_sort(int a[], int length) { merge_sort(a, 0, length-1); } void merge_sort(int a[], int low, int high) { if (low >= high) //Base case: 1 value to sort->sorted return; //(0 possible only on initial call) else { int mid = (low + high)/2; //Approximate midpoint* merge_sort(a, low, mid); //Sort low to mid part of array merge_sort(a, mid+1, high); //Sort mid+1 to high part of array merge(a, low, mid, mid+1,high); //Merge sorted subparts of array } } void merge(int a[], int left_low, int left_high, int right_low, int right_high) { int length = right_high-left_low+1; int temp[length]; int left = left_low; int right = right_low; for (int i = 0; i < length; ++i) { if (left > left_high) temp[i] = a[right++]; else if (right > right_high) temp[i] = a[left++]; else if (a[left] <= a[right]) temp[i] = a[left++]; else temp[i] = a[right++]; } for (int i=0; i< length; ++i) a[left_low++] = temp[i]; }
Source: http://www.programmingsimplified.com/c/source-code/c-program-insertion-sort and https://gist.githubusercontent.com/kbendick/1de4f311e2a780339eb3/raw/f65b82b7a055806004af4962290adb5c401335e1/mergesort.cpp This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.
Last modified: Friday, September 22, 2017, 2:45 PM