정렬

정렬은 데이터를 정해진 기준에 따라 배치해 의미 있는 구조로 재설정하는 것을 말한다.

정렬 알고리즘	평균 시간복잡도	정의	안정성
퀵 정렬	O(nlogn)	기준이 되는 pivot 값을 선정해 해당 값을 기준으로 데이터를 분할하며 정렬하는 방식	❌
병합 정렬	O(nlogn)	정렬된 부분 집합들을 병합하며 전체 데이터를 정렬하는 방식	✅
힙 정렬	O(nlogn)	힙 자료구조를 이용해 가장 큰 값(또는 가장 작은 값)을 차례로 꺼내며 정렬하는 방식	❌
삽입 정렬	O(n²)	정렬된 영역에 데이터를 하나씩 적절한 위치에 삽입하며 정렬하는 방식	✅
계수 정렬	O(n+k)	데이터의 값을 인덱스로 활용해 등장 횟수를 기록하며 정렬하는 방식	✅
버블 정렬	O(n²)	인접한 데이터를 비교하고, swap 연산을 수행하며 정렬하는 방식	✅
선택 정렬	O(n²)	전체 데이터 중 가장 큰 값(또는 가장 작은 값)을 선택해 앞쪽에 배치하며 정렬하는 방식	❌

 

어떤 정렬을 언제 써야 할까?

데이터가 거의 정렬되어 있는 경우

• 삽입 정렬

데이터가 크고 빠른 성능이 필요한 경우

• 퀵 정렬

정렬 안정성이 중요한 경우

• 병합 정렬, 계수 정렬

값의 범위가 제한된 정수인 경우

• 계수 정렬

우선순위가 중요한 경우

• 힙 정렬

 

퀵 정렬

기준이 되는 pivot 값을 선정해 해당 값을 기준으로 데이터를 분할하며 정렬하는 방식

1. 배열에서 pivot을 하나 선택한다.
2. 배열을 pivot 기준으로 나눈다.
   • pivot보다 작은 값은 왼쪽
   • pivot보다 큰 값은 오른쪽
3. 각 부분 배열에 대해 같은 과정을 재귀적으로 반복한다.
4. 최종적으로 정렬된 배열 완성

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

private 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, j);
        }
    }
    swap(arr, i + 1, high);
    return i + 1;
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

 

병합 정렬

정렬된 부분 집합들을 병합하며 전체 데이터를 정렬하는 방식

1. 배열을 반으로 나눈다. (재귀)
2. 나눠진 배열들끼리 병합한다. 이때 작은 값을 먼저 골라 정렬된 상태로 병합한다.
3. 병합을 반복한다.
4. 최종적으로 정렬된 배열 완성

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

private static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    System.arraycopy(temp, 0, arr, left, temp.length);
}

 

힙 정렬

힙 자료구조를 이용해 가장 큰 값(또는 가장 작은 값)을 차례로 꺼내며 정렬하는 방식

1. 배열을 최대 힙으로 변환한다.
2. 힙의 루트(최댓값)를 꺼내서 배열의 끝 요소와 교환한 뒤 힙을 재구성한다.
3. 배열의 앞부분만 남을 때까지 같은 과정을 반복한다.
4. 최종적으로 정렬된 배열 완성

public static 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--) {
        swap(arr, 0, i);
        heapify(arr, i, 0);
    }
}

private static void heapify(int[] arr, int n, int i) {
    int largest = i, left = 2 * i + 1, 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) {
        swap(arr, i, largest);
        heapify(arr, n, largest);
    }
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

 

삽입 정렬

정렬된 영역에 데이터를 하나씩 적절한 위치에 삽입하며 정렬하는 방식

1. 배열의 두 번째 요소부터 시작한다.
2. 이 값을 앞쪽 정렬된 부분과 비교하면서 적절한 위치에 삽입한다.
3. 이 과정을 배열 끝까지 반복한다.
4. 최종적으로 정렬된 배열 완성

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i], j = i - 1;
        while (j >= 0 && arr[j] > key) arr[j + 1] = arr[j--];
        arr[j + 1] = key;
    }
}

 

계수 정렬

데이터의 값을 인덱스로 활용해 등장 횟수를 기록하며 정렬하는 방식

1. 정렬할 데이터의 최댓값을 기준으로 count 배열을 만든다.
2. 주어진 배열을 순회하며 각 값의 등장 횟수를 count 배열에 기록한다.
3. count 배열을 기반으로 정렬된 배열을 구성한다.
4. 이 과정에서 값을 직접 비교하지 않고도 정렬된 결과를 얻을 수 있다.

public static void countingSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    int[] count = new int[max + 1];
    for (int num : arr) count[num]++;
    int idx = 0;
    for (int i = 0; i < count.length; i++) {
        while (count[i]-- > 0) arr[idx++] = i;
    }
}

 

버블 정렬

인접한 데이터를 비교하고, swap 연산을 수행하며 정렬하는 방식

1. 배열의 맨 앞부터 시작해서 인접한 두 요소를 차례대로 비교한다.
2. 만약 왼쪽 요소가 오른쪽 요소보다 더 크면 두 요소의 위치를 서로 바꾼다.
3. 이 과정을 배열 끝까지 반복하면 가장 큰 값이 배열의 맨 뒤로 이동하게 된다. ➡️ 1회차 반복 끝
4. 이 과정을 배열 전체가 정렬될 때까지 반복한다. 즉, 매 반복마다 가장 큰 값이 하나씩 "확정"되어 뒤로 밀려나간다.
5. 어떤 반복에서든 교환이 한 번도 일어나지 않으면 배열은 이미 정렬된 상태이므로 정렬을 조기에 종료한다.

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;        
        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;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

 

선택 정렬

전체 데이터 중 가장 큰 값(또는 가장 작은 값)을 선택해 앞쪽에 배치하며 정렬하는 방식

1. 배열의 맨 앞부터 시작해서 남은 부분 중 가장 작은 값을 찾는다.
2. 찾은 값을 현재 위치의 값과 교환한다.
3. 이 과정을 배열 전체가 정렬될 때까지 반복한다.
4. 결국 매 반복마다 가장 작은 값을 선택해서 앞으로 배치하는 방식이다.

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        int temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
    }
}