[ALGORITHM] 08. O(n log n)

O(n log n)은 로그 선형(Log-Linear) 시간 복잡도를 가지는 알고리즘을 나타낸다.

이는 입력 크기 n에 대해 n과 log n의 곱에 비례하는 실행 시간을 갖는 알고리즘을 의미하며, 

주로 효율적인 정렬 알고리즘에서 나타난다.

 

아래는 가장 널리 사용되는 O(n log n) 알고리즘인 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)이다.

 

// 두 변수의 값을 교환하는 함수
void swap(int* a, int* b) {

    int temp = *a;
    *a = *b;
    *b = temp;
}

// 배열을 특정한 피벗을 기준으로 두 부분으로 나누고, 피벗의 정확한 위치를 반환
int partition(int arr[], int low, int high) {

    int pivot = arr[high];  // 피벗은 배열의 마지막 요소로 선택
    int i = (low - 1);  // 작은 요소들의 마지막 인덱스

    // 배열을 순회하며 피벗을 기준으로 작은 값들을 좌측에 배치
    for (int j = low; j <= high - 1; j++) {
    
        if (arr[j] < pivot) {
        
            i++;
            swap(&arr[i], &arr[j]);
        }
    }

    // 피벗의 정확한 위치를 찾아서 정렬된 배열의 중간으로 이동
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// 배열을 퀵 정렬하는 함수
void quickSort(int arr[], int low, int high) {

    if (low < high) {
    
        // 피벗을 기준으로 배열을 분할하고, 피벗의 정확한 위치를 얻음
        int pi = partition(arr, low, high);

        // 분할된 두 부분에 대해 재귀적으로 퀵 정렬 수행
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}