1. 정렬 Sorting

코와->코어·2021년 9월 28일
0

알고리즘

목록 보기
1/9
post-thumbnail

목표: [8, 2, 4, 9, 3, 6] => [2, 3, 4, 6, 8, 9]

1. 삽입 정렬 Insertion sort

  • 2번째 요소부터 시작하는 이유: 하나의 요소만 남았을 경우에는 이미 정렬된 것이기 때문

[8, 2, 4, 9, 3, 6]
1) key가 바로 지금 삽입/정렬될 요소 ex) key = A[2] = 2

2) A[i]는 이미 정렬된 요소들 중에서 가장 큰 것 ex) A[i] = A[1] = 8

3) A[i] > key : A[i]를 오른쪽으로 한 칸 옮기고 두 번째로 큰 요소와 key를 비교하는 과정 반복
ex) 첫 번째 반복

  • A[i] > key ( 8 > 2 )
  • Ai+1에 8 넣기 : [8 ,8, 4, 9, 3, 6]
  • i를 하나 줄이기 : i = 0
  • i > 0이라는 while문의 조건이 false이므로 반복문 탈출

4) 위의 비교 과정은 key가 A[i]번째 요소보다 큰 경우에 멈춘다: key가 A[i] 보다는 크고 A[i+1]보다는 작은 상황

5) 3번 과정을 통해 A[i+1]번째 요소를 다음 칸(i+2번째 칸)으로 복사해 둔 상황이라 현재 A[i+1]에 key를 삽입해도 문제가 없다
ex) A[i+1] = key( A[1] = 2 ): [2, 8, 4, 9, 3, 6]

2. 합병 정렬 Merge sort

  • 리스트를 하나의 요소가 남을 때까지 절반씩 분할한다

  • 각각 분할된 요소들을 합병(merge)하는 과정에서 요소들을 정렬한다.

  • 1) Θ(1) : 한 개의 요소만 있다면, 이미 정렬된 것

  • 2) 2T(n/2) : 크기가 2/n인 리스트를 두 번 합병 정렬하는 것과 같음

  • 3) Θ(n) : 최대 n개의 요소를 비교하고 합침

  • 만약 한 쪽의 리스트가 먼저 다 정렬되었으면 남은 리스트의 요소들은 비교 안 해도 됨

재귀식 recurrence

위의 2)번과 같은 방법은 재귀라고 볼 수 있다.
크기를 줄인 후 똑같은 과정을 반복하기 때문이다.

Recursion tree

여기에서 c(n/2)은 어떻게 나온 것일까?

T(n) = 2T(n/2) + cn <- 이 식으로부터 T(n/2)를 구하기 위해 n에 (n/2)를 대입하면 다음과 같은 식이 나온다.

T(n/2) = 2T(n/4) + c(n/2)

결국 n/2가 1이 될 때까지 반복해서 n을 2로 나눈다는 말인데,
T(n/2) 부분은 또 하위 레벨(T(n/4)부분)에 넘겨 주고 해당 레벨에 온전히 남는 것은 결국 상수 부분,
즉 cn, c(n/2), c(n/4)...부분이 된다. 트리 그림으로 보면 다음과 같다.

--------------cn-------------- : 1번째 레벨: cn
----c(n/2)----------c(n/2)---- : 2번째 레벨: c(n/2)
c(n/4)-c(n/4)----c(n/4)-c(n/4) : 3번째 레벨: c(n/4)

모든 요소들이 1개만 남게 될 때까지 계속해서 1/2로 리스트의 크기를 나눈다는 것이 이것을 의미하는 것이다.

크기가 6인 리스트를 정렬하는 것은 [8, 2, 4, 9, 3, 6]
크기가 3인 리스트를 두 개 정렬하는 것과 같고, [8, 2, 4][9, 3, 6]

크기가 3인 리스트를 정렬하는 것은 [8, 2, 4]
크기가 1 또는 2인 리스트를 두 개 정렬하는 것과 같다. [8][2, 4]

크기가 1인 리스트는 이미 정렬된 것으로 간주한다. [8][2] [4]

그렇다면 cn의 의미는 무엇일까?

바로 크기를 1로 분할한 저 요소들을 다시 합치면서 정렬하는 데 걸리는 시간을 의미한다. c는 임의의 양의 상수이며, 결국 다시 합치면서 정렬하는 데는 최대 n번 비교하면 된다는 뜻이다.

크기가 1인 리스트를 합칠 때에는, [8][2] [4]

(위에서 분할할 때 2와 4가 함께 분할되었으므로 이들을 먼저 비교해보자.)
2와 4를 비교할 때에는 1번만 비교하면 된다. 즉, 2 < 4를 하면 된다.
그 결과, 다음과 같이 정렬된다. [8][2, 4]

크기가 2인 리스트를 합칠 때에는, [8][2, 4]
두 번 비교하면 된다. 8과 2, 8과 4
8은 2보다 크고, 4보다도 크므로 다음과 같이 정렬된다. [2, 4, 8]

(한쪽에서 [8][2] [4]가 [2, 4, 8]로 정렬되는 동안, 다른 쪽에서는 [9][3] [6]이 같은 과정을 통해 [3, 6, 9]로 정렬되었을 것이다. 이제 이들을 비교하면서 정렬된 순서로 합친다.)

3과 2를 비교하고, 3과 4를 비교한 후, 2와 4 사이에 3을 넣는다. [2, 3, 4, 8]

(6과 2는 비교하지 않는다. 위에서 이미 6보다 작은 3이 2보다 큰 것으로 정렬되었으므로 6은 2의 다음 요소인 4부터 비교한다.)
(마찬가지로 3과 6은 이미 3보다 6이 더 큰 것으로 정렬이 되었으므로 비교하지 않는다.)
6과 4를 비교하고, 6과 8을 비교한 후, 4와 8 사이에 6을 넣는다. [2, 3, 4, 6, 8]

9와 8을 비교한 후, 9를 8의 뒤에 넣는다. [2, 3, 4, 6, 8, 9]

이렇게 분할했던 요소들을 다시 하나로 합치면서 크기를 비교하고 정렬하게 되는데, 이 과정에서 비교가 최대 O(n)번 일어나므로 점화식에 cn이 추가된 것이다.

시간 분석

이렇게 병합 정렬의 점화식의 의미에 대해 알아봤다. 사실 이렇게 병합하는 과정에 대부분의 시간이 걸린다. 리스트를 분할하는 과정은 O(1)의 수준의 시간이 걸리기 때문에 생략해도 되는 수준이다.

위에서 본 recursion tree에서 1번째 레벨의 노드에 cn만 남는 이유가 바로 이 때문이다. 크기가 n인 리스트를 n/2로 분할하는 데에는 O(1)만큼의 시간이 걸리고, 합병하는 데에 cn만큼의 시간이 걸리기 때문에 cn만을 남겨둔 것.

따라서 2번째 레벨의 노드를 정렬하는 데에는 cn/2만큼의 시간이 걸리고, 이 과정을 반복하다 결국 그 자체로 정렬이 되었다고 여겨지는 크기가 1인 리스트가 되는 수준에 도달한다. 그 경우는 분할을 할 필요도 없고, 정렬하는 데에도 O(1)만큼의 시간이 걸리므로 분할 과정을 stop한다.

n에서 1만큼 분할하기까지 log n번, 각 레벨의 노드를 다 합하면 결국 cn이므로 전체 recursion tree의 노드의 합(크기가 n인 리스트를 병합 정렬하는 데 걸리는 시간)은 log n * cn이다. c는 상수이므로 무시하면 O(n log n)으로 표현할 수 있다.

삽입 정렬 vs 합병 정렬

**Θ(n log n)은 Θ(n^2)보다 훨씬 빠르다 -> Merge sort 가 insertion sort보다 훨씬 빠르다!!

  • 실제로는 n>30인 경우에 merge sort가 insertion sort보다 빠르다고 한다.**

3. 빠른 정렬 Quick sort

!!주목!! 잘 알아두세요... 면접에서 "정렬 알고리즘 중 가장 빠른 알고리즘이 무엇이냐?"는 질문을 받고 "퀵 소트"라 대답하면서 최선의 경우 log n번만에 정렬을 완료할 수 있다고 대답했는데 이것만으로는 부족합니다

  • 분할 정복 알고리즘
  • "in place"에서 정렬 : merge sort와 달리 추가 공간이 필요하지 않고 인덱스를 통해 정렬

pseudocode

  • A는 리스트, 리스트의 첫 번째 인덱스, r은 리스트의 마지막 리스트를 의미한다.
  • p < r은 A에 한 개의 요소만 있는지 검사하는 조건이다. 만약 하나만 있다면 stop
  • 재귀적으로 이 과정 반복
  • sub-list들 합칠 필요 없음! => !!!merge sort와의 차이점!!!

  • pivot x를 기준으로 대소비교하여 리스트를 왼쪽은 x보다 작은 것들, 오른쪽은 y보다 큰 것들로 분할

  • 위의 수도코드는 리스트의 첫 번째 요소를 피봇으로 삼아 리스트의 두 번째 요소부터 마지막까지 순회
    ex) [6, 10, 13, 5, 3]에서 pivot은 6, 10-13-5-3의 순으로 A[j]가 변화, i는 1

  • x보다 작은 요소를 찾으면 현재 찾은 요소와 이미 정렬된 요소의 바로 다음 칸에 있는 요소를 swap
    ex)
    6과 10을 비교하면 10이 더 크므로 그대로 둠
    6과 13을 비교하면 13이 더 크므로 그대로 둠
    6과 5를 비교하면 6이 더 큼 -> 이미 정렬된 요소 없으므로 x의 바로 다음 칸에 있는 10과 5를 swap [6, 5, 13, 10, 3]
    6과 3을 비교하면 3이 더 큼 -> 이미 정렬된 요소 5의 바로 다음 칸에 있는 13과 3을 swap [6, 5, 3, 10, 13]

  • 순회를 마치면 x와 현재 정렬된 요소들 중 가장 오른쪽에 있는 요소를 swap
    ex) 현재 찾은 가장 오른쪽에 있는 정렬된 요소는 3이므로 6과 3을 swap [3, 5, 6, 10, 13]
    => 6을 기준으로 작은 요소들은 왼쪽, 큰 요소들을 오른쪽으로 정렬됨

quick sort의 장점

quick sort는 pivot으로 어떤 인덱스의 요소를 선택할 것인지를 프로그래머가 설계할 수 있다는 점이 장점인 것 같다. 내가 정렬하게 될 데이터의 분포를 분석해 가장 최적화된 비율로 customize = code tuning할 수 있다는 점

nice-case

quick sort가 빨리 작업을 끝내려면 pivot이 딱 절반씩 리스트를 분할해 주면 된다. 그러면 점화식을 T(n) = 2T(n/2) + Θ(n) 으로 세울 수 있다.
(Θ(n)은 pivot을 기준으로 대소비교하는 데 걸리는 시간이다. pivot 빼고 나머지 요소들과 비교를 각각 한 번씩 하므로 총 n-1번 비교함)
log n 번의 단계를 n의 가중치로 반복하므로 시간복잡도는 Θ(n log n)

worst-case

그런데 예를 들어 위처럼 첫 번째 요소를 pivot으로 선택한다고 할 때, 전체 리스트가 역순으로 정렬되어 있는 경우/이미 정렬되어 있는 경우는 pivot을 기준으로 분할하면 무조건 나머지 요소들은 pivot보다 작으므로 오른쪽 sub-list는 없게 된다.
ex)
[9 ,8, 4, 1]은 9를 pivot으로 설정하면 [1, 8, 4, 9] : 오른쪽 sub list 없음
[1, 8, 4] 1을 pivot으로 설정하면 [1, 8, 4] : 왼쪽 sub list 없음
[8, 4] 8을 pivot으로 설정하면 [4, 8] : 오른쪽 sub list 없음
[4] 길이가 1이므로 stop

이런 경우 시간복잡도는 T(n) = T(0) + T(n-1) + Θ(n)으로 표현할 수 있다.
항상 한쪽 sub list는 길이가 0이고 나머지 sub list는 pivot 하나만 빠진 sub list이므로

T(0)은 길이가 0일 때의 quick sort 시간인데 이 때는 작업을 하지 않으므로 Θ(1)로 표현해도 된다. Θ(1)은 무시해도 되는 수준이므로 결국

T(n) = T(0) + T(n-1) + Θ(n) = T(0) + T(n-1) + cn 으로 표현할 수 있다. 이 식으로 recursion tree를 그려 보면 등차수열이다! 각 레벨당 cn -> c(n-1) -> c(n-2) - > ... -> 1
등차수열의 합 공식으로 이 점화식의 시간복잡도는 Θ(n^2)임을 알 수 있다.

1:9?

만약 pivot이 전체 리스트를 1:9의 비율로 분할하는 경우는 어떨까?
점화식은 T(n) = T(n/10) + T(9n/10) + Θ(n)이 될 것이다.

recursion tree를 그려보면 위와 같다. quick sort의 총 소요 시간은

여기에서 각 레벨의 합은 cn이다. 각 단계리스트의 인덱스를 조작해서 분할하는 것이지 원본 리스트의 크기가 줄거나 하지는 않기 때문에 총 문제의 크기(가중치)가 모든 레벨에서 동일하게 cn이다. (정확한가?)

pivot 기준으로 분할이 끝날 때까지
한 쪽은 항상 1/10 수준으로 분할되므로 log n단계가 걸릴 것이다. 한 개의 요소만 남게 되므로 비교를 할 필요가 없어진다.

반면 한 쪽은 항상 9/10수준으로 분할되므로 log10/9 n 단계가 걸릴 것이고 여러 요소가 남게 되므로 대소비교를 해 줘야 한다.

총 소요 시간은 노드 전체를 합한 시간일텐데, 가장 빨리 종료되는 sub-list가 발생할 때까지의 총 소요 시간은 cn log n 이 걸리고, 가장 늦게 종료되는 sub-list가 발생할 때까지의 총 소요 시간은 cn log10/9 n + Θ(n)이 걸릴 것이다.
결국 이 경우도 Θ(n lon n)이라고 할 수 있음

randomized quicksort

전체 리스트 분할 비율이 1:9보다 나쁘지 않을 때까지 pivot을 random으로 고르는 방식이다.

예를 들어 크기가 n인 리스트가 있다고 하면, pivot이 분할하게 되는 sub list의 비율은 다음과 같을 것이다.
[pivot은 무조건 정렬되니까 sub list의 총합은 n-1개의 요소들이 됨]
0: n-1
1: n-2
2: n-3
...
n-1: 0
그리고 각각의 비율로 분할될 확률은 동일하게 1/n이다.

이 모든 경우의 확률을 더하면 다음과 같다.

이 식에서 k가 0이나 1인 경우는 Θ(n)시간에 흡수될 수 있다고 보고 식을

이렇게 고친다. 이 식이 항상 a n log n보다 작거나 같다는 것을 증명하면 된다.

하하하.... 멋진 수학적인 과정을 거쳐 randomized quicksort의 예상 시간복잡도가 Θ(n log n)을 만족시킨다는 것이 밝혀졌다!!
사실 이건 랜덤으로 고른 pivot에 대한 결과를 평균 낸 것이기 때문에 항상 n log n을 "보장"하는 것이라 할 수는 없고 "예상, 기대 시간 복잡도"가 n log n 수준이라고 이야기해야 한다.

모든 random choice가 독립적이어야 이렇게 분석할 수가 있다. 각 단계별 분할 과정이 이전의 분할이나 이후의 분할에 영향을 미치지 않아야 한다는 것.

randomized case는 average case와는 다르다. average case는 입력 길이가 평균인 경우를 통계적으로 계산해서 그 경우에 시간복잡도가 어떻게 나오는지를 분석하는 것이고 randomized case는 모든 경우의 수의 확률을 더한 것이다.

profile
풀스택 웹개발자👩‍💻✨️

0개의 댓글