MERGE SORTING PROGRAM

BELOW are the functions to implement

// Sorting function declarations void MergeSort(list& S); // MergeSort for list list& Merge(list& C, list& A, list& B); // Merge for list void SelectionSort(list& S); // SelectionSort for list void InsertionSort(int numbers[], int numbersSize); // InsertionSort for array void RadixSort(list& S); // RadixSort for list 

Insertion Sort - Pseudocode

Algorithm InsertionSort(A, size) for j = 1 to size - 1 key = A[j] i = j - 1 while(i > 0 and A[i] > key) A[i+1] = A[i] i = i - 1 A[i+1] = key 

Merge Sort - Pseudocode

Algorithm MergeSort(S) if S.size() > 1 (S1, S2) = partition(S, n/2) mergeSort(S1) mergeSort(S2) S = merge(S1, S2) 

Merge - Pseudocode

Algorithm Merge(A, B) C = empty list while (!A.isEmpty() and !B.isEmpty()) if A.first().element() < B.first().element() C.insertLast(A.remove(A.first())) else C.insertLast(B.remove(B.first())) while (!A.isEmpty() C.insertLast(A.remove(A.first())) while (!B.isEmpty() C.insertLast(B.remove(B.first())) return C 

sorting.cpp====================================================================================================

// sorting.cpp #include #include #include #include using namespace std; // Display function declarations void Display(list&); // displays std::list to std::out void Display(int a[], int size); // displays array to std::out // Sorting function declarations void MergeSort(list& S); // MergeSort for list list& Merge(list& C, list& A, list& B); // Merge for list void MergeSort(int numbers[], int i, int k); // MergeSort for array void Merge(int numbers[], int i, int j, int k); // Merge for array void SelectionSort(list& S); // SelectionSort for list void SelectionSort(int numbers[], int numbersSize); // SelectionSort for array void InsertionSort(int numbers[], int numbersSize); // InsertionSort for array void RadixSort(list& S); // RadixSort for list // Test function declarations void TestInsertionSortArray(int a[], int size); // InsertionSort list test void TestMergeSortList(list& S); // MergeSort list test void TestSelectionSortList(list& S); // SelectionSort list test int main() { srand((unsigned)time(0)); // seed random number generator // array (numbers_a*) declarations/initialization const int NUMBERS_SIZE = 8; int numbers_a0[] = { 11, 2, 88, 5, 45, 29, 7, 12 }; int numbers_a1[] = { 88, 45, 29, 12, 11, 7, 5, 2 }; int numbers_a2[] = { 1, -3, 7, 99, -77, 2, 4, -1 }; int numbers_a3[] = { 1, 2, 3, 13, 12, 11, 19, 10 }; // test InsertionSort on arrays (numbers_a*) TestInsertionSortArray(numbers_a0, NUMBERS_SIZE); TestInsertionSortArray(numbers_a1, NUMBERS_SIZE); TestInsertionSortArray(numbers_a2, NUMBERS_SIZE); TestInsertionSortArray(numbers_a3, NUMBERS_SIZE); // list (seq_l*) declarations list seq_l0; list seq_l1; list seq_l2; list seq_l3; // build lists (seq_l*) from arrays (numbers_a*) for(int i = 0; i < NUMBERS_SIZE; i++) { seq_l0.push_back(numbers_a0[i]); seq_l1.push_back(numbers_a1[i]); seq_l2.push_back(numbers_a2[i]); seq_l3.push_back(numbers_a3[i]); } // MergeSort tests on lists (seq_l*) TestMergeSortList(seq_l0); TestMergeSortList(seq_l1); TestMergeSortList(seq_l2); TestMergeSortList(seq_l3); // list (seq_l*) declarations list seq_l4; list seq_l5; list seq_l6; list seq_l7; const int LARGE_N = 10; // size for lists *increase* value int* a = NULL; // pointer to int, initialize to OxO a = new int[LARGE_N]; // allocate LARGE_N ints pointed to by a for(int i = 0; i < LARGE_N; i++) { a[i] = (rand() % (LARGE_N*LARGE_N)) + 1; seq_l4.push_back((rand() % (LARGE_N*LARGE_N)) + 1); seq_l5.push_back((rand() % (LARGE_N*LARGE_N)) + 1); seq_l6.push_back((rand() % (LARGE_N*LARGE_N)) + 1); seq_l7.push_back((rand() % (LARGE_N*LARGE_N)) + 1); } // InsertionSort, MergeSort, SelectionSort, // tests (for LARGE_N, on lists (seq_l*) TestInsertionSortArray(a, LARGE_N); TestMergeSortList(seq_l4); TestMergeSortList(seq_l5); TestSelectionSortList(seq_l6); TestSelectionSortList(seq_l7); return 0; } // Display list contents to std::out void Display(list& S) { for(list::iterator it = S.begin(); it != S.end(); ++it) cout << *it << " "; cout << endl; } // Display array contents to std::out void Display(int a[], int size) { for(int i = 0; i < size; ++i) cout << a[i] << " "; cout << endl; } // YOUR IMPLEMENTATION HERE // InsertionSort list test void TestInsertionSortArray(int a[], int size) { cout << "ARRAY UNSORTED: "; Display(a, size); InsertionSort(a, size); cout << "ARRAY INSERTION-SORTED: "; Display(a, size); } // MergeSort list test void TestMergeSortList(list& S) { cout << "LIST UNSORTED: "; Display(S); MergeSort(S); cout << "LIST MERGE-SORTED: "; Display(S); } // SelectionSort list test void TestSelectionSortList(list& S) { cout << "LIST UNSORTED: "; Display(S); SelectionSort(S); cout << "LIST SELECTION-SORTED: "; Display(S); } 

sorting_output.txt===========================================================================================================

ARRAY UNSORTED: 11 2 88 5 45 29 7 12 2 11 88 5 45 29 7 12 2 11 88 5 45 29 7 12 2 5 11 88 45 29 7 12 2 5 11 45 88 29 7 12 2 5 11 29 45 88 7 12 2 5 7 11 29 45 88 12 2 5 7 11 12 29 45 88 ARRAY INSERTION-SORTED: 2 5 7 11 12 29 45 88 ARRAY UNSORTED: 88 45 29 12 11 7 5 2 45 88 29 12 11 7 5 2 29 45 88 12 11 7 5 2 12 29 45 88 11 7 5 2 11 12 29 45 88 7 5 2 7 11 12 29 45 88 5 2 5 7 11 12 29 45 88 2 2 5 7 11 12 29 45 88 ARRAY INSERTION-SORTED: 2 5 7 11 12 29 45 88 ARRAY UNSORTED: 1 -3 7 99 -77 2 4 -1 -3 1 7 99 -77 2 4 -1 -3 1 7 99 -77 2 4 -1 -3 1 7 99 -77 2 4 -1 -77 -3 1 7 99 2 4 -1 -77 -3 1 2 7 99 4 -1 -77 -3 1 2 4 7 99 -1 -77 -3 -1 1 2 4 7 99 ARRAY INSERTION-SORTED: -77 -3 -1 1 2 4 7 99 ARRAY UNSORTED: 1 2 3 13 12 11 19 10 1 2 3 13 12 11 19 10 1 2 3 13 12 11 19 10 1 2 3 13 12 11 19 10 1 2 3 12 13 11 19 10 1 2 3 11 12 13 19 10 1 2 3 11 12 13 19 10 1 2 3 10 11 12 13 19 ARRAY INSERTION-SORTED: 1 2 3 10 11 12 13 19 LIST UNSORTED: 2 5 7 11 12 29 45 88 2 5 7 11 12 29 45 88 2 5 7 11 2 5 2 5 7 11 7 11 12 29 45 88 12 29 12 29 45 88 45 88 LIST MERGE-SORTED: 2 5 7 11 12 29 45 88 LIST UNSORTED: 2 5 7 11 12 29 45 88 2 5 7 11 12 29 45 88 2 5 7 11 2 5 2 5 7 11 7 11 12 29 45 88 12 29 12 29 45 88 45 88 LIST MERGE-SORTED: 2 5 7 11 12 29 45 88 LIST UNSORTED: -77 -3 -1 1 2 4 7 99 -77 -3 -1 1 2 4 7 99 -77 -3 -1 1 -77 -3 -77 -3 -1 1 -1 1 2 4 7 99 2 4 2 4 7 99 7 99 LIST MERGE-SORTED: -77 -3 -1 1 2 4 7 99 LIST UNSORTED: 1 2 3 10 11 12 13 19 1 2 3 10 11 12 13 19 1 2 3 10 1 2 1 2 3 10 3 10 11 12 13 19 11 12 11 12 13 19 13 19 LIST MERGE-SORTED: 1 2 3 10 11 12 13 19 ARRAY UNSORTED: 75 98 36 3 73 44 59 48 67 56 75 98 36 3 73 44 59 48 67 56 36 75 98 3 73 44 59 48 67 56 3 36 75 98 73 44 59 48 67 56 3 36 73 75 98 44 59 48 67 56 3 36 44 73 75 98 59 48 67 56 3 36 44 59 73 75 98 48 67 56 3 36 44 48 59 73 75 98 67 56 3 36 44 48 59 67 73 75 98 56 3 36 44 48 56 59 67 73 75 98 ARRAY INSERTION-SORTED: 3 36 44 48 56 59 67 73 75 98 LIST UNSORTED: 53 75 4 46 61 33 8 73 67 75 53 75 4 46 61 33 8 73 67 75 53 75 4 46 61 53 75 4 53 75 53 75 4 46 61 46 61 33 8 73 67 75 33 8 73 33 8 33 8 73 67 75 67 75 LIST MERGE-SORTED: 4 8 33 46 53 61 67 73 75 75 LIST UNSORTED: 66 33 7 91 90 22 7 76 21 5 66 33 7 91 90 22 7 76 21 5 66 33 7 91 90 66 33 7 66 33 66 33 7 91 90 91 90 22 7 76 21 5 22 7 76 22 7 22 7 76 21 5 21 5 LIST MERGE-SORTED: 5 7 7 21 22 33 66 76 90 91 LIST UNSORTED: 95 93 94 47 8 81 24 80 73 98 8 93 94 47 95 81 24 80 73 98 8 24 94 47 95 81 93 80 73 98 8 24 47 94 95 81 93 80 73 98 8 24 47 73 95 81 93 80 94 98 8 24 47 73 80 81 93 95 94 98 8 24 47 73 80 81 93 95 94 98 8 24 47 73 80 81 93 95 94 98 8 24 47 73 80 81 93 94 95 98 8 24 47 73 80 81 93 94 95 98 LIST SELECTION-SORTED: 8 24 47 73 80 81 93 94 95 98 LIST UNSORTED: 42 39 84 19 9 3 2 18 60 21 2 39 84 19 9 3 42 18 60 21 2 3 84 19 9 39 42 18 60 21 2 3 9 19 84 39 42 18 60 21 2 3 9 18 84 39 42 19 60 21 2 3 9 18 19 39 42 84 60 21 2 3 9 18 19 21 42 84 60 39 2 3 9 18 19 21 39 84 60 42 2 3 9 18 19 21 39 42 60 84 2 3 9 18 19 21 39 42 60 84 LIST SELECTION-SORTED: 2 3 9 18 19 21 39 42 60 84