Sorting

Bubble Sorting

• Sorting의 핵심아이디어가 코딩 테스트의 직관적 느낌에 도움을 준다.
  • Sorting을 아는게 중요한게 아님.

9 3 5 7 1
3 9 5 7 1
3 5 9 7 1
3 5 7 9 1
3 5 7 1 9

• Bubble로 두 수를 가뒀다고 생각각하여 처음에는 9, 3을 비교하여 앞의 숫자보다 뒤의 숫자가 더 작은 경우 Swap 해준다.

3 5 7 1 9 (3, 5)
3 5 7 1 9 (5, 7)
3 5 1 7 9 (7, 1 - Swap !)

• 큰 숫자들이 점점 뒤로 넘어간다.
• Time Complexity : O(n^2) avg
• Stable Sorting이다.
  • Sorting에서 Stable이냐 아니냐는 중요한 속성이다.
  • 같은 기준에서 값들이 정렬 순서가 유지되지 않는 것을 말한다.

Insertion Sorting

9 3 5 7 1 (3 ? - 9앞에)
3 9 5 7 1 (5 ? - 3, 9 사이)
3 5 9 7 1 (7 ? - 5, 9 사이)
3 5 7 9 1
1 3 5 7 9

• 두번째 원소부터 자신이 앞의 원소들 중 어디로 들어가야하는지 O(n)으로 탐색하여 판단 후 삽입한다.
• TimeComplexity : O(n^2)
• Stable

Selection Sorting

3 5 9 1 7
1 5 9 3 7
1 3 9 5 7
1 3 5 9 7
1 3 5 7 9

• 원소를 순회하면서 해당 번째에 들어가야할 숫자를 찾는 알고리즘이다.
• 첫 번째자리에 올 숫자는 가장 작은 값 1 을 찾아 Swap (3, 1)
• 두 번째자리에 올 숫자는 5, 9, 3, 7 중에 가장 작은 값 3 을 찾아 Swap (5, 3)
• 이렇게 n 번째 자리에 올 숫자를 Swap 해준 다음 범위에서 찾아 Selection하여 Swap 한다.
• Time Complexity : O(n^2)
• Unstable

7a 7b 5a 5b 3c
Selection Sorting !
3c 5a 5b 7b 7a

• 7a 7b가 7b 7a로 기존 정렬이 유지되지 않아 Stable하지않다.

MergeSort

• Recursive Implementation이 더 쉽다.

7 3 1 | 5 6 4 2
7 | 3 1 | 5 6 | 4 2
7 | 3 | 1 | 5 | 6 | 4 | 2
7 | 1   3 | 5   6 | 2   4
1   3   7 | 2   4   5   6
1   2   3   4   5   6   7

• Recursive하게 반으로 나눠나가면 원소가 1개가 될 때까지 쪼개진다.
• 두 섹션마다 Merge 시, Two Pointer를 통해 Merge 해 나간다.
• Time Complexity : O(nlogn)
• Stable

Quick Select

• n 번째로 큰 수 찾기
  • 전체 정렬 후 뒤에서 2번째 return O(nlogn)
  • Heap 사용 시 O(nlogk)
• pivot을 두고 그 보다 작은 값들을 좌측에 몰아두고, 큰 값들을 우측에 몰아둔다.

3 5 9 1 2 4 7

1 2 3 |4| 5 7 9

• 뒤에서 두번째 값으로 pivot이 4가된다.
• Partitioning 개념이다.

3 5 9 1 2 4 7
3 5 9 1 2 7 4 (4, 7 Swap)
3 2 9 1 5 7 4 (2, 5 Swap)

• pivot으로 잡은 4를 맨 마지막과 Swap
• pointer 2개를 두고, 맨 앞, 맨 뒤로 각각 배치한다.
• 맨 앞 포인터는 pivot보다 작으면 증가 크면 stop
• 맨 뒤 포인터는 Pivot보다 크면 감소 작으면 stop
• 둘 다 stop일 때 Swap 이후 반복
• 포인터들이 엇갈리면 Break 한다.
• 이를 수행하면 엇갈린 지점을 기준으로 좌측에는 Pivot보다 작은 값이, 우측에는 Pivot보다 큰 값들이 위치하게 되며 맨 뒤 포인터와 Pivot을 Swap 해주면 된다.
• 만약 2번째로 큰수를 알게되는 것이라면, 오른쪽 부분을 Partioning을 반복하면, 최종 Pivot이 구하고자하는 것이 될 것이다.
• Worst : O(n^2), Best : O(n), Avg : O(n)

Quick Sort

• Partitioning을 통한 Sorting
  • Partitioning : smaller < Pivot < bigger

7 3 4 2 5 1
7 1 4 2 5 3 (Pivot을 3으로 잡았다고 가정, 이후 맨 마지막 원소와 Swap)
p1      p2

[2 1] 3 [7 5 4]
[1 2] 3 [4 5 7]

• p1이 pivot보다 작으면 오른쪽으로 이동, p2가 pivot보다 크면 왼쪽으로 이동하면서 그렇지 않은 경우 멈춰서 둘다 멈춰있으면 p1, p2를 swap 한다. 이는 p1, p2가 엇갈릴 때까지 반복되며 엇갈리면 p1과 pivot은 swap한다.
• 마지막으로 swap한 Index를 기준으로 왼쪽은 Pivot보다 작은 값들, 오른쪽은 Pivot보다 큰 값들이 모여있을 것이다.
• 각 Pivot의 왼쪽 오른쪽을 Recursive하게 위 방식으로 Partitioning을 진행하면 정렬이 된다. 이게 Quick Sort다.

[ 7 3 4 2 5 1 ]
[ ...       7 ]
[ ...     5 7 ]
...

• Worst Case : Pivot을 계속 잘 못 잡는 경우
• Pivot을 마지막으로 Swap해서 위치시키면 Partitioning이 안될 수 있다.
• 이러면 Worst Case는 O(n^2)의 Time Complexity가 된다.

[ 7 3 4 2 5 1 ]
[ [...] 4 [...] ]
...

• Best Case : Pivot을 잘 잡아서 절반 Size로 Partitioning이 되는 경우
• Time Complexity : O(nlogn), n번의 Partitioning Procedure(Sliding + Swap), logn 번의 Partitioning Process 수행
• Quick 정렬은 Unstable하다.

Heap Sort

• Heap : Binary Tree ex [1, 3, 5, 7 ,9]

    9
  7     5
 1  3 

• 부모가 자식노드보다 항상 크다.
• max값에 O(1)으로 접근 가능

    9
  7     5
 1  3 11

• Insertion 시, Completed binary tree 특성으로 인해 오른쪽 노드의 왼쪽 자식부터 채운다. 위는 11을 Insertion한 예시다 O(logn)의 Time Complexity다.

    9
  7     11
 1  3 5


    11
  7     9
 1  3 5

    11
  7     9
 1  3 5  10

     11
  7     10
 1  3 5  9

• Insertion한 자식이 부모와 비교하여 Swap 하며 정렬된다.

     11 (pop)
  7     10
 1  3 5  9

     9
  7     10
 1  3 5  

     10 (pop)
  7     9
 1  3 5

     5
  7     9
 1  3 

     9
  7     5
 1  3 

• pop 시에는 max 값을 pop 해준 후, 마지막 원소와 swap해준다. (root, last idx swap)
• 그 이후 Children과 비교하여 가장 큰 숫자와 Swap 한다.
• Time Complexity : O(logn)
• Heap을 Build 하는 데에는 O(n)이 걸린다 (Taylor)

import heapq

nums = [9, 7, 5, 3, 1]
heapq.heapify(nums)
heapq.heappop(nums)
heapq.heappop(nums)

• 위를 이용하면 k 번째로 큰 원소를 찾으려면 k-1번 pop하면된다는 사실도 알 수 있다.
• 이는 배열로도 표현이 가능하다.

 9   7   5   1   3
(0) (1) (2) (3) (4)

• 특정 idx 노드에서 부모 노드를 index tracking 하면, (idx-1)//2 이다.
• 특정 idx 노드에서 left 자식 노드를 index tracking 하면, 2*idx + 1
  • right : 2*idx + 2

9   7   5   1   3   11
9   7  11   1   3   5
11  7   9   1   3   5

• 삽입 시, 위 공식을 이용해 Bubble Swap하면 된다.

11  7   9   1   3   5
    7   9   1   3   5 (11 pop)
5   7   9   1   3 (swap first last)
9   7   5   1   3 (5와 right node swap)

• deletion 연산도 공식을 통해 tree에서와 같은 알고리즘으로 swap 한다.

Heapify

import heapq
heapq.heapify()

std::make_heap()

1 3 5 7 9 4 6

   1
 3   5
7 9 4 6

• heap 의 관계가 만족되는지 Check 후 heapify

  • 6.. Select ! (오른쪽 -> 왼쪽 방향으로)
  • 5 (7 9) 4 6 => 6 (7 9) 4 5 <5, 6 swap>
  • 3 (5) 7 9 => 9 (5) 7 3 <3, 9 swap>
  • 1 9 5 7 3... => 9 1 5 7 3 ... <1, 9 swap>
  • 9 1 (5) 7 3 => 9 7 (5) 1 3 < 1, 7 swap>
  • 9 7 (5) 1 3 => 1, 3 모두 자식 노두가 없으므로 Stop

• Time Complexity : O(n)

• maxHeap : 부모가 자식보다 큰 Tree

• Heap을 이용한 정렬. maxHeap으로는 오름차순 정렬이 가능하다.

3 5 7 9 4 2
9 5 7 3 4 2 (max heapify)

7 5 2 3 4 | 9 (pop root(9)한 후에 맨 뒤로 보내주고, max heapify)
5 4 2 3 |7 9 (pop root(7)한 후에 9를 제외한 맨 뒤로 보내주고, max heapify)
...
2 3 4 5 7 9

• max heapify O(n) + Pop(O(logn)) n번 반복 O(nlogn) = O(nlogn)
• Unstable

Counting Sort

• Time Complexity : O(n + alpha)
  • alpha 가 뭐냐에따라 O(nlogn) 보다 좋은 솔루션일 수 있다.

3 3 2 1 2

1 2 2 3 3

• 1 1개, 2 2개, 3 2개 순서로 출력

3 4 0 1 2

1 1 1 1 1 (count array)
1 2 3 4 5 (accumulate array) : 각 숫자들이 끝나는 위치 정보가 담긴다. 말 그대로 누적합을 하면된다. 각 인덱스의 누적합은 각 숫자마다 필요한 칸을 확보하는 것과 같다. 
-
-1
0 1 2 3 4 (offseted acc array): index는 0부터 시작이므로 offset -1을 해준다.

3 4 0 1 2 에서 맨 뒤에서 부터 찾아 위치정보에 따라 sorted array에 기록한다.
        p

2 ? offseted accumulate array 에서 2 이므로 sorted array에서 2 index에 써진다. offsted accumulate array에서 2는 1로 줄어든다 (2-1 = 1)

0 1 1 3 4 (offsted acc array)

3 0 5 1 0 5

2 1 0 1 0 2 : 0이 2개 1이 1개...

2 3 3 4 4 6 (accumulated array)
1 2 2 3 3 5 (offseted)

3 0 5 1 0 5
        <-p
        p
      p
    p
  p
p

0 0 0 0 0 5 (1 2 2 3 3 4)
0 0 0 0 0 5 (0 2 2 3 3 4)
0 0 1 0 0 5 (0 1 1 3 3 4)
0 0 1 0 5 5 (0 1 1 3 3 3)
0 0 1 0 5 5 (-1 1 1 3 3 3)
0 0 1 3 5 5 (-1 1 1 2 3 3)

• 특이한 방식의 Counting Sort이지만, accumulate array 방식을 도입하면서, Stable Sort 속성을 만들어준다.
• Time Complexity : O(n+k)
  • k는 최대 값인데, count array의 length가 길어 질 수 있다. (효율적이지 않다.)

Radix Sorting

• Countings Sort는 O(n + k)의 시간 복잡도를 갖지만 k값이 매우 크면 공간 복잡도가 효율적이지 않다.

341 582 50 924 134 8 192

• 위를 Counting Sort를 적용한다면, 공간 복잡도가 꽤나 크다.
• 이를 Counting Sort와 비슷하게 적용하려면 무조건 stable sort이어햔다.

50 391 582 192 924 134 8

• 먼저, 1의 자리 숫자들로 정렬한다.

8 924 134 50 582 391 192

• 다음은 10의 자리수로 정렬

8 50 134 192 392 582 924

• 마지막으로 세자리 이므로 100의 자리 수로 정렬을 하면 정렬된다.
• 공간복잡도가 자리수대로 적용되므로 0 ~ 10의 범위로 줄어든다.
• Time Complexity는 O(w(n+k))로, k는 10으로 고정된 것이고 w는 자리수 이다.
  • Counting Sort를 자리수대로 수행하는 것이다.