LEE CHANWOO

📝 Blog 2024 version 1.7.0
🔖 NOV 26, 2024

7 분 소요

image


Sorting

: 컴퓨터 관련 전공에서 매우 중요한 고전 문제. Sorting을 이용하면 많은 문제들을 효율적으로 풀 수 있음.

  • 이진 탐색(Binary Search) : O(log2n) 보장
  • 가장 큰 값 (혹은 가장 작은 값) 찾기 : O(1) 보장
  • 중복되는 같은 값들이 있을 때 이들을 제거 : O(n) 보장
  • 최소 신장 트리(Minimal Spanning Tree) : O(n) 보장
  • SQL: ORDER BY, GROUP BY
  • 대용량 데이터 탐색(B Tree)


  • 문제를 푸는 데 전체 수행 시간의 상당 비중 (약 25% - 50%)이 sorting 시간에 소비됨. 따라서 다양한 sorting 알고리즘들의 기법, 효율성, 장/단점들을 습득하는 것이 매우 중요함.


  • Sorting의 대상이 되는 값들을 각각 key 라고 지칭함. 다음의 2 가지 유형의 key들이 있음.
    • 숫자(Numeric) : 학번, 사번, 점수 등
    • image
    • 문자열(String) : 이름, 단어, 용어 등
    • image


고려사항


Time 성능

  • 비교(comparison) 연산을 총 몇 번하나?
  • 즉, O(n2) 혹은 O(n*log2n) 이냐?
    • cf) 탐색에서는, O(n) vs O(log2n)
  • Swap 연산을 많이 (혹은 적게) 하나?


Space 성능

  • In-Place
  • Extra Space (즉, space(예: stack)가 여분으로 더 필요하나?)


유형


Internal Sort (내부 정렬)

  • Sort small or medium volume data in main memory
  • selection sort, bubble sort, insertion sort, quick sort, heap sort, merge sort, etc.
  • 성능 척도 : 비교 회수 (CPU cost)
  • O(n2) or O(n*log2n)
  • 자료구조 과목에서 취급

External Sort (외부 정렬)

  • Sort very large volume data in disk storage
  • Can not directly use internal sort algorithms
  • Divide a file into several sorted subfiles (= run)
  • Use internal sort and merge sorted subfiles
  • 성능 척도 : disk 접근 회수 (I/O cost)
  • 데이터베이스 과목에서 취급


Selection Sort (선택 정렬)

  • 전체 list가 2 개의 sublist 들로 분할됨 : sorted / unsorted
  • 전체 list가 모두 sort 될 때까지 각 단계(pass)에서 다음 과정을 반복;
    • (1) Unsorted list에서 smallest key를 탐색해서 선택.
    • (2) 이 smallest key를 unsorted list의 맨 앞에 위치한 key와 swap.


image


image


Selection Sort (int list[ ], int n)
  int i = 0, j = 0;
  int smallest = 0; int temp = 0;
    // list에서 smallest key를 찾음/
  for (i = 0; i < n - 1; i ++) {
    smallest = i;
    for (j = i + 1; j < n; j++)
      if (list[j] < list[smallest])
        smallest = j;
    // Smallest key와 맨 앞의 key와 교환 //
    temp = list [i];
    list [i] = list [smallest];
    list [smallest] = temp;
  • 총 비교 회수 :
    • = (n-1) + (n-2) + . . . + 1
    • = (n-1)n/2
    • = O(n^2)


  • Duplex(이중) Selection Sorting
    • Unsorted List를 탐색하는 동안 smallest 와 largest key를 함께 동시에 찾음.
    • Smallest key와 list의 맨 앞에 위치한 key와 swap
    • Largest key를 list의 맨 뒤에 위치한 key와 swap
    • 결과적으로 한 단계에서 smallest와 largest 값 2 개가 제자리를 찾아 감.
    • 총 비교 회수의 성능은 조금 향상됨.
    • 그러나 Big Oh 표기의 관점에서 여전히 O(n^2)의 시간 범주에 속함


Bubble Sort

  • 전체 list가 2 개의 sublist 들로 분할됨 : sorted / unsorted
  • 전체 list가 모두 sort 될 때까지 각 단계(pass)에서 다음 과정을 반복;
    • (1) unsorted list의 오른쪽 끝에서 왼쪽으로 이동하면서 각 쌍(pair)의 2 개의 key 값들을 서로 비교함.
    • (2) 만약 비교 후 key들의 크기가 뒤바뀌었으면 서로 swap함.
  • 각 단계에서 smallest key가 filtering되어 sorted list로 이동됨.


image


image


  • 총 비교 회수 :
    • = (n-1) + (n-2) + . . . + 1 = (n-1)n/2 = O(n^2)


비교 : Selection Sort와 Bubble Sort

  • Selection Sort는 각 단계에서 swap이 단 1 번만 발생
    • : 즉, Smallest key와 맨 앞의 key와의 swap 때만 발생
  • Bubble Sort는 각 단계에서 swap 횟수가 많음
    • : Smallest key가 한 칸마다 왼 쪽 방향으로 계속 이동하므로;
  • Swap 측면에서, Key size가 큰 경우 (예: 문자열)에는, Selection Sort가 더 효율적임.
  • Key들이 거의 sort가 되는 과정인 경우, Bubble Sort가 매우 효율적임.
    • 즉, 만일 어떤 단계에서 swap이 전혀 없으면 sort가 완료 된 것이므로 그 다음 단계를 수행할 필요 없고, 여기서 종료됨.
  • Key들이 이미 sort가 된 list 인 경우, Bubble Sort는 첫번째 단계에서 종료됨: 따라서 O(n)으로 향상됨. 반면에 Selection Sort는 여전히 O(n^2).


Insertion Sort (삽입 정렬)

  • 전체 list가 2 개의 sublist 들로 분할됨 : sorted / unsorted
  • 전체 list가 모두 sort 될 때까지 각 단계(pass)에서 다음 과정을 반복;
    • (1) 각 unsorted list의 맨 앞의 key를 pivot이라는 변수에 이 값을 저장함.
    • (2) pivot과 pivot 이전에 위치한 각 key들을 왼쪽 방향으로 계속 이동하면서 비교함.
    • (3) pivot 보다 큰 key를 만날 때 마다, 이 큰 key를 오른 쪽으로 한 칸 이동함. 최종적으로 (즉, pivot보다 작은 key 다음 위치) 남은 빈 공간에 pivot을 insert함.


image


image


  • i 번째 단계 수행 후에는, list의 첫번째에서 i 번째 까지의 모든 key들은 (즉 pivot 이전의 모든 key들) 이미 sort가 완료가 된 상태임.

  • Worst case의 총 비교회수
    • Input list의 Key들이 내림 차순으로 이미 sort 된 경우
      • 예: {80, 70, 60, 50, 40, 30, 20, 10}
    • 이 경우 각 단계에서 pivot 이전의 모든 key들과 비교를 해야 함.
    • 1 + 2 + . . . + (n – 1) = n (n-1)/2 = O(n2)
  • Best case의 총 비교회수
    • Input list의 Key들이 오름 차순으로 이미 sort 된 경우
      • 예: {10, 20, 30, 40, 50, 60, 70, 80}
    • 이 경우 각 단계에서 pivot 바로 이전의 key 한 개만 비교하면 충분.
    • 1 + 1 + . . . + 1 = O(n)


비교 : Selection, Bubble, Insertion

  • Worst case에 모든 알고리즘이 O(n^2)으로서 동일
  • Extra Space가 필요 없음. Array 1 개면 충분.
  • 알고리즘들이 비교적 단순하므로 사용하기 편함.
  • Key들의 개수(n)가 적은 경우에는 사용해도 무방. 단, 많은 경우에는 매우 느림. 예: n = 100,000이상
  • Key들이 내림 차순으로 이미 정렬된 경우에는 insertion sort 를 사용하면 매우 비효율적.
  • Key들이 오름 차순으로 이미 정렬된 경우에는 bubble과 insertion sort 를 사용하면 매우 효율적
  • Swap 연산은 selection sort 를 사용하면 매우 효율적.


연습: Selection, Bubble, Insertion

  • 1) 다음의 각 list를 Selection, Bubble, Insertion Sort를 이용하여 정렬 과정을 단계별로 보여라.
  • 2) 각 방법에 대해 비교 회수와 swap 회수를 계산하라.
    • list 1 = {7, 5, 10, 4, 3, 6, 8, 9, 2, 1}
    • list 2 = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
    • list 3 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}


Quick Sort

(One of Top 10 algorithms in 20th Century)

  • 전체 list가 모두 sort 될 때까지 각 단계(pass)에서 다음 과정을 반복;
    • (1) Pivot 을 선택 (단, pivot 을 list의 맨 앞의 key로 선택한다고 가정)
    • (2) List를 2 개의 sublist로 다음과 같이 분할(Split)함;
      • 왼 쪽 sublist의 모든 key들은 pivot 보다 작음.
      • 오른 쪽 sublist의 모든 key들은 pivot 보다 큼


image


  • Divide and Conquer 알고리즘 기법은 주어진 문제를 계속하여 더 작은 크기의 각각의 문제들로 분할한 후 각각의 답을 합치는 방식임.
  • Quick sort는 위의 방식을 기반으로, split 과정을 계속 거쳐 여러 개의 작은 sublist로 분할. 각 sublist가 더 이상 분할이 안 되면 정렬이 완료됨.


image

  • 이제 왼 쪽 sublist를 split을 더 분할이 안 될 때 까지 계속 수행함;
  • 다음에 오른 쪽 sublist를 split을 더 분할이 안 될 때 까지 계속 수행한 후 종료함.


image


image


image


성능 분석

  • Quick sort의 시간 성능은 list를 어떠한 형태로 split 하는지에 따라 결정됨.

  • 즉, split 된 2 개의 sublist가 균형 있게 거의 같은 크기(balance)를 갖는지, 혹은 한 쪽으로만 크기가 편중(biased)되었는지?

  • Worst Case Analysis
    • Split 된 sublist들이 completely unbalanced (= biased) 일 때 발생
    • 즉, 각 split 단계에서 pivot을 smallest 혹은 largest key를 매번 선택할 때
      • 예 : {9, 8, 7, . . . ,2, 1} : Decreasingly sorted
      • 예 : {1, 2, 3, . . . ,8, 9} : Increasingly sorted
    • 각 split 단계 후에, sublist들이 다음의 형태를 갖음;
      • list [n - 1], list [n - 2], . . . , list [1];
    • 총 비교 회수 : (n - 1) + (n - 2), . . . + 1 = O(n^2)


  • Average Case Analysis
    • Split 된 sublist들이 roughly qual size 일 때 발생;
      • 즉 key들의 개수가 대략 균등하게 2 개의 sublist에 배분되는 경우.
    • 매번 split 후에 각 sublist의 크기는 다음과 같이 ½ 씩 감소됨;
      • n, n/2, n/4, n/8, . . . n/2k
    • 이제 총 split의 회수(k)는 다음과 같음;
      • n/2k = 1; k = log2n
    • 각 split에서 비교 연산을 n 번 수행함.
    • 따라서 quick sort의 총 비교 연산의 회수는 다음과 같음.
      • 각 split에서 비교 회수 * 총 split 회수
      • = n * log2n
      • = O(nlog2n)


  • 다음은 Quick Sort의 Average Case를 Formal한 방식으로 분석하는 과정;
  • 여기서 T(n)은 n 개의 keys들을 정렬하기 위한 총 비교 회수;

image

  • Quick sort has the best average time among all the sorting methods


Quick Sort의 성능 향상

  • Pivot을 list의 맨 앞 혹은 맨 뒤의 key로 정한 경우;
    • 그 list가 오름 차순 혹은 내림 차순으로 정렬이 되었는지를 검토;
    • 만약 그렇다면, pivot을 임의로 random 값으로 재선정해서 worst case를 피할 것.
  • 분할 된 sublist가 점차적으로 중간에 small size (예: key 개수가 10개)가 되는 경우;
    • 이 경우 split을 중지하고 다른 알고리즘(예: Insertion sort)를 사용하여 종료하는 것이 더 효율적
    • Quick sort는 small size인 경우에는 비효율적
  • 좋은 Pivot의 선택이 중요
    • 분할된 각 sublist가 거의 균등한 size가 되도록 pivot을 선택


Choice of Pivot : Median 값

  • Pivot으로 전체 list에서 “Median (중간값)” 을 선택
  • 모든 key 값들을 고려하여 median 값을 계산하는 것은 비효율적;
  • 다른 방법: Sampling 방법
    • Median of Three : first, middle, last
    • 맨 앞, 맨 뒤, 가운데 key들 중에서, 중간 값(median)을 pivot으로 선택
    • 예: list[6, 20]인 경우, list[6], list[13]와 list[20] 중에서
      • 만약 list[6] = 30, list[13] = 2, list[20] = 10이면, pivot은 list[20] = 10;
      • 만약 list[6] = 3, list[13] = 2, list[20] = 10이면, pivot은 list[6] = 3;


  • Quick Sort using median of three as pivot

image

  • 위는 각 sublist가 거의 equal size (not biased)로 split되는 경우의 예

댓글남기기

참고