정렬 알고리즘

정렬 알고리즘

원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘

Stable & Unstable

• stable : 동일한 key값을 갖고 있는 원소들의 순서가 보존 되는 것
• unstable : 동일한 key값을 갖고 있는 원소들의 순서가 보존 되지 않는 것

Inplace & Not-In-Place

• in-place 알고리즘
  • 입력 데이터를 수정하면서 정렬을 수행
  • 즉, 추가적인 메모리 공간을 사용하지 않고, 주어진 입력 데이터 내부에서 직접적으로 작업을 수행
• not-in-place
  • 추가적인 메모리 공간을 사용하여, 입력 데이터를 복사하고 정렬을 수행

 

1. 버블 정렬

• 두 개의 인접한 원소를 비교해 순서에 맞게 교환하여 정렬
• 각 회차가 끝날 때마다 가장 큰 or 가장 작은 수의 자리가 확정

func bubbleSort<T: Comparable>(_arr: inout [T]) {
		for i in 0..<arr.count {
			for j in 1..<arr.count - i {
				if arr[j-1] > arr[j] {
					arr.swapAt(j-1, j)
				}
			}
		}
}

• O(N^2)의 시간 복잡도
• 추가적인 배열을 사용하지 않음 ⇒ in-place
• 같은 값에 대해 순서 보존 ⇒ stable

 

 

2. 삽입

• 앞에서부터 정렬된 부분과 비교하여, 자신의 위치를 찾아 삽입
• 회차를 돌 때마다 정렬된 영역에 원소가 하나씩 추가

func insetionSort<T: Comparable>(_ arr: input [T]) {
	 for i in 1..<array.count {
        let key = array[i]
        var j = i - 1
        // key보다 큰 원소들은 한 칸씩 뒤로 이동
        while j >= 0 && array[j] > key {
            array[j+1] = array[j]
            j -= 1
        }
        // key가 들어갈 위치 확정
        array[j+1] = key
    }

}

• (정렬 시)O(N) ~ O(N^2)의 시간복잡도
• 추가적인 배열을 사용하지 않음 => in-place
• 같은 값에 대해 순서 보존 => stable

 

 

3. 병합

• Devide & Conquer 방식으로 설계된 알고리즘
• 하나의 배열을 입력받고, 연산 중 두 개의 배열로 계속 쪼개 나가면서 합침

• 분할은 배열의 크기가 1보다 작거나 같을 때까지 반복
• 시간 복잡도 - O(logN)

  func mergeSort<T: Comparable>(_ array: [T]) -> [T] {
      guard array.count > 1 else { return array }  // 요소가 1개 이하라면 정렬 필요 없음
      
      let middle = array.count / 2
      let leftArray = mergeSort(Array(array[..<middle]))  // 왼쪽 반 정렬
      let rightArray = mergeSort(Array(array[middle...])) // 오른쪽 반 정렬
      
      return merge(leftArray, rightArray)
  }
  
  func merge<T: Comparable>(_ left: [T], _ right: [T]) -> [T] {
      var sortedArray: [T] = [] // 새로운 배열 생성 후 사용
      var leftIndex = 0, rightIndex = 0
      
      // 두 배열을 비교하면서 작은 값을 결과 배열에 추가
      while leftIndex < left.count && rightIndex < right.count {
          if left[leftIndex] < right[rightIndex] {
              sortedArray.append(left[leftIndex])
              leftIndex += 1
          } else {
              sortedArray.append(right[rightIndex])
              rightIndex += 1
          }
      }
      
      // 남은 요소들 추가
      sortedArray.append(contentsOf: left[leftIndex...])
      sortedArray.append(contentsOf: right[rightIndex...])
      
      return sortedArray
  }
  
  // 테스트
  let numbers = [8, 3, 5, 2, 9, 1, 6, 4, 7]
  print(mergeSort(numbers))  // [1, 2, 3, 4, 5, 6, 7, 8, 9]
  

  • 새로운 배열 생성 후 사용 ⇒ not-in-place
  • stable ⇒ 같은 값일 때, 왼쪽먼저

 

 

4. 퀵

• pivot을 기준으로 작거나 같은 값, 큰 값으로 데이터를 재귀적으로 분리하는 방식
• 합병 정렬과 마찬가지로 divide & conquer, 재귀함수를 통해 구현 가능
• 각회차 종료시 pivot의 자리 확정

func quickSortInPlace(_ arr: inout [Int], low: Int, high: Int) {
    if low < high {
        let pivotIndex = partition(&arr, low: low, high: high)
        quickSortInPlace(&arr, low: low, high: pivotIndex - 1) // 왼쪽 정렬
        quickSortInPlace(&arr, low: pivotIndex + 1, high: high) // 오른쪽 정렬
    }
}

func partition(_ arr: inout [Int], low: Int, high: Int) -> Int {
    let pivot = arr[high] // 마지막 요소를 피벗으로 선택
    var i = low
    
    for j in low..<high {
        if arr[j] < pivot { 
            arr.swapAt(i, j)
            i += 1
        }
    }
    arr.swapAt(i, high)
    return i
}

var numbers = [8, 3, 7, 4, 9, 1, 6]
quickSortInPlace(&numbers, low: 0, high: numbers.count - 1)
print(numbers) 
// 출력: [1, 3, 4, 6, 7, 8, 9]

 

ex) 배열 [8, 3, 7, 4, 9, 1, 6]

 

1. 피벗 선택 → 6으로 선택

- 피벗보다 큰 수: high (왼쪽(8)에서 탐색 시작)

- 피벗보다 작은 수: low  (오른쪽(1)에서 탐색 시작)

 

언제까지 탐색? high의 위치 low의 위치가 교차 되었을 때 멈추고 피벗과 hight 교체

 

2. high, low 지정

- 현재 배열에서 high -> 8

- 현재 배열에서 low -> 1

두 수 교체

-> [1, 3, 7, 4, 9, 8, 6]

 

3. high, low 교차되지 않았기 때문에 다시 진행

- 현재 배열에서 high -> 7  (1,3은 6보다 작음)

- 현재 배열에서 low -> 4    (8,9는 6보다 작음)

두 수 교체

-> [1, 3, 4, 7, 9, 8, 6]

 

4.

high, low 선정 -> high: 7, low: 4

-> high, low 위치 역전 

-> 피봇과 high 교체

-> [1, 3, 4, 6, 9, 8, 7]

 

5. [1,3,4] , [9,8,7]

- 6을 기준으로 두 개의 배열로 다시 나누고 각 배열에서 다시 피벗을 설정하여 동일하게 진행

-> [1, 3, 4, 6, 7, 8, 9]