✍️Today I Learned

1. 정렬
2. 삽입 정렬
3. 병합 정렬
4. 계수 정렬
5. 힙 정렬

---

정렬이란

사용자가 정의한 순서대로 데이터를 나열하는 것

정렬을 하는 이유

1. 원하는 값을 빨리 찾기 위해
   ex) 중앙값이나 최댓값이 필요한 경우 정렬하면 빠르게 찾을 수 있다.
2. 정렬이 전제 조건인 알고리즘이 존재하기 때문
   ex) 이진 탐색

---

삽입 정렬

정렬되지 않은 데이터를 이미 정렬된 부분 배열의 적절한 위치에 차례로 삽입하여 전체 데이터를 정렬하는 알고리즘
의사 코드

 for j = 2 to A.length
     key = A[j]
     // A[j]를 정렬된 부분 배열 A[1..j-1]에 삽입한다.
     i = j - 1
     while i > 0 and A[i] > key
         A[i + 1] = A[i]
         i = i - 1
     A[i + 1] = key

구현 코드

using namespace std;
int main(){
	int arr[] = {5, 4, 3, 2, 1};
    for(int i = 1; i<sizeof(arr)/sizeof(int); i++){
    	int key = arr[i];
        int j = i;
        while(j>0){
        	if(arr[j-1] > arr[j]){
        		arr[j] = arr[j-1];
            	arr[j-1] = key;
                j--;
        	}
        }
    }
	return 0;
}

세부 동작

1. 최초 데이터
   첫 번째 원소(i=0)은 정렬된 것으로 간주하여 두 번째 원소부터 시작한다.
2. 정렬
   이전 인덱스의 데이터가 현재 인덱스의 데이터보다 큰 경우 현재 인덱스의 데이터와 순서를 바꾼다.
3. 반복
   이전 인덱스의 데이터가 현재 인덱스보다 크지 않을 때까지 반복한다.

시간 복잡도

최악의 경우 매 원소 마다 0 번째 ~ 직전 원소들과 비교하므로 O(N²)

---

병합 정렬

정렬되지 않은 데이터를 계속 반으로 나눈 뒤 작은 단위부터 정렬하며 병합해 나가는 방식의 정렬 알고리즘
의사 코드

MERGE_SORT(A, p, r)
if p < r
  q = (p + r) / 2
  MERGE_SORT(A, p, q)
  MERGE_SORT(A, q + 1, r)
  MERGE(A, p, q, r) // 이미 정렬된 A[p...q]와 A[q+1....r]을 병합해서 하나의 배열로 만듬

구현 코드

#include <iostream>
using namespace std;

void merge(int arr[], int left, int mid, int right) {
    int size = right - left + 1; // 임시 배열의 크기
    int* temp = new int[size];   // C-style 동적 배열 할당

    int i = left;    // 첫 번째 부분 배열(arr[left...mid])의 시작 인덱스
    int j = mid + 1; // 두 번째 부분 배열(arr[mid+1...right])의 시작 인덱스
    int k = 0;       // 임시 배열(temp)의 시작 인덱스

    // 두 부분 배열을 비교하며 임시 배열에 정렬하여 저장
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // 첫 번째 부분 배열에 남은 요소가 있다면 임시 배열에 복사
    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    // 두 번째 부분 배열에 남은 요소가 있다면 임시 배열에 복사
    while (j <= right) {
        temp[k++] = arr[j++];
    }

    // 임시 배열(temp)에 정렬된 요소들을 원래 배열(arr)의 해당 위치에 복사
    for (int idx = 0; idx < size; ++idx) {
        arr[left + idx] = temp[idx];
    }

    delete[] temp;
}

// mergeSort 함수는 변경할 필요 없음
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        // (left + right) / 2 는 큰 값에서 오버플로우를 일으킬 수 있음
        int mid = left + (right - left) / 2;

        // 왼쪽 부분 배열 정렬
        mergeSort(arr, left, mid);
        // 오른쪽 부분 배열 정렬
        mergeSort(arr, mid + 1, right);

        // 정렬된 두 부분 배열 병합
        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {9, 3, 1, 5, 13, 12};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "원본 배열: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    mergeSort(arr, 0, n - 1);

    cout << "정렬된 배열: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    // 출력 결과
    // 원본 배열: 9 3 1 5 13 12
    // 정렬된 배열: 1 3 5 9 12 13

    return 0;
}

세부 동작

1. 분할
   정렬할 배열 중간 지점을 기준으로 두 개의 하위 배열로 나눈다.
2. 정복
   각 하위 배열은 재귀적으로 병합 정렬을 호출해서 정렬한다.
3. 결합(two pointer)
   정렬된 두 개의 하위 배열을 하나의 정렬된 배열로 병합한다.
   이 때 두 배열의 원소를 순서대로 비교하여 작은 값을 먼저 새로운 배열에 추가한다.

시간 복잡도

데이터가 1개가 될 때까지 반으로 나누는 과정을 통해 생성되는 분할 트리의 높이 ->log N
각 분할 단계 마다 모든 데이터를 병합하여 병합 연산은 단계마다 총 N번 발생
-> 전체 시간 복잡도 = O(N) * O(log N) = O(N log N)

---

계수 정렬

데이터 값 자체를 인덱스로 사용하는 데이터에 의존적인 정렬 방식이다. 각 값의 빈도 수를 세어 그 정보를 기반으로 정렬을 수행한다.
의도 코드

//A는 입력 배열이고, k는 입력 배열의 최대값
COUNTING-SORT(A, k)
  count ← 크기가 k + 1인 0으로 채워진 배열
  output ← 입력 배열과 같은 크기의 배열
  for i = 0 to A.length - 1
      count[A[i]] ← count[A[i]] + 1

  idx ← 0
  for i = 0 to k-1
      while (count[i]--) {
          arr[idx++] = i;
      }

구현 코드

#include <iostream>
using namespace std;
void countingSort(int A[], int k, int size) {
	// 0 ~ 최댓값 개수 만큼 count배열 동적할당, 0으로 초기화
	int* count = new int[k + 1]();
	// count에 빈도수 입력
	for (int i = 0; i < size; i++) {
		count[A[i]]++;
	}
	// A배열에 빈도수만큼 복사 입력
	int idx = 0;
	for (int i = 0; i < k + 1; i++) {
		while (count[i]>0) {
			A[idx++] = i;
			count[i]--;
		}
	}
	// 메모리 해제
	delete[] count;
}
int main() {

	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
	int A[] = { 1, 5, 5, 2, 3, 7, 2, 4, 8, 1 };
	int k = A[0];
	for (auto& i : A) {
		if (i > k) k = i;
	}
	countingSort(A, k, sizeof(A) / sizeof(int));
	for (auto& i : A) {
		cout << i << " ";
	}
	return 0;
}

세부 동작

1. 카운트 배열 생성
   입력 배열의 최댓값이 k일때 크기가 k+1인 count배열을 생성하고 0으로 초기화한다.
2. 빈도수 계산
   입력 배열을 순회하며 각 원소의 값을 인덱스로 사용하여 배열의 해당 위치에 빈도수를 누적한다.

시간 복잡도

count 배열 초기화 -> O(K)
빈도수 확인 -> O(N)
정렬된 배열 생성 -> O(N)
-> 최종 시간 복잡도 = O(N+K)

계수 정렬의 한계

1. 음수 값이 존재하는 경우
   음수 값을 배열의 인덱스로 사용할 수 없기 때문에 계수 정렬을 적용할 수 없다.
2. 원소 값의 범위가 넓거나 듬성듬성 있는 경우
   데이터 범위가 큰 경우 메모리 사용면에서 비효율적이며 사실상 불가능하다.

---

힙 정렬

조건을 만족하는 이진 트리이다. 보통 최대 힙과 최소 힙으로 구분된다.
최대 힙: 모든 부모 노드의 값이 자식 노드의 값보다 크거나 같다.
최소 힙: 부모 노드의 값이 자식 노드보다 작거나 같다.

최대 힙

• build_heap()
• max_heapify()
  buil_heap()이 max_heapify()를 호출하여 최대 힙을 구축하는 구조

max_heapify()

특정 원소를 기준으로 최대 힙의 성질을 만족하도록 재구성하는 함수
의사 코드

// 전역 변수: A (배열), heap_size (힙 크기)

// 인덱스 i를 루트로 하는 트리를 최대 힙 속성을 만족하도록 수정 (Heapify)
max_heapify(i)
  l = LEFT(i)  // 왼쪽 자식 인덱스
  r = RIGHT(i) // 오른쪽 자식 인덱스
  largest = i  // 가장 큰 값의 인덱스 (일단 부모 자신으로 초기화)

  // 왼쪽 자식과 비교
  if l < heap_size and A[l] > A[largest] then
    largest = l
  // 오른쪽 자식과 비교
  if r < heap_size and A[r] > A[largest] then
    largest = r

  // 만약 자식 노드가 부모 노드보다 크다면
  if largest != i then
    swap A[i] and A[largest] // 두 노드의 값을 교환
    max_heapify(largest)    // 교환된 위치(자식 노드)에서 재귀적으로 Heapify 수행

max_heapify() 세부 동작

1. 부모 노드와 자식 노드 비교
2. 부모 노드보다 큰 자식 노드가 있다면 두 노드의 값을 교환
3. 교환된 위치(자식 노드)에서 재귀적으로 max_heapify() 수행
   교환으로 인해 힙 속성이 깨졌는지 확인하는 작업

build_heap()

주어진 데이터 전체에 대해서 최대 힙 조건을 만족하도록 max_heapify()를 수행하는 과정

의사 코드

// A : 힙으로 만들 배열
build_max_heap()
  heap_size = A.length // 배열의 크기를 설정합니다

  // 마지막 non-leaf 노드부터 루트(1번 인덱스)까지 역순으로 반복합니다
  for idx = floor(A.length / 2) down to 1
    max_heapify(idx) // 각 내부 노드에 대해 MAX_HEAPIFY를 호출합니다

build_heap() 세부 동작

1. 제일 아래 non-leaf 노드부터 max_heapify()로 힙 구축
2. A.length / 2 부터 1번 인덱스까지 반복한다.
   인덱스 i인 노드의 자식 노드 인덱스
   왼쪽 자식 노드 인덱스: 2*i
   오른쪽 자식 노드 인덱스: 2*i + 1
   따라서 A.length / 2 이상인 인덱스의 노드는 모두 리프 노드가 되고 max_heapify()를 수행할 필요가 없다.

힙 정렬

힙 정렬은 배열을 오름차순이나 내림차순으로 정렬하는 것을 의미한다. 위에서 설명한 최대 힙을 구축하는 것은 최댓값이 루트 노드(첫 번째 노드)에 있다는 것을 보장하지만 그 아래 노드들의 정렬을 보장하지 않는다. 따라서 힙을 정렬하기 위해서는 build_heap() 이후 정렬 과정이 필요하다.

1. build_heap()
   배열 전체를 최대 힙으로 만든다.

2. 정렬 과정
   heap_size: 정렬 대상 노드의 개수
   heap_size = n일때

   heap_size > 1 동안 반복

   1. 루트 노드A[0]를 힙의 마지막 요소A[n-1]와 교환
      최댓값을 배열 A 의 n-1 인덱스와 교환
   2. heap_size--
      정렬 완료된 값을 끝으로 이동시켰으므로 정렬 대상 노드의 개수를 1 줄인다.
   3. 루트 노드(A[0])에 대해 max_heapify() 수행

   heap_size = 1이면 배열 A는 오름차순으로 정렬된다.

시간 복잡도

단계	시간
힙 만들기	O(N)
정렬 과정(heapify N번)	O(N log N)
전체	O(N log N)

출처: 스파르타코딩 내일배움캠프