정렬된 배열

정렬된 배열은 항상 낮은 값에서 높은 값으로 정렬된 배열이다. 새로운 항목을 추가할 때마다 정렬된 위치에 삽입된다.

정렬된 배열은 데이터를 정렬된 상태로 유지하면서 새로운 항목을 비교적 드물게 추가할 때 유용하다. 이런 경우 전체 배열을 다시 정렬하는 것보다 더 빠르다. 그러나 배열을 자주 변경해야 한다면 일반 배열을 사용하고 수동으로 정렬하는 것이 더 빠를 수 있다.

구현은 매우 기본적이다. Swift의 내장 배열을 감싼 간단한 래퍼이다:

public struct OrderedArray<T: Comparable> {
  fileprivate var array = [T]()

  public init(array: [T]) {
    self.array = array.sorted()
  }

  public var isEmpty: Bool {
    return array.isEmpty
  }

  public var count: Int {
    return array.count
  }

  public subscript(index: Int) -> T {
    return array[index]
  }

  public mutating func removeAtIndex(index: Int) -> T {
    return array.remove(at: index)
  }

  public mutating func removeAll() {
    array.removeAll()
  }
}

extension OrderedArray: CustomStringConvertible {
  public var description: String {
    return array.description
  }
}

보는 바와 같이, 모든 메서드는 내부 array 변수의 해당 메서드를 호출한다.

남은 것은 insert() 함수이다. 다음은 초기 구현이다:

  public mutating func insert(_ newElement: T) -> Int {
    let i = findInsertionPoint(newElement)
    array.insert(newElement, at: i)
    return i
  }

  private func findInsertionPoint(_ newElement: T) -> Int {
    for i in 0..<array.count {
      if newElement <= array[i] {
        return i
      }
    }
    return array.count  // 끝에 삽입
  }

헬퍼 함수 findInsertionPoint()는 배열 전체를 순회하며 새로운 요소를 삽입할 적절한 위치를 찾는다.

참고: array.insert(... atIndex: array.count)는 새로운 객체를 배열의 끝에 추가하므로, 적절한 삽입 위치를 찾지 못한 경우 array.count를 인덱스로 반환하면 된다.

다음은 플레이그라운드에서 테스트하는 방법이다:

var a = OrderedArray<Int>(array: [5, 1, 3, 9, 7, -1])
a              // [-1, 1, 3, 5, 7, 9]

a.insert(4)    // 인덱스 3에 삽입
a              // [-1, 1, 3, 4, 5, 7, 9]

a.insert(-2)   // 인덱스 0에 삽입
a.insert(10)   // 인덱스 8에 삽입
a              // [-2, -1, 1, 3, 4, 5, 7, 9, 10]

배열의 내용은 항상 낮은 값에서 높은 값으로 정렬된다.

안타깝게도 현재 findInsertionPoint() 함수는 다소 느리다. 최악의 경우 배열 전체를 스캔해야 한다. 이진 검색을 사용해 삽입 위치를 찾으면 속도를 높일 수 있다.

다음은 새로운 버전이다:

  private func findInsertionPoint(_ newElement: T) -> Int {
    var startIndex = 0
    var endIndex = array.count

    while startIndex < endIndex {
        let midIndex = startIndex + (endIndex - startIndex) / 2
        if array[midIndex] == newElement {
            return midIndex
        } else if array[midIndex] < newElement {
            startIndex = midIndex + 1
        } else {
            endIndex = midIndex
        }
    }
    return startIndex
  }

일반 이진 검색과의 큰 차이점은 값을 찾지 못했을 때 nil을 반환하는 대신, 요소가 있어야 할 배열 인덱스를 반환한다는 것이다. 이 위치에 새로운 객체를 삽입한다.

이진 검색을 사용해도 insert()의 최악의 경우 시간 복잡도는 변하지 않는다. 이진 검색 자체는 O(log n) 시간이 걸리지만, 배열 중간에 새로운 객체를 삽입하는 작업은 여전히 메모리에서 나머지 요소들을 이동시켜야 한다. 따라서 전체 시간 복잡도는 여전히 **O(n)**이다. 그러나 실제로는 이 새로운 버전이 확실히 더 빠르며, 특히 큰 배열에서 더욱 그렇다.

보다 완전하고 프로덕션 준비가 된 SortedArray는 Ole Begemann이 제공한다. 관련 글은 장단점을 설명한다.

Swift Algorithm Club을 위해 Matthijs Hollemans가 작성함