[알고리즘] 5강 - 정렬(3)

✅ 1. 힙 정렬

(1) 힙 정렬 이란?

• 힙 자료구조: 우선순위 큐 추상 자료형을 구현한 자료구조이며, 완전 이진 트리이다.
• 최대 힙: 각 노드의 값은 자신의 자식 노드의 값보다 크거나 같아야 함.
• 최소 힙: 각 노드의 값은 자신의 자식 노드의 값보다 작거나 같아야 함.
• ** 힙 정렬: 이러한 힙 자료구조의 장점을 활용한 정렬 방식이라고 보면 됨. **
• TIP: 힙 정렬에서 오름차순 정렬을 할 때에는 최대 힙을 활용하고, 내림차순 정렬이면 최소 힙을 활용을 하게 됨.

(2) 힙 정렬 - 구현

• 장점: 힙은 완전이진트리의 구조를 띄고 있기 때문에 간단한 인덱스 조작으로 자식 노드와 부모 노드를 쉽게 찾을 수 있음.
• 이러한 장점이 있기 때문에 힙은 트리 구조임에도 불구하고, 일차원 배열로 구현하는 것이 사실상 표준에 가까움.

(3) 힙 정렬 - 힙 자료구조 장점 ( 임의의 값 삽입의 간단함 )

• 완전 이진 트리의 구조를 띄고 있기 때문에, 90 이라는 데이터가 추가 될 때 반드시 왼쪽부터 채워져야 함.
• 즉, 40 오른쪽 자식 노드로써 90이 들어가야 된다는 의미임.
• 또한, 현재 힙은 최대 힙이므로 각 노드의 값은 자식노드의 값보다 커야 하기 때문에 부모 노드와 비교를 한 뒤 40과 90의 위치를 바꾸고, 90과 60의 위치를 바꿔주고, 90과 80의 위치를 바꿔주게됨. 
• ** 이렇게 임의의 값이 삽입이 되었을 때 힙의 조건을 만족할 때 까지 반복하면서 힙을 재구성을 하게 됨. **
• ** 결론: 삽입이 매우 간단하다는 장점이 있음. **

(4) 힙 정렬 - 힙 자료구조 장점 ( 최댓값 삭제가 쉬움 )

• 최댓값 삭제: 0번째 인덱스에 있는 최댓값을 삭제(즉, 최댓값을 사용하는 경우) 힙을 구현하는 배열의 마지막 원소를 가져다가 루트 노드(0번째 인덱스)에 넣게 됨.
• 힙 재구성: 이후, 힙을 재구성 해주는데 과정은 루트가 된 10 자식 노드는 60과 70이 있는데 60과 70을 비교 한 뒤, 두개 중에 더 큰 70과 자리를 바꾸게 된다. 이유는, 60이 만약 10과 변경이 된다면 70이 더 큰데 60 아래에 있기 때문에 힙의 조건을 만족하지 못하는 상황이 발생 할 수 있기 때문임.
• 결론: 10은 70과 위치를 교환하고 이후, 10은 50과 위치를 교환하며 힙 재구성이 종료가 되게 됨.

(5) 힙 정렬 - 힙 자료구조의 장점을 활용한 정렬 방식

• 힙 구조에서 루트 노드를 계속 뽑아서 정렬하는 방식으로 보면 됨.

(5) 힙 정렬 - 알고리즘

• 1단계: 1차원 배열을 힙으로 변환하는 과정
• 2단계: 데이터의 개수만큼 반복하면서 최대값을 삭제(root 노드 뽑는 작업)하고 배열의 마지막 인덱스를 루트에 넣고, 힙을 재구성하는 과정임.

(6) 힙 정렬 - 처리 과정

• 1단계: 정렬이 안된 입력 1차원 배열을 힙으로 변환하는 단계
• 2단계: 최대값을 뽑고 삭제 된 자리에 다른 최대값이 올라가는 힙 재구성을 해주는 단계
• 여기서 핵심은 입력 배열을 힙으로 변환을 한 뒤 최대값을 뽑아서 삭제를 하는 것이 아닌, 가장 큰 루트 노드의 값인 60을 가장 마지막 인덱스에 있는 가장 작은값인 10과 위치를 교환하고 60은 위치를 고정시키게 된다.
• 이후, 가장 작은 값인 10이 루트에 있는데 이것을 힙 재구성을 하게 되면, 10은 고정된 인덱스를 제외한 마지막 인덱스인 40의 오른쪽 자식 노드로 들어가게 된다. ( 즉, 최댓값과 마지막 인덱스의 최솟값과 위치를 바꾸는 것임. )
• ** 이러한 과정을 반복하게 되면 현재 루트에 있는 50도 60 위치에 들어가게 되고 계속해서 반복하는 원리임. **

• 최댓값과 마지막 인덱스의 위치를 교환하면, 최댓값은 고정이 된 상태가 유지가 되며, 이것을 반복하면 정렬이 됨.

(7) 힙 정렬 - 처리 과정 1단계 (초기 힙 구축)

• 초기 힙 구축: 1차원의 입력 배열을 힙으로 변환하는 과정을 초기 힙 구축 단계라고 함.
• 방법1: 주어진 입력 배열의 각 원소들을 모두 힙에 삽입하는 과정을 반복
• 힙 자료구조의 경우 임의의 값을 삽입하는데 있어서 쉽기 때문에 이러한 방법도 존재함.
• 방법2: 주어진 입력 배열을 완전 이진 트리로 만든 후, 노드들의 위치를 서로 계속해서 교환해 나가는 방법임.

• 입력 배열이 주어졌을 때 입력 배열의 가장 맨 앞 인덱스를 루트로 먼저 지정하게 되고, 다음 인덱스의 요소와 비교를 한 뒤 더 크다면 위치를 교환하고, 다음으로 자식 노드가 존재하는 상황에서 인덱스 계산을 통해서 하나의 배열 안에서 데이터를 교환하는 것을 반복하는 과정을 거침.
• ** 즉, 입력 배열 안에서만 데이터 교환이 이뤄질 수 있음. **

• (1) 잎 노드부터 시작해서 오른쪽에서 왼쪽으로 진행하며 힙의 조건을 만족할 수 있도록 교환을 해줌.
• (2) 먼저 자식 노드가 없는 잎 노드는 힙의 조건을 만족하는 상태이므로, 넘어가게 됨.
• (3) 자식이 있는 노드인 10에 도달하게 되면, 자식 노드인 40과 비교를 한 뒤 자식 노드가 더 크기 때문에 위치 교환이 일어남.
• (4) 이후, 20 노드의 자식 노드인 40과 80 중 더 큰 80과 위치를 교환하며, 이러한 과정을 반복해 최댓값을 루트로 올림.
• ** 핵심은 특정 노드의 자식 노드와 비교 후 교환이기 때문에 특정 노드는 부모 노드와의 비교는 하지 않음. **

• ** 결국은 오른쪽에서 왼쪽으로 올라가는 상향식 탐색을 진행하며, 특정 노드의 자식 노드와 비교 및 교환을 진행하기 때문에 교환 방식은 하향식으로 진행이 됨. **

(8) 힙 정렬 - 처리 과정 2단계 (최댓값 삭제 및 힙 재구성)

• (1) 최댓값인 루트와 배열의 마지막 인덱스에 위치한 완전 이진 트리 최하단에 있는 데이터와 위치를 교환함.
• ** 교환 된 데이터 중 최댓값은 삭제된 데이터로 간주하며, 배열의 뒷 부분에 들어가 있는 형태임. **
• (2) 루트 노드에 마지막 인덱스의 값인 10이 들어가고, 힙 재구성을 통해서 루트 자식 노드 중 가장 큰 값인 70과 위치를 교환한 뒤 이후에 10의 자식 노드가 된 30과 50 중 더 큰 값인 50과 또 위치를 교환하게 됨.

• 정렬 결과: 위와 같이 힙의 재구성을 통해서 배열이 정렬된 모습이 됨.

(9) 힙 정렬 - 성능과 특징

• 초기 힙 생성: 잎 노드를 제외한 위치부터 루트까지 올라가며 각 노드의 자식과 비교해 아래로 내리는 sift-down 을 수행하는데, 이 과정은 트리의 내려갈 깊이가 매우 짧기 때문에 시간이 거의 걸리지 않음. 이론적으로는 O(n) 의 수행 시간을 가짐.
• 바깥 루프(n): 루트(최댓값)를 꺼내서 배열의 맨 뒤로 보내는 작업은 모든 원소가 정렬될 때까지 n번 반복
• 안쪽 루프(log n): 루트 자리에 새로 올라온 원소를 제자리로 보내기 위해 아래로 내리는 sift-down을 수행함.
• 이때, 트리의 높이인 log n 만큼 비교하며 내려가게 됨.
• 초기 힙 생성: O(n)
• 정렬 반복: n * log n = O(n log n)
• 최종: O(n) + O(n log n) = O(n log n)

• 안정적이지 않은 정렬 알고리즘: 루트에 있는 20(최댓값)을 삭제 하게 되면 10과 자리르 바꾸게 되는데, 이때 루트에 있는 10은 B(20) 보다 작으므로, 위치가 바뀌게 된다. 이 경우 동일한 값의 위치가 정렬전의 상대적인 순서가 정렬 후에 유지가 되지 못한 것을 볼 수 있음.
• 제자리 정렬 알고리즘: 입력 배열 외에는 추가적으로 필요한 저장공간이 상수개를 넘지 않으므로, 제자리 정렬 알고리즘임.

---

✅ 2. 계수 정렬

• 비교 기반의 정렬 알고리즘: 지금까지 나온 정렬 방식은 모두 데이터간의 비교를 기반으로 한 정렬 알고리즘 이었음.
• 또한, 비교 기반의 정렬 알고리즘 같은 경우에는 성능의 하한이 O(nlogn) 으로 아무리 빨라도 O(nlogn) 보다 효율적인 알고리즘은 구할 수 없었음.
• 데이터 분포 기반 정렬 알고리즘: 데이터가 가진 값의 분포나 특성을 이용한 정렬 방식으로, 데이터가 일정한 범위 내에 존재하거나, 자릿수 같은 고유한 규칙이 있을 때 해당 데이터 분포 기반으로 정렬을 할 수 있음.
• ** 즉, 데이터의 분포가 고유한 규칙이 있을때에만 사용이 가능하므로, 제한적임. **
• 선형 시간 O(n): 데이터 분포 기반 정렬 알고리즘 같은 경우에는 선형 시간 O(n) 의 성능을 낼 수 있는 것이 특징임.

(1) 계수 정렬 이란?

• 계수 정렬: 데이터간의 비교 기반 정렬이 아닌, 입력 배열에서 특정 인덱스의 값보다 작거나 같은 값을 갖는 데이터가 몇개인지 개수를 알아내어 정렬하는 방식이다.

입력 배열: [2, 2, 1, 1, 3, 1]
-> 1보다 작은 값 or 같은 값 총 개수 = 3개
-> 2보다 작은 값 or 같은 값 총 개수 = 5개
-> 3보다 작은 값 or 같은 값 총 개수 = 6개

1의 마지막 인덱스 = 3 index
2의 마지막 인덱스 = 5 index
3의 마지막 인덱스 = 6 index

• ** 이와 같이, 입력 배열이 있다고 가정하면 1보다 작은 값 or 같은 값 총 개수는 3개를 알 수 있기 때문에 1이 속해 있을 수 있는 마지막 인덱스 3을 얻을 수 있게 되며, 이처럼 해당 값에 대한 인덱스 범위를 알 수 있게 되며, 이를 통해서 정렬을 함. **
• 또한, 자세히 보면 1 이후 2를 계산 할 때 1을 포함한 누적값을 통해서 index 의 마지막 위치를 알아내는 원리임.

(2) 계수 정렬 - 알고리즘

• A[1..n]: 입력 배열을 의미하며, n은 입력 크기를 의미한다.
• B[1..n]: 데이터가 정렬되어서 담기는 결과 배열을 의미한다.
• for (i=2; i<=n; i++): 입력 데이터의 최솟값과 최댓값을 계산하여 입력값의 범위를 MIN, MAX 변수에 담아주는 연산임.
• 즉, MIN 과 MAX 변수에는 입력 배열의 가장 작은값과 가장 큰값을 담아주게 됨.
• for (j=MIN; j<=MAX; j++) COUNT[j] = 0: COUNT[ ] 배열의 모든 요소들을 0으로 초기화해주는 로직.
• for (i=1; i<=n; i++) COUNT[ A[i] ]++: 입력 배열의 크기만큼 반복을 돌리면서, A[i] 입력 배열의 인덱스를 기준으로 요소들에 순차적으로 접근을 하며, COUNT[ ] 배열의 인덱스를 입력 배열의 요소의 값으로 접근을 통해 COUNT[ ] 배열의 요소의 값을 1씩 늘리는 로직.
• 쉽게 말해, 입력 배열의 동일한 값이 존재할 때 마다 COUNT[ ] 배열의 동일한 값을 인덱스로 요소를 늘려주는 역할임.
• for (j=MIN+1; j <= MAX; j++): 출현횟수의 누적값을 계산해주는 로직이며, 각 입력값보다 작거나 같은 데이터 개수를 계산해주는 로직이며, 쉽게 말해 COUNT[ ] 배열에는 입력 배열의 동일한 값들의 개수들이 들어가 있는 상태이며, 이러한 각 인덱스의 요소들 보다 작은 값도 가지고 있어야 하므로, 자신보다 앞선 인덱스들의 요소들의 누적합으로 COUNT[ ] 배열의 요소를 바꾸는 로직으로 볼 수 있음.
• for (i=n; i > 0; i--): 입력 배열 A[ ] 의 데이터를 정렬 배열 B[ ] 에 담아주는 반복문이며, 입력 배열의 데이터를 COUNT 배열의 인덱스로 넣으면 카운트 배열에 있는 개수를 하나 지워주며, 결과 정렬 배열 B[ ] 에 담아주게 된다.
• 최종: 정렬 배열 B[ ] 에 정렬된 상태로 결과가 나오게 됨.

• A[ ]: 입력 배열을 나타낸다.
• COUNT[ ]: 입력 배열에 존재하는 값들 각각의 작거나 같은 값들의 개수를 카운트 하기 위한 배열이다.
• 핵심: COUNT[ ] 배열은 입력 배열의 숫자들의 범위를 기반으로 배열의 크기가 정해지게 되며, 입력 배열의 숫자와 카운트 배열의 인덱스의 값은 동일하게 구성이 되고, 카운트 배열의 요소로는 입력 배열의 작거나 동일한 값의 누적합이 들어가게 된다.
• 예를들면, [2, 2, 1, 1, 100] 5개의 데이터가 존재한다고 가정하면, 100개의 인덱스를 가지는 배열이 만들어지게 되며, COUNT[1] 에는 1이 2개 이기 때문에 요소에는 2라는 값이 들어가게 되고, COUNT[2] 에는 2라는 숫자가 2개 그리고 COUNT[1] 의 요소 값을 더한 누적합이 들어가게 되는 원리이다.
• 결론: 각 카운트 배열의 인덱스는 입력 배열의 요소들의 숫자 범위가 되며, 해당 인덱스 내부의 요소는 숫자의 개수가 된다.
• ** 또한, 실제 정렬 과정에서는 입력 배열의 마지막 인덱스 값을 확인 한 뒤, 카운트 배열의 요소값을 확인 하게 되면, 누적합인 마지막 인덱스의 값에 해당 입력 배열의 값을 정렬 할 배열에 넣어두고, 카운트 배열의 요소값을 -1 을 해주게 된다. 그러면 마지막 인덱스에서 -1 이 된 인덱스에 넣어지는 원리이다. **

• ** 실제 동작 원리는, 위와 같이 입력 배열 A[ ] 가 주어졌을 때, 마지막 인덱스의 요소인 5를 COUNT[ ] index 5를 통해서 누적합의 개수를 확인하게 된다. 이때, 작거나 동일한 값이 4라는 값을 얻게 되고, 정렬 될 새로운 배열인 B[ ] 4번째 인덱스에 5의 값이 들어가게 되고, 숫자가 하나 사라졌으므로, COUNT[ ] 의 5의 개수를 4 -> 3으로 -1을 해주게 된다. **

• 결론은 위와 같은 과정을 반복하게 되면, 이와 같이 정렬이 완수 될 수 있음.

(3) 계수 정렬 - 성능과 특징

• O(n): 입력 데이터의 크기만큼 반복문을 돌리며, 입력 배열의 숫자들의 범위를 찾기 위해 하나씩 비교를 하게 되며, 추가적으로 입력 데이터의 크기만큼 반복을 하며, COUNT 배열에 입력 배열의 동일한 데이터를 추가함. 그리고 마지막으로 입력 데이터의  n의 크기만큼 반복해 COUNT 배열의 횟수를 내리며 B 배열에 정렬함.
• ** 즉, 파란색 부분의 입력 데이터 n에 크기에 비례한 연산을 기준으로 정해진 시간복잡도는 O(n) 이 될 수 있음. **
• O(k): k = MAX-MIN+1 의 값으로 배열 내부의 가장 큰 값과 가장 작은 값을 기준으로 COUNT 배열이 만들어지고, 그만큼 반복문을 하는 연산을 의미한다. ( 빨간색 부분 )
• ** 두 개의 O(n+k) 연산을 더하게 되면, 결론은 O(n) 의 성능을 가지게 됨. **

• 입력데이터의 범위는 k이며, 해당 k가 n가 비슷하거나, 더 작아야 선형 시간 O(n) 이 될 수 있다는 의미이다.
• ** 즉, [2, 2, 1, 100] 이런식으로 있게 되면, n은 4인데 k는 1~100까지의 범위를 가지게 되어 COUNT 배열은 100개의 원소를 담는 배열이 될 수 있기 때문에, 입력 데이터의 범위인 k는 n보다 작거나 비슷해야 O(n)을 보장 할 수 있다는 의미. **
• 안정적인 정렬 알고리즘: 원본 배열의 뒤쪽에 있던 데이터가 COUNT 배열의 누적합 개수에 의해서 마지막 인덱스를 알고 결과 배열 인덱스에 데이터를 넣게 되고, 누적합 -1 을하게 되고 이후에 동일한 값이 나온다고 하면 -1이 된 인덱스이기 때문에 동일한 값에 대한 상대적인 위치가 변하지 않게 됨.
• 제자리 정렬 알고리즘이 아님: 입력 배열을 제외해도 카운트 배열, 결과 배열 두 개의 배열을 추가적으로 이용하기 때문에 추가적인 메모리 공간을 사용하기 때문에 제자리 정렬 알고리즘이 아님.
• 보편적이지 못한 정렬 알고리즘: 입력값의 범위를 미리 알아야하고, 추가적인 배열이 필요하기 때문에 일반적으로 사용하기는 어렵다고 보면 됨.

---

✅ 3. 기수 정렬

(1) 기수 정렬 이란?

• 기수 정렬: 입력 배열의 데이터들을 자릿수별로 나누고 안정적인 정렬 알고리즘을 적용한 정렬 방식임.
• LSD 기수 정렬: 낮은 자릿수부터 높은 자릿수로 정렬을 진행하는 방식
• MSD 기수 정렬: 높은 자릿수부터 낮은 자릿수로 정렬을 진행하는 방식
• TIP: 계수 정렬의 범위(k)가 크면 메모리 사용량이 커진다는 단점을 해결하기 위해 등장한 알고리즘으로 볼 수 있음.

(2) 기수 정렬 - 알고리즘

• LSD 기수 정렬(가장 낮은 자릿수부터 정렬)방식을 이용한 알고리즘이다.
• for (i=1; i<=d; i++): d는 숫자의 최대 자릿수를 의미하며, 쉽게 말해 데이터가 최대 100의 자리까지 있다면 d = 3이 되어 루프를 3번 돌게된다는 의미이다.
• 0~d 만큼 루프를 돌며, 각각 d의 자리를 기준으로 정렬이 됨.
• ** 내부적으로 계수 정렬 알고리즘을 활용하고 있음. **

(3) 기수 정렬 - LSD 기수 정렬

• (1) 위의 예시는 1의 자리를 기준으로 정렬을 먼저 수행하는 LSD 기수 정렬 방식으로 진행이 되며, 일의 자리를 확인한 뒤 0,1,2,3...9 까지의 순으로 정렬을 하게 된다.
• 이때, 각 데이터의 i자릿수의 값에 대해서 안정적인 정렬 알고리즘을 적용하기 때문에, 정렬전 후의 상대적인 위치가 유지가 됨을 알 수 있음. ( 265, 095, 185 순서가 유지됨을 알 수 있음. )
• (2) 다음으로 10의 자리를 기준으로 정렬이 됨.
• (3) 마지막으로 100의 자리를 기준으로 정렬이 되면, 모두 정렬이 잘 된 것을 알 수 있음.

(4) 기수 정렬 - MSD 기수 정렬

• LDS 기수 정렬과 반대로 가장 큰 자리수를 기준으로 먼저 정렬이 되는 방식이다.

(5) 기수 정렬 - 성능과 특징

• 자릿수 d 만큼 반복문을 돌기 때문에 입력 데이터 n과 d를 곱한 값이 연산의 횟수로 볼 수 있지만, d는 상수이므로, O(n)임.

• 기수 정렬의 경우 입력 데이터 d가 상수 이므로, O(n) 의 시간복잡도를 가지게 됨.
• 안정적인 정렬 알고리즘: 동일한 숫자의 상대적인 위치가 유지가 됨.
• 제자리 정렬 알고리즘이 아님: 계수 정렬을 내부적으로 활용하기 때문에 전체 데이터 개수와 진법 크기만큼의 추가 공간이 필요하게 됨.

---

✅ 4. 버킷 정렬

(1) 버킷 정렬 이란?

(2) 버킷 정렬 - 알고리즘

• (1) 여러 개의 버킷 만들기: 입력값의 범위를 구한 뒤, 해당 범위에서 가장 큰 값(MAX), 가장 작은 값(MIN)을 뺀 뒤 1을 더하고 입력데이터(n)을 나누게 되면 구간의 크기를 구할 수 있으며, n 만큼의 버킷(배열) 에 각 인덱스는 해당 구간의 크기를 기준으로 하고 있음.
• (2) 각 데이터를 해당 버킷에 넣기: 각 구간마다 연결 리스트 형태를 가지는 버킷 배열에 입력 데이터의 값을 넣게 되면, 구간에 맞게 데이터가 연결 리스트 형태로 들어가게 되는 원리임.
• (3) 각 버킷을 삽입 정렬하기: 위의 65가 뒤로 가고 61이 앞으로 가듯 각 버킷의 연결 리스트를 삽입 정렬을 하게 됨.
• (4) 버킷 순서대로 각 데이터 나열하기: 버킷 배열의 인덱스 0번의 연결 리스트 제일 첫 번째 요소부터 순서대로 정렬을 하게 되면 정렬 결과가 B[ ]  배열처럼 담기게 된다.
• 결과적으로 버킷 정렬은 이러한 과정을 통해서 정렬이 됨.

(3) 버킷 정렬 - 성능과 특징

• 삽입 정렬에 의해 BUCKET[i]를 정렬: 데이터 개수 n만큼 반복하는데, 각 버킷 별로 삽입 정렬을 하는건 상수 시간 O(1) 만큼만 걸리며, 모든 버킷을 n만큼 반복하며 정렬하기 때문에 해당 반복 구간에는 O(n) 이 걸림.
• 결과적으로 보면, 모두 데이터 크기만큼 반복 또는 버킷의 상수 시간만큼 반복하기 때문에 시간복잡도는 O(n) 이다.

• ** 삽입 정렬 과정에서 하나의 버킷에 모든 데이터가 들어가 있는 경우 삽입 정렬 최악의 수행 시간인 O(n^2) 이 나올 수 있다는 단점이 존재함. 그렇기 때문에 버킷 정렬은 입력 데이터의 값이 확률적으로 균등하게 분포할 때 유용한 방식임. **
• 버킷의 개수가 입력 데이터의 개수에 비례해야 유용: 입력 데이터의 개수와 버킷의 개수가 비례할 때는 결국 각 버킷에는 상수 개의 데이터가 존재하기 때문에 각 버킷을 삽입 정렬 했을 때, 상수 시간에 정렬이 가능해지며, 결과적으로 선형 시간의 동작이 가능해 지기 때문임.
• 안정적인 정렬 알고리즘: 데이터를 버킷에 넣을 때와 각 버킷의 정렬 과정에서 상대적인 순서를 유지해줌.
• 제자리 정렬 알고리즘이 아님: 추가적인 공간이 bucket[ ] 과 크기 n의 배열 B[ ] 이 필요하기 때문에 제자리 정렬 아님.