[자료구조][알고리즘] 정렬

Stable vc Unstable

'정렬을 했을 때 같은 값을 가진 원소들의 순서가 유지되는가?' 를 기준으로,
정렬을 했을 때 같은 값을 가진 원소들의 순서가 항상 유지되는 경우가 Stable이다. 즉, 정렬 결과가 항상 일정하다.

대표적인 알고리즘들
Stable Sorting 알고리즘:

• Insertion Sort
• Merge Sort
• Bubble Sort
• Counting Sort

Unstable Soring 알고리즘:

• Selection sort
• Heap Sort
• Shell Sort
• Quick Sort

In-Place vc Not In-Place

In-Place 는 원소의 개수에 비해 충분히 무시할만한 공간을 더 사용하는 알고리즘이다. 추가적인 메모리 공간이 필요 없으며 Not In-Place에 비해 Cache Hit Rate이 높다.

대표적인 In-Place 알고리즘

• Insertion Sort
• Selection Sort
• Bubble Sort
• Shell Sort
• Heap Sort
• Quick Sort(정렬 알고리즘-4.2: 정의에 따라서 Not in place sorting으로 볼 수도 있으나 흔히 In-place로 본다.)

Not In-Place 는 원소의 개수에 비례하여 저장 공간을 더 사용하는 정렬 알고리즘이다. 추가적인 메모리 공간이 필요하며 In-Place에 비해 Cache Hit Rate이 낮다.

대표적인 Not In-Place 알고리즘

• Merge Sort
• Counting Sort
• Radix Sort
• Bucket Sort

Bubble Sort

두 개의 인접한 원소를 비교해 순서에 맞지 않으면 서로 교환하는 정렬 방식.
바로 앞, 뒤의 요소를 비교하고 swap 하는 방식으로 정렬을 진행하며 오름차순 정렬이라고 가정할 시 가장 큰 요소가 제일 먼저 정렬 되는 특징이 있다.

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

시간 복잡도는 항상 O(n^2)으로, 구현 가능한 가장 느린 정렬 알고리즘이다.

번외로, 여기서 inout을 쓰는 이유는 . . .
Swift에서 함수에 변수를 전달하면 일반적으로 변수의 복사본이 함수로 전달된다. 그래서 함수 내에서 변수를 수정해도, 원본 변수는 변하지 않는다. 하지만 'inout' 키워드를 사용하면 변수의 복사본이 아니라 직접 변수를 전달할 수 있다. 그래서 함수 내에서 변수를 수정하면, 원본 변수도 같이 변경되는 셈이다. 이렇게 하면 함수가 변수를 직접 수정할 수 있다. 변수를 복사하지 않고 직접 참조하기 때문에, 직접 복사하는 경우보다 시간복잡도 측면에서 효율적이다.

Insertion Sort

Insertion Sort는 각 요소를 이미 정렬된 부분 리스트에 삽입하여 최종적으로 정렬된 리스트를 만드는 과정을 반복한다.
처음에는 첫 번째 요소를 정렬된 부분 리스트로 간주하고, 다음 요소부터 순서대로 정렬된 부분 리스트에 삽입하면서 정렬을 완성한다.

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] < arr[j - 1] {
                arr.swapAt(j, j - 1)
            } else {
                break
            }
        }
    }
}

마찬가지로 O(n) = n^2의 시간복잡도를 가지게 된다.

Merge Sort

주어진 리스트를 반으로 나눈 뒤 각각을 재귀적으로 정렬하고, 정렬된 두 개의 리스트를 합쳐서 전체 리스트를 정렬하는 알고리즘이다.

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]
    }
  }
}

Quick Sort

주어진 배열을 특정한 값인 pivot을 기준으로 두 개의 부분 배열로 분할하고 각 부분 배열을 재귀적으로 정렬하는 방식으로 동작한다.
pivot을 기준으로 작은 값은 pivot 왼쪽으로, 큰 값은 pivot 오른쪽으로 이동시킨다. 분할된 부분 배열은 독립적으로 정렬되며, 이러한 과정을 반복하여 전체 배열이 정렬될 때까지 진행된다.

func quickSort<T: Comparable>(_ arr: inout [T],
                              _ start: Int,
                              _ end: Int) {
  if end <= start + 1 { return }
  let pivot = arr[start]
  var left = start + 1, right = end - 1

  while true {
    while left <= right && arr[left] <= pivot { left += 1 } // pivot 보다 큰 값
    while left <= right && arr[right] > pivot { right -= 1 } // pivot 보다 작거나 작은 값
    if left > right { break }
    arr.swapAt(left, right)
  }
  arr.swapAt(start, right)

  quickSort(&arr, start, right)
  quickSort(&arr, right + 1, end)
}

Quick Sort는 Unstable하다. pivot의 선택 및 배열의 분할 과정에서 같은 값의 요소들의 상대적인 순서가 변경될 수 있기 때문이다.

Swift에서 사용하는 Sort는 뭘까?

TimSort를 사용한다. TimSort는 merge+insertion이다.