정렬 알고리즘(버블 정렬, 삽입정렬, 선택정렬)

버블 소트 (bubble sort)

• 인접한 원소의 비교를 통해 정렬하는 방법
• 오름차순으로 정렬할 경우, 매 비교마다 가장 큰 원소를 끝으로 보냄
• 시간 복잡도 O(n^2)
  • n-1, n-1, n-2, n-3 ...1 -> n(n-1)/2
• 구현은 단순하지만, 시간이 오래걸려 자료의 개수가 많아질수록 비효율적임.
• 최적/최악의 경우에도 비교 횟수는 같다
• 정렬을 위한 추가 배열 필요 없음
• 안정정렬

var arr: [Int] = [4, 5, 6, 2, 9, 1, 8]

for i in (0...(arr.count-1)).reversed() {
    for j in 0...i {
        if(arr[j] > arr[i]) {
            let tmp = arr[j]
            arr[j] = arr[i]
            arr[i] = tmp
        }
    }
}

삽입 정렬 (insert sort)

• 이미 정렬되어 있는 배열에, 정렬할 원소를 삽입하는 방법
• 배열의 앞에서부터 차례로 정렬
• 정렬을 위한 추가 배열 필요 없음
• 구현은 단순하지만, 시간이 오래걸려 자료의 개수가 많아질수록 비효율적임.
• 안정정렬
• 시간 복잡도 O(n^2)
  • 처음 배열이 오름차순으로 정렬되어 있는 경우 (최적) : O(n)
  • 처음 배열이 내림차순으로 정렬되어 있는 경우 (최악) : O(n^2)
• 어느정도 정렬이 되어있는 배열에서 사용하기 좋다

var arr: [Int] = [4, 5, 6, 2, 9, 1, 8]

for i in 1...arr.count-1 {
    var e = i
    for j in (0...i-1).reversed() {
        if arr[e] < arr[j] {
            let tmp = arr[e]
            arr[e] = arr[j]
            arr[j] = tmp
            e = j
        } else {
            break
        }
    }
}

선택 정렬(select sort)

• 정렬되어 있지 않은 원소 중, 최솟값을 골라 정해진 위치에 넣는 방법
  • 삽입정렬 : 선택할 원소는 정해져 있음, 놓을 위치는 정해져 있지 않음
  • 선택정렬 : 선택할 원소는 정해져 있지 않음, 놓을 위치는 정해져 있음
• 최적/최악의 경우에도 비교 횟수는 같다
• 정렬을 위한 추가 배열 필요 없음
• 시간 복잡도 O(n^2)
• 불안정 정렬
  • 최솟값을 고른 후, 맨 앞의 원소와 swap하는 과정에서, 처음의 인덱스 순서가 흐트러질 수 있기 때문

var arr: [Int] = [4, 5, 6, 2, 9, 1, 8]

for i in 0...arr.count-1 {
    var min = i
    for j in i...arr.count-1 {
        if arr[j] < arr[min] {
            min = j
        }
    }
    let tmp = arr[i]
    arr[i] = arr[min]
    arr[min] = tmp
}