[정렬 알고리즘] 합병 정렬, 퀵정렬, 계수 정렬

합병정렬(머지소트)

---

• 주어진 배열을 크기가 1인 배열이 될때까지 두개씩 쪼개나가는 분할 과정을 진행한 후 하나씩 합쳐나가며 정렬을 수행함(분할정복 알고리즘)
• 합병정렬을 위해 추가적인 메모리 공간을 필요로함(제자리 정렬X)
• 중복된 데이터에 대해 입력순서를 유지하는 안정정렬
• 시간복잡도 : O(NlogN)
  • 2개씩 분할하는 과정을 보면 마치 이진트리가 생성되는 절차와 같다. -> logN
  • 크기가 1인 배열이 되면 다시 2개씩 합병하며 정렬을 수행함 -> N
  • 따라서, 정렬에 O(NlogN)의 시간복잡도를 보임

분할정복 알고리즘
분할 정복알고리즘은 큰 하나의 문제를 작은 2개의 문제로 분리하고 각각 해결한 다음 결과를 모아 해결하는 기법이다.
일반적으로 쪼갠 문제를 또다시 쪼개어 나가는 방식으로 순환호출 방식을 이용하여 구현한다.

 

N개의 입력이 있을 때, 분할 과정에서 한번 분할 될때마다 두개의 배열로 나눠지므로

최종적으로 배열의 크기가 1일 때까지 분할 되면 마치 이진트리와 같은 구조가 되므로

분할연산에서 시간 복잡도는 logN을 갖는다.

합병 연산에서는 N개의 자료를 비교하며 정렬을 수행하므로 O(N)

따라서 전체 정렬 시간복잡도는 O(NlogN)

 

[합병정렬 과정]

 

[합병정렬 java코드]

// 병합 정렬 수행
public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;

        // 분할
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 병합
        merge(arr, left, mid, right);
    }
}

// 두 부분 배열 병합
public static void merge(int[] arr, int left, int mid, int right) {
    // 크기 구하기
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 임시 배열 생성
    int[] L = new int[n1];
    int[] R = new int[n2];

    // 데이터 복사
    for (int i = 0; i < n1; ++i)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j)
        R[j] = arr[mid + 1 + j];

    // 병합 과정
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }

    // 남은 요소 복사
    while (i < n1) {
        arr[k++] = L[i++];
    }
    while (j < n2) {
        arr[k++] = R[j++];
    }
}

 

 

퀵정렬

---

• 주어진 원소 중 하나를 pivot이라는 기준점으로 선택하여 pivot 보다 작은 원소는 왼쪽, pivot 보다 큰 원소는 오른쪽에 위치시켜 두개의 부분배열로 나누어가며 최종 부분 배열의 크기가 0이나 1이 될때까지 반복하며 정렬을 수행한다.(분할정복 알고리즘)
• 추가적인 메모리 공간을 요구하지 않는다.(제자리 정렬)
• 합병정렬의 경우 나뉘어지는 부분 배열의 크기가 같은 균등 분할을 진행하지만, 퀵정렬의 경우 pivot 값에 따라 불균등하게 나뉠 수 있다.
• 시간복잡도 : O(logN)
  
  • 피벗을 정하고 정렬을 수행하는데 O(N)
  • 두개의 부분배열로 나누는데 O(logN)
  • 따라서, 전체 정렬에 O(logN)
• 최악의 경우 : O(N^2)
  • pivot이 중간값이 아니고 한쪽으로 치어쳐진 경우 불균등 배열이 편향된 트리가 나올 수 있음
    이로인해, 분할에 최약의 경우 O(N)을 갖게되어 전체 정렬 O(N^2)을 갖게 될 수 있다.

[퀵정렬의 과정]

 

[퀵정렬 java 코드]

// 퀵 정렬 함수
public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        // 분할
        int pivotIndex = partition(arr, low, high);

        // 재귀적으로 정렬
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

// 파티션 함수: 피벗 기준으로 정렬
public static int partition(int[] arr, int low, int high) {
    int pivot = arr[high]; // 마지막 요소를 피벗으로 선택
    int i = low - 1; // 작은 값의 인덱스

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            // swap arr[i]와 arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // 피벗을 제자리로 이동
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;
}

 

합병정렬과 퀵정렬의 차이

---

	합병정렬	퀵정렬
제자리 정렬	O	X	제자리 정렬은 메모리 공간 효율 뿐만 아니라, 주어진 배열에만 접근 하므로 지역성과 연속성을 갖으므로 cpu 캐시를 통해 좋은 성능을 갖출 수 있다.
균등/불균등	균등	불균등	퀵정렬의 경우, 한쪽으로 치우처진 편향된 구조로 배열이 나뉘어질 수 있어 이로인해 시간복잡도 최악의 경우 O(N^2)을 갖는다.
공간복잡도	N	logN	합병정렬은 주어진 배열과 크기가 같은 임시 배열이 필요하며, 퀵정렬은 정렬을 수행하기 위한 스택 공간만 추가적으로 필요로 한다. (합병정렬도 스택 logN만큼 필요하지만 N이 더 크므로 무시)

 

계수정렬

---

계수정렬은 배열 내에 존재하는 요소가 몇번 나왔는지 count를 계산하고 그 값을 기준으로 요소가 존재해야할 위치를 찾아 정렬하는 방식이다.

별도의 count값을 기록하는 배열을 추가적으로 필요하고 각 값에 해당하는 인덱스에 갯수를 적고 누적합을 계산한다.

누적합을 계산하는 이유는 인덱스에 해당하는 값 앞에 몇개의 요소가 존재하는지 구분하기 위한 목적이다.

따라서 counting 배열의 각 인덱스의 값에 -1을 하면 각 요소의 위치를 알 수 있다.

(이때 역순으로 배열을 순회하면서 정렬 결과를 만들어야 함, count-1 하기 때문에)

 

별도의 메모리 공간을 필요(제자리 정렬 아님)로 하지만 O(N)의 시간복잡도를 갖기에 매우 빠른 성능을 갖고 있다.

다만 숫자의 범위가 매우 크고 고르게 분포되어있지 않을 때, 가장 큰 값 만큼의 추가 배열 공간을 필요로 하기 때문에 공간이 매우 비효율적으로 사용될 수 있는 단점이 있다.

(또한 정수에만 사용될 수 있음)

 

[계수정렬 java코드]

public static void countingSort(int[] arr) {
    if (arr.length == 0) return;

    // 1. 배열의 최댓값과 최솟값 찾기
    int max = arr[0];
    int min = arr[0];
    for (int num : arr) {
        if (num > max) max = num;
        if (num < min) min = num;
    }

    // 2. 범위 크기 계산 (min부터 max까지)
    int range = max - min + 1;

    // 3. 카운트 배열 생성 및 초기화
    int[] count = new int[range];

    // 4. 각 값의 출현 횟수 세기
    for (int num : arr) {
        count[num - min]++;
    }

    // 5. 누적합 계산 (정렬된 위치 계산용)
    for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }

    // 6. 출력 배열 생성 (정렬 결과 저장)
    int[] output = new int[arr.length];

    // 7. 뒤에서부터 원소를 순회하며 output에 넣기 (안정 정렬 위해)
    for (int i = arr.length - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }

    // 8. 결과를 원래 배열에 복사
    System.arraycopy(output, 0, arr, 0, arr.length);
}

 

Arrays.sort와 Collections.sort의 차이

---

Arrays.sort는 기본타입에 대해 더블 피벗 퀵정렬을 수행한다. 

피벗을 두개 두어 부분배열을 3개로 나누어 정렬하는 방식이다.

세 구간으로 나누어 각각 재귀적으로 수행하므로 퀵정렬보다 빠르다.

시간복잡도는 O(NlogN)이다.

참조타입에 대해서는 TimeSort(삽입정렬 + 합병정렬)을 사용한다.

시간복잡도는 O(NlogN)이다.

 

Collections.sort는 내부적으로 Arrays.sort를 사용한다.

컬렉션은 참조타입만 저장 가능하므로 TimeSort를 사용하게 된다.