func bubbleSort(_ array : inout [Int]){
for i in 0..<(array.count - 1){
var isSwap = false
for j in 0..<((array.count - i) - 1) {
if array[j] > array[j + 1]{
array.swapAt(j, (j + 1))
isSwap = true
}
}
if isSwap == false {return}
}
}
시간 복잡도 : O(N^2)
func selectionSort(_ array : inout [Int]){
for i in 0..<(array.count - 1){
var minIndex = i
for j in (i + 1)..<array.count {
if array[j] < array[minIndex]{
minIndex = j
}
}
array.swapAt(i , minIndex)
}
}
시간 복잡도 : O(N^2)
func insertionSort(_ array : inout [Int]){
for i in 1..<(array.count){
for j in stride(from: i , to : 0 , by: -1){
if array[j] > array[j - 1]{
array.swapAt(j, (j - 1))
} else {
break
}
}
if isSwap == false {return}
}
}
시간 복잡도 : O(N^2)
func quickSort(_ array: [Int]) -> [Int] {
// base case
guard let first = array.first, array.count > 1 else {return array}
let pivot = first
let _left = array.filter {$0 < pivot}
let _right = array.filter {$0 > pivot}
return quickSort(_left) + [pivot] + quickSort(_right)
}
시간 복잡도 : O(N log N)
func mergeSort(_ array: [Int]) -> [Int] {
if array.count <= 1 {return array}
let center = array.count / 2
let _left = Array(array[0..<center])
let _right = Array(array[center..<array.count])
func merge(_ _left: [Int], _ _right: [Int]) -> [Int]{
var _left = _left
var _right = _right
var result = [Int]()
while !_left.isEmpty && !_right.isEmpty {
if _left[0] < right[0] {
result.append(_left.removeFirst())
} else {
result.append(_right.removeFirst())
}
}
if !_left.isEmpty {
result.append(contentsOf: _left)
}
if !_right.isEmpty{
result.append(contentsOf: _right)
}
return result
}
return merge(mergeSort(_left),mergeSort(_right))
}
시간 복잡도 : O(N log N)