정렬 알고리즘

irenett·2024년 10월 21일

정렬 알고리즘 총 정리

1. 버블 정렬 (Bubble Sort)

시간 복잡도: 최악 및 평균 O(N^2), 최선 O(N)
특징: 인접한 두 요소를 비교하여 정렬함. 데이터가 거의 정렬되어 있을 때 효율적일 수 있음.

public void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
    	//인접한 요소를 비교하고 하나씩 나아가며 정렬된 원소를 제외한 나머지 반복
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 현재 원소가 다음 원소보다 크면 교환
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

2. 선택 정렬 (Selection Sort)

시간 복잡도: O(N^2)
특징: 매 반복마다 최소값을 찾아 해당 위치로 이동.

public void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
    	// i를 최소값으로 가정
        int minIndex = i;
        // i 다음부터 끝까지 최소 찾기
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // 최소값을 현재 위치로 교환
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

3. 삽입 정렬 (Insertion Sort)

시간 복잡도: 최악 및 평균 O(N^2), 최선 O(N)
특징: 이미 정렬된 부분과 비교하며 적절한 위치에 삽입함. 데이터가 거의 정렬되어 있을 때 매우 효율적.

public void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
    	// 현재 요소를 키로 설정
        int key = arr[i];
        int j = i - 1;
        // 이전 요소들이 현재 키보다 크면면 반복하며 오른쪽으로 이동
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 키 삽입
        arr[j + 1] = key;
    }
}

4. 병합 정렬 (Merge Sort)

시간 복잡도: O(N log N)
특징: 분할 정복 전략을 사용. Stable한 정렬 알고리즘이며, 추가적인 메모리 공간을 사용.

public 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);
    }
}

private 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 i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];

	// 두 배열을 병합하며 정렬
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

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

5. 퀵 정렬 (Quick Sort)

시간 복잡도: 최악 O(N^2), 평균 및 최선 O(N log N)
특징: 분할 정복 전략을 사용. 피벗을 기준으로 좌우로 나누어 정렬. Unstable 정렬 알고리즘.

public 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);
    }
}

private 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++;
            // i와 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;
}

6. 힙 정렬 (Heap Sort)

시간 복잡도: O(N log N)
특징: 최대 힙 또는 최소 힙을 사용하여 정렬. Unstable 정렬 알고리즘.

public void heapSort(int[] arr) {
    int n = arr.length;
    
    // 배열을 최대 힙으로 만들기
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // 힙에서 원소 하나씩 꺼내 정렬
    for (int i = n - 1; i > 0; i--) {
    	// 현재 루트값(=최대)와 끝 요소를 교환
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        
        // 줄어든 힙 재정렬
        heapify(arr, i, 0);
    }
}

private void heapify(int[] arr, int n, int i) {
    int largest = i; // 현재 루트
    int left = 2 * i + 1; // 왼쪽 자식
    int right = 2 * i + 2; // 오른쪽 자식
    
    // 왼쪽 자식 > 현재 루트 면 변경
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    
    // 오른쪽 자식 > 현재 루트면 변경
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    
    // 루트 변경됐으면 교환하고 재귀
    if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;
        heapify(arr, n, largest);
    }
}

7. 계수 정렬 (Counting Sort)

시간 복잡도: O(N + K) (N: 배열 길이, K: 최대값)
특징: 데이터의 범위가 제한된 경우 매우 빠르게 동작. 정수형 데이터만 처리 가능.

public void countingSort(int[] arr) {
	// 배열의 최댓값 찾기
    int max = Arrays.stream(arr).max().orElse(Integer.MIN_VALUE);
    
    // count 배열 생성
    int[] count = new int[max + 1];
    
    // 각 원소의 빈도를 count에 저장
    for (int i : arr) {
        count[i]++;
    }
    
    // count 배열 돌면서 정렬된 결과 원본 배열에 저장
    int index = 0;
    for (int i = 0; i < count.length; i++) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }
}

Quick Sort와 Merge Sort를 비교해 주세요.

둘다 기본적으로 분할 정복 전략을 사용하나,

특징

Quick Sort: 피벗(pivot)을 기준으로 배열을 두 개의 부분 배열로 분할하고, 피벗보다 작은 값과 큰 값을 각각의 부분 배열에 배치한 후, 재귀적으로 정렬합니다.
Merge Sort: 배열을 반으로 계속 분할하여 더 이상 분할할 수 없는 크기까지 나눈 뒤, 분할된 부분 배열들을 정렬하면서 병합해 나갑니다.

시간 복잡도

Quick Sort:
- 평균/최선 시간 복잡도: O(N log N)
- 최악 시간 복잡도: O(N^2) (피벗 선택이 좋지 않을 경우)
Merge Sort:
- 시간 복잡도: O(N log N)

공간 복잡도

Quick Sort: O(log N) (재귀 호출 스택 사용하기 때문에 추가 메모리가 거의 필요하지 않음)
Merge Sort: O(N) (분할된 배열을 병합하기 위한 추가 메모리 필요)

정렬의 안정성

Quick Sort: 불안정한 정렬 (피벗을 기준으로 이동하기 때문에 같은 값의 원소가 입력 순서대로 유지되지 않을 수 있음)
ex) 입력 배열: [5(A), 3, 3, 4, 5(B)]
정렬 결과: [3, 3, 4, 5(B), 5(A)]
Merge Sort: 안정적인 정렬 (병합 단계에서 두 개의 부분 배열을 합칠 때 왼쪽부터 먼저 추가하면서 병합하기 때문에 같은 값의 원소가 입력 순서대로 유지됨)

정리

항목	Quick Sort	Merge Sort
시간 복잡도	평균 O(N log N), 최악 O(N^2)	항상 O(N log N)
공간 복잡도	O(log N)	O(N)
안정성	불안정함	안정적
추가 메모리 사용	매우 적음	추가 메모리 필요
사용 사례	메모리가 제한된 환경, 대량의 데이터	안정성이 중요한 경우, 외부 정렬
특징	평균적으로 빠르고 메모리 효율적	항상 일정한 시간 복잡도 보장, 추가 메모리 필요

Quick Sort에서 O(N²)이 걸리는 예시를 들고, 이를 개선할 수 있는 방법에 대해 설명해 주세요.

피봇을 기준으로 배열을 분할하기 때문에, 분할이 잘못되면 최악의 경우가 발생할 수 있습니다.
특히, 피봇이 배열의 최댓값 혹은 최소값으로 계속 선택될 경우, 배열은 한쪽만 계속 분할되고 정렬되지 않은 부분의 크기가 1씩만 줄어들어 전체 시간복잡도가 O(N^2)이 됩니다.

이미 정렬된 배열 [1, 2, 3, 4, 5] 이 있다고 치겠습니다.
Quick Sort가 피벗을 항상 마지막 원소로 선택한다고 가정하면,

첫 번째 피벗은 5가 선택됩니다. 모든 요소가 피벗보다 작기 때문에, 정렬되지 않은 부분은 피벗만 분리하여 [1, 2, 3, 4]가 됩니다.
다시 마지막 요소인 4를 피봇으로 선택합니다. 똑같이 모든 요소가 피벗보다 작기 때문에 피벗만 분리하여 정렬되지 않은 부분은 [1, 2, 3]이 됩니다
...
이처럼 반복적으로 배열의 크기가 매번 1 씩 줄어들어 시간 복잡도는 O(N^2)가 됩니다.

네, Quick Sort에서 피벗 선택은 알고리즘의 핵심적인 부분이지만, 피벗은 꼭 마지막 값으로 선택할 필요는 없습니다. 원하는 기준에 따라 유연하게 피벗을 선택할 수 있습니다. 피벗 선택 방식에 따라 Quick Sort의 성능이 크게 달라질 수 있기 때문에, 다양한 전략이 존재합니다. 각각의 전략은 특정 상황에서 성능을 개선하거나, 최악의 경우를 방지하는 데 도움이 됩니다.

개선 방안

랜덤 피벗 (Random Pivot):
- 특징: 배열 내에서 랜덤 인덱스를 피벗으로 선택합니다. 최악 발생 가능성을 줄일 수 있습니다. 평균적인 성능이 중요할 때, 또는 입력 데이터의 패턴을 알 수 없을 때 유용합니다.
Median of Three:
- 특징: 배열의 첫 번째 요소, 중간 요소, 마지막 요소의 중앙값(arr[low], arr[(low + high) / 2], arr[high])을 피벗으로 선택합니다.
  중간 크기의 배열(수십~수백개)이나 정렬된 배열에 대해 최적화된 성능을 기대할 때 유용합니다.
Median of Medians:
- 특징: 배열을 작은 그룹으로 나누어 각 그룹의 중앙값을 찾고, 그 중앙값들 중에서 중앙값을 피벗으로 선택하는 방법입니다. 최악의 경우를 방지하면서, 일정한 성능을 보장하고자 할 때 유용합니다.

Stable Sort가 무엇이고, 어떤 정렬 알고리즘이 Stable한지 설명해 주세요.

Stable Sort: 동일한 값의 원소가 정렬 후에도 상대적인 순서를 유지하는 정렬 알고리즘

특히 Stable Sort가 중요한 이유는 특정 키 값에 따라 데이터를 정렬한 후, 다시 다른 기준으로 정렬해야 하는 경우 때문입니다. 예를 들어 사람의 나이 순으로 정렬 후, 이름 순으로 정렬할 경우 첫번째 정렬의 상대적인 순서가 보장되는 것이 중요합니다.

Stable한 정렬 알고리즘: 버블 정렬, 삽입 정렬, 병합 정렬, 계수 정렬, 기수 정렬 등
불안정한 정렬 알고리즘: 퀵 정렬, 힙 정렬, 선택 정렬 등

Merge Sort를 재귀를 사용하지 않고 구현할 수 있을까요?

Bottom-up Merge Sort :

반복문을 활용한 비재귀 방식으로 구현한 머지 소트로, 기존과 동일한 시간복잡도로 배열의 크기를 점점 두 배로 키워가며 정렬합니다.
추가 메모리를 사용하는 양은 동일하지만, 재귀 호출 스택 메모리를 사용하지 않기 때문에 스택 오버플로우가 발생하지 않아 메모리 효율성이 높아질 수 있습니다.

방식

기본적으로 배열을 크기가 1인 부분 배열끼리 병합하면서 2, 4, 8, 등 작은 크기부터 시작하여 점점 큰 크기로 모든 원소가 정렬될 때까지 병합합니다.

코드

public void iterativeMergeSort(int[] arr) {
    int n = arr.length;
	
    // 반복문으로 배열 크기를 두 배씩 증가
    for (int currSize = 1; currSize < n; currSize *= 2) {
        for (int leftStart = 0; leftStart < n - 1; leftStart += 2 * currSize) {
            int mid = Math.min(leftStart + currSize - 1, n - 1);
            int rightEnd = Math.min(leftStart + 2 * currSize - 1, n - 1);
			
            // 두 개의 부분 배열을 병합
            merge(arr, leftStart, mid, rightEnd);
        }
    }
}

private 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 i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];

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

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

Radix Sort에 대해 설명해 주세요.

Radix Sort / 기수 정렬 :

정수나 문자열 같은 데이터를 자릿수를 기준으로 정렬 알고리즘입니다. 각 자릿수를 하위 자릿수부터 상위 자릿수 또는 그 반대로 정렬하여 전체 데이터를 정렬합니다.
정렬 대상이 정수 또는 고정 길이 문자열이어야 합니다.
Stable 정렬
시간복잡도 : O(d(n+k)) => 최대 자릿수의 개수 (배열의 크기 + 자릿수의 숫자 범위)
공간복잡도 : O(n+k)

LSD (Least Significant Digit) / MSD (Most Significant Digit) 방식 두가지로 나뉩니다.

각 자릿수(1의 자리, 10의 자리, 100의 자리, ...)를 기준으로 데이터를 정렬합니다. 각 자릿수마다 계수 정렬(Counting Sort)와 같은 안정적인 정렬 알고리즘을 사용하여 정렬을 반복합니다.

동작 과정

가장 낮은 자릿수부터 정렬합니다. (1의 자리부터 시작)
정렬된 결과를 기준으로 다음 자릿수를 정렬합니다. (10의 자리, 100의 자리, ...)
모든 자릿수에 대해 정렬이 끝나면, 전체 데이터가 정렬됩니다.

예시
입력 배열: [170, 45, 75, 90, 802, 24, 2, 66]

1의 자리 기준 정렬: [170, 90, 802, 2, 24, 45, 75, 66]
10의 자리 기준 정렬: [802, 2, 24, 45, 66, 170, 75, 90]
100의 자리 기준 정렬: [2, 24, 45, 66, 75, 90, 170, 802]

최종 결과: [2, 24, 45, 66, 75, 90, 170, 802]

코드 구현

import java.util.Arrays;

public class RadixSort {
    // Radix Sort 메소드
    public void radixSort(int[] arr) {
        // 배열의 최대값을 구함
        int max = Arrays.stream(arr).max().getAsInt();

        // 자릿수 기준으로 Counting Sort를 반복
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }

    // 특정 자릿수에서의 Counting Sort 메소드
    private void countingSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n]; // 정렬된 결과를 저장할 배열
        int[] count = new int[10]; // 0~9의 카운트를 저장할 배열

        // 현재 자릿수에 대한 카운트 계산
        for (int i = 0; i < n; i++) {
            int digit = (arr[i] / exp) % 10;
            count[digit]++;
        }

        // 누적 합 계산 (안정적인 정렬을 위해)
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 출력 배열을 생성 (안정성을 보장하기 위해 역순으로 처리)
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

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

Bubble, Selection, Insertion Sort의 속도를 비교해 주세요.

값이 거의 정렬되어 있거나, 아예 정렬되어 있다면, 위 세 알고리즘의 성능 비교 결과는 달라질까요?

알고리즘	최선 시간 복잡도	평균 시간 복잡도	최악 시간 복잡도	비교 및 교환 횟수	특징
버블 정렬	O(N) = 이미 정렬	O(N^2)	O(N^2)	많은 교환	교환이 많이 일어나서 느림
선택 정렬	O(N^2)	O(N^2)	O(N^2)	비교는 많고 교환은 적음	교환이 적음, 항상 일정한 시간
삽입 정렬	O(N) = 이미 정렬	O(N^2)	O(N^2)	비교와 삽입을 동시에 수행	거의 정렬된 배열에서 매우 빠름

버블 정렬

이미 정렬된 경우:
최선의 경우, 버블 정렬은 첫 번째 순환을 마친 후 교환이 발생하지 않으면 바로 종료할 수 있습니다. 이 경우, 시간 복잡도는 O(N)으로 매우 빠릅니다.
거의 정렬된 경우:
교환이 많이 일어나지 않기 때문에, 거의 정렬된 경우에도 성능이 상대적으로 좋아질 수 있습니다.

선택 정렬

이미 정렬된 경우:
선택 정렬은 항상 모든 원소를 비교하고, 최소값을 찾아 교환하는 구조이기 때문에, 배열이 이미 정렬되어 있더라도 성능 개선이 없습니다.
거의 정렬된 경우:
비교와 교환이 적어 효율적인 경우도 있지만, 기본적으로 비교 횟수는 항상 일정하기 때문에 성능은 변하지 않습니다.

삽입 정렬

이미 정렬된 경우:
배열이 정렬되어 있으면 각 요소는 제자리에 삽입되므로, 비교만 진행하고 교환이 발생하지 않습니다. 이때 시간 복잡도는 O(N)입니다.
거의 정렬된 경우:
필요한 만큼만 교환이 이루어지므로 성능이 크게 향상됩니다.
이 경우 시간 복잡도는 O(N)에 가깝게 줄어들 수 있습니다.

본인이 사용하고 있는 언어에선, 어떤 정렬 알고리즘을 사용하여 정렬 함수를 제공하고 있을까요?

자바 기준으로, Arrays.sort()와 Collections.sort() 함수는 각각 Dual-Pivot Quick Sort와 Timsort 알고리즘을 사용합니다.

Arrays.sort() (Primitive 타입)

사용 알고리즘: Dual-Pivot Quick Sort
두 개의 피벗을 사용하여 배열을 세 개의 부분 배열로 나눕니다. 이로 인해 기존 Quick Sort보다 성능이 더 나을 수 있습니다.
평균 시간 복잡도는 O(N log N), 최악은 O(N^2)입니다.
불안정한 정렬 알고리즘입니다.

Arrays.sort() (Reference 타입)

사용 알고리즘: Timsort
Timsort는 Merge Sort와 Insertion Sort를 결합한 알고리즘입니다.
이미 정렬된 배열 또는 부분적으로 정렬된 배열에서 매우 효율적입니다.
시간 복잡도는 O(N log N)입니다.
안정한 정렬 알고리즘입니다.

Collections.sort() (List)

사용 알고리즘: Timsort

정렬해야 하는 데이터는 50G인데, 메모리가 4G라면, 어떤 방식으로 정렬을 진행할 수 있을까요?

50GB의 데이터를 정렬해야 하는데, 시스템의 메모리가 4GB인 경우, 한 번에 전체 데이터를 메모리에 적재할 수 없으므로, 이 상황에서는 외부 정렬(External Sorting) 기법을 사용하는 것이 일반적입니다.
외부 정렬은 데이터를 여러 번에 나누어 처리하고, 저장 매체(디스크)에 저장하면서 정렬을 진행하는 방법입니다.
Hadoop이나 Spark 같은 분산 시스템에서는 이러한 외부 정렬을 기본적으로 처리할 수 있는 방법을 제공합니다.

K-웨이 병합 정렬(Multi-way Merge Sort)

외부 정렬에서 자주 사용하는 방법으로, 데이터를 작은 덩어리로 나누어 정렬한 후, 이 정렬된 덩어리들을 다시 병합하는 방식으로 진행됩니다.
이 방법은 대용량 데이터를 처리할 때 매우 유용하며, 다음과 같은 단계로 수행됩니다.
O(N log (N / M))으로, N은 데이터의 크기, M은 메모리 크기입니다.
내부 정렬을 수행하며 데이터를 여러 차례 읽고 쓰는 과정에서 추가적인 오버헤드가 발생합니다.

단계

데이터를 작은 덩어리로 나누어 정렬:
- 메모리 용량이 4GB이므로, 데이터를 4GB 단위로 쪼개어 처리해야 합니다.
- 먼저 50GB의 데이터를 읽어와서, 4GB씩 나누어 각 덩어리를 정렬합니다.
- 정렬할 때는 일반적인 내부 정렬 알고리즘(Quick Sort 또는 Merge Sort같은..)을 사용할 수 있습니다.
- 정렬된 각 덩어리를 디스크에 임시 파일로 저장합니다.
50GB의 데이터를 4GB씩 나누면 12개의 정렬된 덩어리(임시 파일)가 생성됩니다.
정렬된 덩어리들을 병합:
- 모든 덩어리가 정렬된 후에는 병합 과정이 필요합니다. 이때는 K-웨이 병합 알고리즘을 사용합니다.
- 한 번에 최대 메모리 크기만큼의 데이터를 읽어오면서 여러 개의 파일을 동시에 병합합니다.
- 예를 들어, 4GB 메모리를 사용할 수 있으므로 12개의 정렬된 파일에서 각각의 일부 데이터를 메모리로 불러와, 정렬된 순서대로 병합합니다.
- 병합 과정에서는 각 파일의 첫 번째 요소를 비교하여 가장 작은 값을 결과 파일에 기록하고, 다음 값을 읽어오는 과정을 반복합니다.
최종 정렬된 결과 저장:
- 모든 덩어리가 병합되면, 최종적으로 정렬된 데이터를 하나의 파일로 출력합니다.

irenett

이전 포스트

Java Exception

다음 포스트

정렬 알고리즘