DSA - Sorting - Selection Sort

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 !...

October 23, 2024 · 1 min · Dmytro Chumakov

DSA - Sorting - Quick Sort

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 ....

October 19, 2024 · 2 min · Dmytro Chumakov

DSA - Sorting - Insertion Sort

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....

October 15, 2024 · 2 min · Dmytro Chumakov

DSA - Sorting - Merge Sort

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....

October 14, 2024 · 2 min · Dmytro Chumakov

DSA - Sorting - Bubble Sort

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....

October 11, 2024 · 1 min · Dmytro Chumakov