[알고리즘] Swift 정렬

 

Swift의 sort 메서드는 어떻게 동작하는지, 얼마나 효율적인지 궁금할 때가 있다. 이를 알아보기 위해 대표적인 정렬 알고리즘 몇 가지를 알아보고, swift에서는 어떻게 구현되어 있는지 알아보자!

0. 알아둬야 할 것들

0-1. Stable vs Unstable

• Stable
  • 정렬의 결과가 항상 일정(= 기존의 정렬 순서가 유지됨)
• Unstable 
  • 정렬의 결과가 매번 다를 수 있음(=기존의 정렬순서가 유지되지 않음)

 

 - id: 1 / name: Hue / power: 7777 / date: 2024.04.25 10:00
 - id: 2 / name: Jack / power : 8888 / date: 2024.04.25 10:02
 - id: 3 / name: Den / power: 9999 / date: 2024.04.25 10:10
 - id: 4 / name: Bren / power: 8888 / date: 2024.04.25 11:32
 - id: 5 / name: Lon / power: 8888 / date: 2024.04.25 12:34

위 데이터가 있다고 가정했을 때, power을 기준으로 정렬을 한다고 하자. 그럼 어떻게 될까?

 - id: 1 / name: Hue / power: 7777 / date: 2024.04.25 10:00
 - id: 2 / name: Jack / power : 8888 / date: 2024.04.25 10:02
 - id: 4 / name: Bren / power: 8888 / date: 2024.04.25 11:32
 - id: 5 / name: Lon / power: 8888 / date: 2024.04.25 12:34
 - id: 3 / name: Den / power: 9999 / date: 2024.04.25 10:10

 

위처럼 같은 값을 가진 데이터일 땐, 기존 순서를 유지한 채 정렬을 한다. 이를 Stable이라 한다. 반면 기존 순서를 유지하지 않고 바뀌는 경우를 Unstanble이라고 알아두면 된다.

 

 

0-2. In-Place vs Not In-Place

• In-Place
  • 원소의 개수에 비해 충분히 무시할 만한 공간을 더 사용하는 알고리즘
  • 기존 데이터의 메모리 공간에서 정렬이 처리됨
  • 추가적인 메모리 공간 필요 X (Cache Hit Rate 높음)
• Not In-Place
  • 원소의 개수에 비례하여 저장 공간을 더 사용하는 정렬 알고리즘
  • 기존 데이터 이외에 별도의 메모리 공간을 할당함
  • ex) tmp 변수를 이용해 정렬할 때, 추가적인 메모리를 사용해야 함
  • 추가적인 메모리 공간 필요 O (Cache Hit Rate 낮음)

 

 

1. 버블정렬

두 개의 인접한 원소를 비교해 순서에 맞지 않으면 서로 교환하는 정렬 방식

1-1. 구현코드

func bubbleSort<T: Comparable>(_ arr: inout [T]) {
  let size = arr.count
  // i = 정렬된 데이터의 개수
  for i in 0..<size {
    // j = 데이터 순회 Index
      for j in  1..<size-i {
      if arr[j-1] > arr[j] {
        arr.swapAt(j - 1, j)
      }
    }
  }
}


var scores = [100, 32, 40, 1, 5, 7, 9, 14, 14]
bubbleSort(&scores)
print(scores) // 결과값 [1, 5, 7, 9, 14, 14, 32, 40, 100]

 

 

1-2. 특징

시간복잡도: O(N^2)

Stable (기존의 정렬 순서가 유지됨)

In-Place (추가적인 메모리 공간 필요 X)

 

 

1-3. 추가적인 키워드

 

inout

 

기존 메서드에서 파라미터로 값을 넘겨줄 땐 값을 복사한다.(Call-by-value) 하지만 inout 키워드를 사용하면 주소값을 참조하게 된다.(Call-by-Reference) 따라서 복사해서 값을 넘길 땐 O(N) 시간복잡도가 들지만, 주소값을 참조하는 경우에는 O(1)의 시간복잡도가 필요하다. 그런데 여기서 Swift만의 특징이 있는데, inout 키워드를 사용할 땐, Copy-in Copy-out을 한다고 한다. 풀어서 설명해 보자면 복사해서 값을 가져와서, 값을 처리하고 다시 원본에 복사해서 붙여 넣는 형태라고 한다. 그러나 최적화될 땐, Call-by-Reference 형태로 주소값을 참조한다고 한다.

 

 

 

2. 삽입정렬

두 개의 인접한 원소를 비교해 순서에 맞지 않으면 서로 교환하는 정렬 방식

2-1. 구현코드

func insertionSort<T: Comparable>(_ arr: inout [T]) {
  let size = arr.count
  // i = 정렬된 데이터 개수(=정렬된 영역의 데이터 개수)
  for i in 1..<size {
    // j = 데이터 순회 Index
    for j in stride(from: i, to: 0, by: -1) {
      if arr[j-1] > arr[j] {
        arr.swapAt(j - 1, j)
      } else{ break }
    }
  }
}

var scores = [100, 32, 40, 1, 5, 7, 9, 14, 14]
insertionSort(&scores)
print(scores) //  결과 [1, 5, 7, 9, 14, 14, 32, 40, 100]

2-2. 특징

시간복잡도: O(N^2) // 어느 정도 정렬이 되어있는 경우엔 O(N)

Stable (기존의 정렬 순서가 유지됨)

In-Place (추가적인 메모리 공간 필요 X)

 

2-3. 추가적인 키워드

for j in stride(from: 10, to: 0, by: -1) {
     print(j)
}
    // 출력 10 9 8 7 6 5 4 3 2 1
    
for j in stride(from: 10, through: 0, by: -1) {
    print(j)
}
	// 출력 10 9 8 7 6 5 4 3 2 1 0

 여기선 배열의 맨 뒤 index부터 돌아주기 위해 stride라는 메서드를 활용했다. python에서는 사실 stride가 필요 없고 단순히 range(10,0,-1)과 같은 방식으로 구현이 가능하다. 하지만 swift에선 10.. <0 식으로 구현을 하면 런타임에러가 발생한다. 따라서 stride를 활용해야 한다. 

 

 

3. Merge정렬

데이터들을 분할하고 다시 병합하는 정렬방식

3-1. 구현코드

func mergeSort<T: Comparable>(_ arr: inout [T],  _ start: Int, _ end: Int) {
  if end == start + 1 { return } // base condition(개수 1)
  let mid = (start + end) / 2
  mergeSort(&arr, start, mid)
  mergeSort(&arr, mid, end)
  merge(arr: &arr, start, end)

  /// 정렬된 두 배열을 합쳐서 정렬하는 과정
  func merge(arr: inout [T], _ start: Int, _ end: Int) {
    let mid = (start + end) / 2
    var lIndex = start, rIndex = mid

    var temp: [T] = []
    temp.reserveCapacity(end - start)
    for _ in start..<end {
      if lIndex == mid {
        temp.append(arr[rIndex])
        rIndex += 1
      } else if rIndex == end {
        temp.append(arr[lIndex])
        lIndex += 1
      } else if arr[lIndex] <= arr[rIndex] { // stable
        temp.append(arr[lIndex])
        lIndex += 1
      } else {
        temp.append(arr[rIndex])
        rIndex += 1
      }
    }

    for i in start..<end {
      arr[i] = temp[i - start]
    }
  }
}

var scores = [100, 32, 40, 1, 5, 7, 9, 14, 14]
mergeSort(&scores, 0, scores.count)
print(scores) // 결과값 [1, 5, 7, 9, 14, 14, 32, 40, 100]

 

 

3-2. 특징

시간복잡도: O(NlogN)

Stable (기존의 정렬 순서가 유지됨)

Not In-Place (추가적인 메모리 공간 필요 O)

 

3-3. 추가적인 키워드

reserveCapacity는 배열의 들어갈 원소의 개수를 미리 지정해 두는 메서드이다. 예를 들어 10이라고 지정을 한다면 그 배열은 10개의 요소를 가지고 있을 것이다. 만약 이때 append를 한다면 다시 10개가 더 들어가 원소의 개수가 20인 배열이 된다.

 

4. Quick 정렬

pivot을 기준으로 작거나 같은 값, 큰 값으로 데이터를 재귀적으로 분리하는 정렬방식

4-1. 구현코드

func mergeSort<T: Comparable>(_ arr: inout [T],  _ start: Int, _ end: Int) {
  if end == start + 1 { return } // base condition(개수 1)
  let mid = (start + end) / 2
  mergeSort(&arr, start, mid)
  mergeSort(&arr, mid, end)
  merge(arr: &arr, start, end)

  /// 정렬된 두 배열을 합쳐서 정렬하는 과정
  func merge(arr: inout [T], _ start: Int, _ end: Int) {
    let mid = (start + end) / 2
    var lIndex = start, rIndex = mid

    var temp: [T] = []
    temp.reserveCapacity(end - start)
    for _ in start..<end {
      if lIndex == mid {
        temp.append(arr[rIndex])
        rIndex += 1
      } else if rIndex == end {
        temp.append(arr[lIndex])
        lIndex += 1
      } else if arr[lIndex] <= arr[rIndex] { // stable
        temp.append(arr[lIndex])
        lIndex += 1
      } else {
        temp.append(arr[rIndex])
        rIndex += 1
      }
    }

    for i in start..<end {
      arr[i] = temp[i - start]
    }
  }
}

var scores = [100, 32, 40, 1, 5, 7, 9, 14, 14]
mergeSort(&scores, 0, scores.count)
print(scores) // 결과값 [1, 5, 7, 9, 14, 14, 32, 40, 100]

 

4-2. 특징

시간복잡도: O(NlogN)

Stable (기존의 정렬 순서가 유지되지 않음)

In-Place (추가적인 메모리 공간 필요 X)

 

 

4-3. 추가적인 키워드

 quickSort는 In-Place로만 구현이 돼야 해당 정렬의 장점을 살릴 수 있다고 한다.(속도의 빠름) 따라서 따로 배열을 만들어서 Not In-Place 하게 구현하면 안 된다.

 

5. Swift의 sort

2018년도까지 swift의 sort는 Intro Sort 방식을 사용하고 있었다고 한다. 그러나 이후에는 Tim Sort를 사용하고 있다고 밝혔다. (swift github에)

	Intro Sort	Tim Sort
구성	Quick / Heap / Insertion	Merge / Insertion
Time Complexity	O(NlogN)	O(N) ~ O(NlogN)

 

 

 

 

6. 정리

	Bubble	Insertion	Merge	Quick
Time Complexity	O(N^2)	O(N)~O(N^2)	O(NlogN)	O(NlogN) ~ O(N^2)
Stable	O	O	O	X
In-Place	O	O	X	O