[CS] 정렬 알고리즘 (버블 정렬, 선택 정렬, 퀵 정렬, 병합 정렬, 힙 정렬)

알고리즘은 문제를 해결하기 위한 명령어의 집합이며, 입력 데이터를 받아서 출력 데이터를 생성하는 과정을 의미합니다. 이러한 알고리즘 중 정렬 알고리즘에 대하여 알아보겠습니다.

목차

버블 정렬

선택 정렬

삽입 정렬

퀵 정렬

병합 정렬

힙 정렬

---

버블 정렬

버블 정렬은 인접한 두 개의 원소를 비교하고, 필요에 따라 위치를 교환하면서 정렬하는 알고리즘입니다. 시간 복잡도는 최선, 평균, 최악의 경우 모두 O(n^2)입니다. 따라서 큰 크기의 배열에서는 비효율적일 수 있습니다.

동작 방식

1. 배열의 첫 번째 원소부터 인접한 원소와 비교합니다.

2. 만약 인접한 원소가 순서에 맞지 않다면 위치를 교환합니다.

3. 배열의 끝까지 위의 과정을 반복하며, 가장 큰 원소가 배열의 마지막으로 이동합니다.

4. 위의 과정을 배열의 길이만큼 반복합니다.

예시 코드

public class BubbleSort {
    public static 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;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 12, 1, 9};
        bubbleSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

---

선택 정렬

선택 정렬은 주어진 배열에서 최솟값을 선택하여 정렬된 부분과 교환하는 과정을 반복하여 정렬하는 알고리즘입니다. 시간 복잡도는 최선, 평균 최악 모두 O(n^2)입니다. 비교 연산의 횟수가 상수이기 때문에 입력 데이터에 민감하지 않은 특징이 있습니다.

동작 방식

1. 주어진 배열에서 가장 작은 원소를 찾습니다.

2. 해당 원소를 배열의 맨 앞 원소와 교환합니다.

3. 정렬된 부분이 하나씩 늘어나며, 위의 과정을 반복하여 전체 배열을 정렬합니다.

예시 코드

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = 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;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 12, 1, 9};
        selectionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

---

삽입 정렬

삽입정렬은 배열의 요소를 하나씩 선택하여 이미 정렬된 부분의 올바른 위치에 삽입하는 방식으로 정렬하는 알고리즘입니다. 작은 규모의 배열에 대하여 효율적인 알고리즘 중 하나입니다. 시간 복잡도는 최선의 경우 O(n), 평균 및 최악의 경우 O(n^2)입니다.

동작 방식

1. 두 번째 원소부터 시작하여, 이전의 정렬된 부분과 비교하여 올바른 위치에 삽입합니다.

2. 선택한 원소를 이전 정렬된 부분의 적절한 위치에 삽입하고, 다른 원소들을 오른쪽으로 한 칸씩 이동시킵니다.

3. 배열의 첫 번째 원소까지 위의 과정을 반복하여 정렬을 완료합니다.

예시 코드

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            // key보다 큰 원소는 오른쪽으로 이동
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 12, 1, 9};
        insertionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

---

퀵 정렬

퀵 정렬은 배열을 분할하고 재귀적으로 정렬하는 방식으로 동작합니다. 특정한 원소를 기준으로 배열을 분리하는데, 이를 pivot이라고 합니다. 퀵 정렬은 평균적으로 가장 빠른 정렬 알고리즘 중 하나입니다. 시간 복잡도는 O(nlogn), 최악의 경우 O(n^2)입니다.

동작 방식

1. 배열에서 pivot을 선택합니다. pivot은 보통 배열의 중간 원소를 선택합니다.

2. pivot을 기준으로 작은 원소는 왼쪽에, 큰 원소는 오른쪽에 위치하도록 배열을 분할합니다.

3. 분할된 부분 배열에 대해 재귀적으로 퀵 정렬을 수행합니다.

4. 분할된 부분 배열의 크기가 1이하가 될 때까지 위의 과정을 반복합니다.

예시 코드

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 분할(Divide)
            int pivotIndex = partition(arr, low, high);

            // 피벗을 기준으로 왼쪽과 오른쪽 부분 배열에 대해 재귀적으로 정렬(Conquer)
            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++;
                // 원소 교환
                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;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 12, 1, 9};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

---

병합 정렬

병합 정렬은 배열을 반으로 분할하고, 분할된 배열을 정렬한 뒤 병합하여 최종적으로 정렬된 배열을 얻습니다. 시간 복잡도는 항상 O(nlogn)입니다. 배열을 반으로 분할하는 단계가 O(logn)이고 분할된 배열을 병합하는 단계가 O(n)의 시간이 소요됩니다.

동작 방식

1. 배열을 반으로 분할합니다.

2. 각 부분 배열에 대해 재귀적으로 병합 정렬을 수행합니다.

3. 분할된 부분 배열을 병합하여 정렬된 배열을 얻습니다.

예시 코드

public class MergeSort {
    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[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        // 왼쪽과 오른쪽 부분 배열에 원소 복사
        for (int i = 0; i < n1; i++) {
            leftArr[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            rightArr[j] = arr[mid + 1 + j];
        }

        int i = 0, j = 0;
        int k = left;

        // 두 부분 배열을 비교하여 병합
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i];
                i++;
            } else {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }

        // 남은 원소들을 복사
        while (i < n1) {
            arr[k] = leftArr[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 12, 1, 9};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

---

힙 정렬

힙 정렬은 힙 자료구조를 사용하여 배열을 정렬하는 알고리즘입니다. 힙은 완전 이진트리의 일종으로, 최대 힙 또는 최소 힙의 조건을 만족합니다. 힙 정렬은 힙 자료구조를 구성하고, 최대/최소 원소를 반복적으로 교환하여 정렬을 수행합니다. 시간 복잡도는 항상 O(nlogn)입니다. 배열을 힙으로 구성하는 과정에서 O(n)의 시간이 소요되고, 힙을 정렬하는 과정에서 O(nlogn)의 시간이 소요됩니다.

동작 방식

1. 주어진 배열을 힙으로 구성합니다.

2. 최대 힙인 경우, 힙의 최대 원소를 배열의 가장 마지막 원소와 교환합니다.

3. 교환된 원소는 정렬된 부분으로 간주하고, 힙의 크기를 줄여 재구성합니다.

4. 위의 과정을 반복하여 전체 배열을 정렬합니다.

예시 코드

public class HeapSort {
    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--) {
            // 최대 원소(루트 노드)와 현재 노드 교환
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 힙 다시 구성
            heapify(arr, i, 0);
        }
    }

    public static 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 temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;

            // 교환된 자식 노드에 대해 재귀적으로 힙 구성
            heapify(arr, n, largest);
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 12, 1, 9};
        heapSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}