1. 정렬(Sort)
Sort
•
특정 기준을 적용하여 데이터를 나열하는 알고리즘
•
오름차순 정렬(갈수록 커지는 것)
•
내림차순 정렬(갈수록 작아지는 것)
2. 기본적인 정렬 알고리즘의 종류
2.1. 선택정렬(Selection Sort)
•
오름차순 정렬이라고 가정했을 때, 최솟값을 맨 앞으로 이동시킴으로써 정렬합니다.(오름차순)
•
왼쪽은 정렬이 모두 되었다고 보장할 수 있습니다.
•
O(N^2)의 시간복잡도를 가지게 됩니다.
for i in 0...N - 1 {
var index: Int = i
for j in (i + 1)...N {
if data[index] > data[j] {
index = j
}
}
let temp: Int = data[index]
data[index] = data[i]
data[i] = temp
}
Swift
복사
2.2. 삽입정렬(Insertion Sort)
•
원소를 차례대로 정렬된 배열에 삽입시킴으로써 정렬하는 알고리즘 입니다.
•
왼쪽은 정렬이 모두 되었다고 보장할 수 있습니다.
•
O(N^2)의 시간복잡도를 가지게 됩니다.
for i in 1...(N - 1) {
for j in stride(from: i, to: 0, by: -1) {
if data[j] < data[j - 1] {
let temp: Int = data[j]
data[j] = data[j - 1]
data[j - 1] = temp
}
}
}
Swift
복사
2.3. 버블정렬(Bubble Sort)
•
오름차순 정렬이라고 가정했을 때, 인접한 원소를 비교하여 큰 수를 뒤로 보냄으로써 정렬하는 알고리즘 입니다.
•
오른쪽은 정렬이 모두 되었다고 보장할 수 있습니다.
•
O(N^2)의 시간복잡도를 가지게 됩니다.
for i in stride(from: N - 1, to: 0, by: - 1) {
for j in 0...(i - 1) {
if data[j] > data[j + 1] {
let temp: Int = data[j]
data[j] = data[j + 1]
data[j + 1] = temp
}
}
}
Swift
복사