Engineering Computation Workshop 7 === ###### tags: `comp20005` `workshop` `c` --- ### Assignment, More Arrays & Sorting --- ### Sorting Algorithms #### What you need to know - Iterative Selection Sort - Iterative Insertion Sort - Recursive Selection Sort - Recursive Insertion Sort --- ### Iterative Selection Sort ```cpp void selection_sort(int arr[], int n) { int i, j, min_idx; // One by one move boundary of unsorted subarray for (i = 0; i < n-1; i++) { // Find the minimum element in unsorted array min_idx = i; for (j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; // Swap the found minimum element with the first element swap(&arr[min_idx], &arr[i]); } } ``` --- ### Recursive Selection Sort ```cpp void selection_sort(int *A, int n) { // return early if we have the case n < 2 (already sorted) if (n < 2) return; // store largest value index as we go int largest = 0; for (int i=0;i<n;i++){ largest = A[largest] > A[i] ? largest : i; // update index of largest } swap(&(A[largest]), &(A[n-1])); // swap the largest and the last element selection_sort(A, n-1); // recurse with array size - 1 } ``` --- ### Iterative Insertion Sort ```cpp void insert_sort(int A[], int n) { int key, j; for (int i = 1; i < n; i++) { key = A[i] j = i-1; // Move elements that are greater than our key to the right one index while (j >= 0 && A[j] > key) { A[j+1] = A[j]; j -= 1; } A[j+1] = key; } } ``` --- ### Recursive Insertion Sort ```cpp void insert_sort(int A[], int n) { if (n<2) return; insert_sort(A, n-1); // Insert last element at its correct position int last = A[n-1]; int j = n-2; // Move elements of arr[0..i-1], that are greater than key while (j >= 0 && A[j] > last) { A[j+1] = A[j]; j--; } A[j+1] = last; } ``` --- ### Assignment Examples --- ### Workshop Question Discussion ---