Sorting

Introduction The selection sort is an in-place comparison sorting algorithm. It’s similar to bubble sort in that it works by repeatedly swapping items in a list and not very efficient on larger lists. source Code Example func selectionSort(_ array: [Int]) -> [Int] { var A = array let N = array.count for i in 0 ..< N { var jMin = i for j in (i + 1) ..< N { if A[j] < A[jMin] { jMin = j } } if jMin != i { let tmp = A[i] A[i] = A[jMin] A[jMin] = tmp } } return A } Implementation For each index: Set jMin index to the current index For each index from i + 1 to the end of the list: If the element at inner index j is less than the element at index jMin, set jMin to j If jMin does not equal i, swap the element at the current index i with the element at index jMin Time/Space Complexity Time complexity: O(N^2) Space complexity: O(1) auxiliary ...

Introduction The quick sort is an efficient sorting algorithm commonly used widely in production. Quick sort is a divide-and-conquer algorithm. It works by selecting a pivot from the array and partitioning the other elements into two subarrays. source Code example // Sorts a (portion of an) array, divides it into partitions, then sorts those func quickSort(array: inout [Int], low: Int, high: Int) { // Ensure indices are in correct order if low < high { // Partition array and get the pivot index let p = partition(array: &array, low: low, high: high) // Sort the two partitions quickSort(array: &array, low: low, high: p - 1) // Left side of pivot quickSort(array: &array, low: p + 1, high: high) // Right side of pivot } } // Divides array into two partitions func partition(array: inout [Int], low: Int, high: Int) -> Int { let pivot = array[high] // Choose the last element as the pivot // Temporary pivot index var i = low for j in low ..< high { // If the current element is less than or equal to the pivot if array[j] <= pivot { // Swap the current element with the element at the temporary pivot index let tmp = array[i] array[i] = array[j] array[j] = tmp // Move the temporary pivot index forward i += 1 } } // Swap the pivot with the last element let tmp = array[i] array[i] = array[high] array[high] = tmp return i } Implementation quickSort Ensure that the low and high indices are in the correct order. Partition the input list using the partition function. Recursively call quickSort on the left side of the pivot. Recursively call quickSort on the right side of the pivot. partition Choose the last element as the pivot. Set i to low. For each j from low to high (not inclusive), compare if the current element is less than or equal to the pivot: 3.1 Swap the element at index i with the element at index j. 3.2 Increment i by 1. Swap the element at index i with the last element. Return i. Time/Space complexity Time complexity: O(N^2) Space complexity: O(N) ...

Introduction The insertion sort algorithm builds a sorted list one item at a time by comparison. It is more efficient on small datasets but much less efficient on larger ones. source source Code Example func insertionSort(_ array: [Int]) -> [Int] { var A = array for i in 0 ..< A.count { var j = i while j > 0 && A[j - 1] > A[j] { let tmp = A[j] A[j] = A[j - 1] A[j - 1] = tmp j -= 1 } } return A } Implementation For each index in the input array: Set the j variable to i. Loop while j is greater than 0 and the element at index j - 1 is greater than the element at index j: Swap the elements at index j and j - 1. Decrement j by 1. Why use Insertion Sort? Fast for small data sets. More efficient in practice than most other algorithms, such as selection sort or bubble sort. Adaptive: Efficient for datasets that are already substantially sorted; the time complexity is O(kn) when each element in the input is no more than k places away from its sorted position. Stable: Does not change the relative order of elements with equal keys. In-place: Only requires O(1) of additional memory space. Online: Can sort a list as it receives it. Time/Space Complexity Time: O(N^2) Space: O(1) (in-place) Thank you for reading! 😊

What is Merge Sort? Merge sort is a recursive algorithm that uses the divide and conquer algorithm design paradigm to find the solution. source The merge sort conceptually consists of two separate functions: mergeSort and merge. It works as follows: Divide the unsorted list into two equal halves. Recursively sort the two halves. Merge the two halves to form a sorted array. There are multiple implementations of merge sort. I will be focusing on the top-down implementation using lists. ...

What is the Bubble Sort Algorithm? The bubble sort is a basic sorting algorithm named after the way elements progressively “bubble up” to the top of the list. source Code Example func bubbleSort(_ array: [Int]) -> [Int] { var A = array var N = array.count var swapping = true while swapping { swapping = false for i in 1 ..< N { if A[i - 1] > A[i] { let tmp = A[i - 1] A[i - 1] = A[i] A[i] = tmp swapping = true } } N -= 1 } return A } Implementation The bubble sort uses an loop and swapping property to control it behaviour. Inside the loop, it iterates over all elements, comparing the current and next elements. If the current element is greater than the next, it swaps them. ...