forked from suleturp/swift-algorithm-club
-
Notifications
You must be signed in to change notification settings - Fork 1
/
InsertionSort.swift
41 lines (38 loc) · 1.14 KB
/
InsertionSort.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/// Performs the Insertion sort algorithm to a given array
///
/// - Parameters:
/// - array: the array of elements to be sorted
/// - isOrderedBefore: returns true if the elements provided are in the corect order
/// - Returns: a sorted array containing the same elements
func insertionSort<T>(_ array: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {
guard array.count > 1 else { return array }
var a = array
for x in 1..<a.count {
var y = x
let temp = a[y]
while y > 0 && isOrderedBefore(temp, a[y - 1]) {
a[y] = a[y - 1]
y -= 1
}
a[y] = temp
}
return a
}
/// Performs the Insertion sort algorithm to a given array
///
/// - Parameter array: the array to be sorted, containing elements that conform to the Comparable protocol
/// - Returns: a sorted array containing the same elements
func insertionSort<T: Comparable>(_ array: [T]) -> [T] {
guard array.count > 1 else { return array }
var a = array
for x in 1..<a.count {
var y = x
let temp = a[y]
while y > 0 && temp < a[y - 1] {
a[y] = a[y - 1]
y -= 1
}
a[y] = temp
}
return a
}