Swiftでクイックソートを実装する
環境
sh$swift --version
swift-driver version: 1.82.2 Apple Swift version 5.9 (swiftlang-5.9.0.114.10 clang-1500.0.29.1)
Target: arm64-apple-macosx14.0
モチベーション
実装したことが無い気がするのでやっておく
簡単のため配列の長さは奇数で。
1回目
swiftfunc solve(_ array: [Int]) -> [Int] {
let pivot = array[array.count / 2]
var left: [Int] = []
var right: [Int] = []
for (i, a) in array.enumerated() {
if i == array.count / 2 {
continue
}
if a <= pivot {
left.append(a)
} else {
right.append(a)
}
}
left.append(pivot)
let newArray = left + right
var success = true
let newArrayCount = newArray.count
for i in newArray.indices {
if i == newArrayCount - 1 {
break
}
if newArray[i] <= newArray[i + 1] {
continue
} else {
success = false
break
}
}
if success {
return newArray
} else {
return solve(newArray)
}
}
let array = [3, 7, 8, 5, 2, 1, 9, 5, 4]
let answer = solve(array)
print(answer) // [1, 2, 3, 4, 5, 5, 7, 8, 9]
2回目
swiftfunc solve(_ array: [Int]) -> [Int] {
let pivotIndex = array.count / 2
let pivot = array[pivotIndex]
var left: [Int] = []
var right: [Int] = []
for (i, a) in array.enumerated() {
if i == pivotIndex {
continue
}
if a <= pivot {
left.append(a)
} else {
right.append(a)
}
}
left.append(pivot)
let newArray = left + right
let newArrayCount = newArray.count
for i in newArray.indices {
if i == newArrayCount - 1 {
break
}
if newArray[i] > newArray[i + 1] {
return solve(newArray)
}
}
return newArray
}
let array = [3, 7, 8, 5, 2, 1, 9, 5, 4]
let answer = solve(array)
print(answer) // [1, 2, 3, 4, 5, 5, 7, 8, 9]
indexを見る必要があって汚くなってしまった