Sorting Algorithm in Swift: Insertion Sort(Part — 2)
Let’s start with next algorithm Insertion Sort. If you want to explore on Bubble sort then please refer to Part-1 session of this series.
Insertion Sort:
Insertion sort is a sorting technique which follow below steps:
- First put unsorted number in an array.
- Insert array to new number array
- Then pick any number from the pile, insert that number to new array and start comparing that number from the last value of new array.
- if picked number from array is less than the number from the new array then simply swap the number.
- Repeat the process until complete arrays is sorted.
Let’s take and example
[3,4,5,1,0,8,1]
Below are sorting steps
[3]|[4,5,1,0,8,1]
[3,4]|[5,1,0,8,1]
[3,4,5]|[1,0,8,1]
[1,3,4,5]|[0,8,1]
[0,1,3,4,5]|[8,1]
[0,1,3,4,5,8]|[1]
[0,1,3,4,5,8,1]
Code snippet:
/// Performs the Insertion sort algorithm to a given array////// - Parameter array: the array to be sorted, conatining elements that conform to the Comparable protocol/// - Returns: a sorted array containing the same elementsfunc insertionSort<T: Comparable>(_ array: [T]) -> [T] { var sortedArray = array for index in 1..<sortedArray.count { var currentIndex = index let temp = sortedArray[currentIndex] while currentIndex > 0 && temp < sortedArray[currentIndex - 1] { sortedArray[currentIndex] = sortedArray[currentIndex - 1] currentIndex -= 1 } sortedArray[currentIndex] = temp} return sortedArray}
Usage:
print(insertionSort([3,4,5,1,0,8,1])
Complexities:
Best Case: O(n) When arrays is in sorted order
Worst Case: O(n2) when we try to sort ascending order of array but actually array is in Descending order.
Average Case: O(n2) When try to sort jumbled order value array. Insertion sort is actually very fast for sorting small arrays.
When to use
- Insertion sort is actually very fast for sorting small arrays. Some library prefer to use Insertion sort for small array(count less then 10)
- Complexity is not a concern