버블 정렬

  • 버블 정렬은 인접한 값을 비교해서 더 큰 수를 뒤로 보내 정렬하는 알고리즘이다.
  • 원리 자체가 굉장히 간단하기 때문에 구현도 간편하지만, 시간 복잡도가 O(N^2) 이기 때문에 성능은 떨어진다.
  • 시간 복잡도가 O(N^2)인 이유는 배열의 모든 요소를 한번씩 비교하면서 교환까지 이루어지기 때문이다.
  • 버블 정렬을 Swift로 구현하자면 다음과 같다.
func bubbleSort(arr: [Int]) -> [Int] {
    var arr = arr
    var totalLength = arr.count - 1
    
    while totalLength != 0 {
        for i in 0...totalLength {
            let nextIndex = i + 1
            if nextIndex <= totalLength {
                if arr[i] > arr[nextIndex] {
                    let small = arr[nextIndex]
                    arr[nextIndex] = arr[i]
                    arr[i] = small
                }
                if nextIndex == totalLength {
                    totalLength -= 1
                }
            }
        }
    }
    
    return arr
}

선택 정렬

  • 선택 정렬은 배열의 모든 요소를 비교하면서 가장 작은 수를 가장 앞으로 보내어 정렬하는 알고리즘이다.
  • 버블 정렬과 마찬가지로 배열의 모든 요소를 비교하지만, 교환은 단 한번만 이루어진다.
  • 그래서 버블 정렬보다 우위에 있지만 빅 오 표기법상 상수를 무시하여 같은 O(N^2) 시간 복잡도를 가진다.
  • Swift로 구현하면 다음과 같다.
func selectionSort(arr: [Int]) -> [Int] {
    var arr = arr
    
    var startPosition = 0
    
    while startPosition != (arr.count - 1) {
        var lowerNumberIndex: Int!
        
        for i in startPosition...(arr.count - 1) {
            if i == startPosition {
                lowerNumberIndex = i
            } else {
                if arr[i] < arr[lowerNumberIndex] {
                    lowerNumberIndex = i
                }
                if i == (arr.count - 1) {
                    let temp = arr[startPosition]
                    arr[startPosition] = arr[lowerNumberIndex]
                    arr[lowerNumberIndex] = temp
                    startPosition += 1
                }
            }
        }
    }
    
    return arr
}