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:

1. First put unsorted number in an array.
2. Insert array to new number array
3. 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.
4. if picked number from array is less than the number from the new array then simply swap the number.
5. 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]

Insertion Sort

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 elements
func 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

Happy Coding

Happy Coding !!!!