# Sorting In Swift

SiDarthVader

31.7K views

### What is Insertion Sort?

Insertion Sort is a sorting algorithm that picks an element from the array (usually the first), takes it out of the index it is currently in, and 'inserts' it in the correct position within a 'sorted sublist'. The elements swap indexes if the first element has a greater value than the second element. If not, the iteration continues with the second element & third element to check if they are in ascending order, while the first element has become a part of the 'sorted sublist'. This process of comparing adjacent elements continues throughout the array until the end has been reached.

```
[3,4,5,1,0,8,1]
[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]
```

Best-Case Complexity: Ðž(n) Worst-Case Complexity: Ðž(n^2)

```
for i from 1 to N
key = a[i]
j = i - 1
while j >= 0 and a[j] > key
a[j+1] = a[j]
j = j - 1
a[j+1] = key
```

Add the code to sort the array using the Insertion Sort algorithm

1

2

3

4

5

6

7

8

struct insertionSort {

func insertionSort(_ array: [Int]) -> [Int] {

}

}

## Stuck? Check the solution here

```
func insertionSort(_ array: [Int]) -> [Int] {
var arr = array
for x in 1..<arr.count {
var y = x
while y > 0 && arr[y] < arr[y - 1] {
swap(&arr[y - 1], &arr[y])
y -= 1
}
}
return arr
}
```

Create your playground on Tech.io

This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.

Suggested playgrounds