정렬 알고리즘

이담호·2024년 4월 10일
sorting algorithm
post-thumbnail

목차

  1. Selection Sort 선택 정렬
  2. Insertion Sort 삽입 정렬
  3. Bubble Sort 버블 정렬
  4. Merge Sort 병합 정렬
  5. Quick Sort 퀵 정렬
  6. Heap Sort 힙 정렬
  7. Shell Sort 쉘 정렬

1. Selection Sort 선택 정렬

선택 정렬은 목록의 정렬되지 않은 부분에서 가장 작은(또는 가장 큰) 요소를 반복적으로 선택하고 목록의 정렬된 부분으로 이동하여 작동하는 간단하고 효율적인 정렬 알고리즘이다.
목록의 정렬되지 않은 부분에서 가장 작은(또는 가장 큰) 요소를 반복적으로 선택하고 정렬되지 않은 부분의 첫 번째 요소와 스왑한다. 이 과정은 전체 목록이 정렬될 때까지 정렬되지 않은 나머지 부분에 대해 반복한다.




Java Code

package selectionsort;

import arrayprinter.ArrayPrinter;

public class SelectionSort {
    public static void sort(int array[]) {
        int n = array.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }

            int tmp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 7, 4, 10, 2, 3, 9, 8, 6, 1};
        sort(arr);
        ArrayPrinter.print(arr);
    }
}

결과

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

복잡도 분석

  • Time Complexity
    • 배열의 요소를 하나씩 선택하는 한 루프 O(N)
    • 다른 모든 요소들과 비교하는 또 다른 루프 O(N)
    • 따라서 전체적인 시간 복잡도 = O(N) * O(N) = O(N2N^2)
  • Auxiliary Space
    • O(1)은 배열에서 두 값을 교환하는 동안 임시 변수에 사용되는 유일한 추가 메모리다. 선택 정렬은 O(N)개 이상의 스왑을 수행하지 않으며 메모리 쓰기 비용이 많이 드는 경우 유용할 수 있다.

장점

  • 간단하고 이해하기 쉽다.
  • 작은 데이터 셋에서 잘 작동한다.
  • 거의 정렬된 데이터 셋에서 선형 시간 복잡도로 동작한다.

단점

  • 최악의 경우와 평균적인 경우 O(N2N^2)의 시간복잡도를 가진다.
  • 대규모 데이터 셋에 적합하지 않다.

특징

  • in-place
  • not stable

2. Insertion Sort 삽입 정렬

삽입 정렬은 정렬되지 않은 목록의 각 요소를 목록의 정렬된 부분에 있는 올바른 위치에 반복적으로 삽입하여 작동하는 간단한 정렬 알고리즘이다.
손에 있는 카드패를 정리하는 것처럼 정렬되어 있지 않은 부분의 요소를 정렬되어 있는 목록의 올바른 위치에 삽입하여 정렬한다.

Java Code

package insertionsort;

import arrayprinter.ArrayPrinter;

public class InsertionSort {
    public static void sort(int[] array) {
        int n = array.length;
        for (int i = 1; i < n; i++) {
            int target = array[i];
            int j = i - 1;

            while(j >= 0 && array[j] > target) {
                array[j + 1] = array[j];
                j--;
            }

            array[j + 1] = target;
        }
    }

    public static void main(String args[]) {
        int[] arr = {5, 7, 4, 10, 2, 3, 9, 8, 6, 1};
        sort(arr);
        ArrayPrinter.print(arr);
    }
}

결과

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

복잡도 분석

  • Time Complexity
    • Best case: O(n2n^2), 리스트가 거의 정렬되어 있는 경우
    • Average case: O(n2n^2), 리스트가 랜덤 순서로 되어있는 경우
    • Worst case: O(n2n^2), 리스트가 역순으로 정렬되어 있는 경우
  • Auxiliary Space
    • O(1), 삽입 정렬에는 O(1) 공간이 추가로 필요하므로 공간 효율적인 정렬 알고리즘이다.

장점

  • 간단하고 구현이 쉽다.
  • 작은 데이터 셋과 거의 정렬된 데이터 셋에 효율적이다.
  • 공간 효율적이다.

단점

  • 대규모 데이터 셋에 적합하지 않다.

특징

  • in-place
  • stable

3. Bubble Sort 버블 정렬

버블 정렬은 인접한 원소들이 순서가 틀릴 경우 반복적으로 스왑하는 방식으로 작동하는 가장 간단한 정렬 알고리즘이다.

  • 왼쪽에서부터 시작하여 인접 요소를 비교하고 높은 요소를 오른쪽에 배치한다.
  • 이런 식으로 가장 큰 요소는 처음에 가장 오른쪽 끝으로 이동한다.
  • 그런 다음 데이터가 정렬될 때까지 두 번째로 큰 것을 찾아서 배치하는 등의 과정을 계속한다.


Java Code

package bubblesort;

import arrayprinter.ArrayPrinter;

public class BubbleSort {
    public static void sort(int[] array) {
        int n = array.length;
        int tmp;

        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 7, 4, 10, 2, 3, 9, 8, 6, 1};
        sort(arr);
        ArrayPrinter.print(arr);
    }
}

최적화

package bubblesort;

import arrayprinter.ArrayPrinter;

public class BubbleSort {
    public static void sort(int[] array) {
        int n = array.length;
        int tmp;
        boolean swapped;

        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    swapped = true;
                }
            }

            if (!swapped) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 7, 4, 10, 2, 3, 9, 8, 6, 1};
        sort(arr);
        ArrayPrinter.print(arr);
    }
}

복잡도 분석

  • Time Complexity
    • O(n2n^2)
  • Auxiliary Space
    • O(1)

장점

  • 간단하고 구현이 쉽다.
  • 추가적인 메모리 공간이 필요하지 않다.

단점

  • 대규모 데이터 셋에 적합하지 않다.
  • 비교 기반 정렬 알고리즘으로, 비교 연산자가 입력 데이터 세트의 요소들의 상대적인 순서를 결정해야 한다. 특정한 경우에는 알고리즘의 효율성을 제한할 수 있다.

4. Merge Sort 병합 정렬

병합 정렬은 분할정복 접근법을 따르는 정렬 알고리즘이다. 입력 배열을 재귀적으로 더 작은 하위 배열로 나누고 그 하위 배열을 정렬한 다음 다시 병합하여 정렬된 배열을 얻는 방식으로 작동한다.
1. Divide
2. Conquer
3. Merge

Java Code

package mergesort;

import arrayprinter.ArrayPrinter;

public class MergeSort {
    public static void sort(int array[], int left, int right) {
        if (left == right) {
            return;
        }

        int mid = (left + right) / 2;
        sort(array, left, mid);
        sort(array, mid + 1, right);

        merge(array, left, mid, right);
    }

    public static void merge(int array[], int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        for (int i = 0; i < n1; i++) {
            leftArray[i] = array[left + i];
        }
        for (int i = 0; i < n2; i++) {
            rightArray[i] = array[mid + 1 + i];
        }

        int leftIndex = 0;
        int rightIndex = 0;
        int targetIndex = left;

        while (leftIndex < n1 && rightIndex < n2) {
            if (leftArray[leftIndex] <= rightArray[rightIndex]) {
                array[targetIndex] = leftArray[leftIndex];
                leftIndex++;
            } else {
                array[targetIndex] = rightArray[rightIndex];
                rightIndex++;
            }
            targetIndex++;
        }

        while (leftIndex < n1) {
            array[targetIndex] = leftArray[leftIndex];
            leftIndex++;
            targetIndex++;
        }

        while (rightIndex < n2) {
            array[targetIndex] = rightArray[rightIndex];
            rightIndex++;
            targetIndex++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 7, 4, 10, 2, 3, 9, 8, 6, 1};
        sort(arr, 0, arr.length - 1);
        ArrayPrinter.print(arr);
    }
}

복잡도 분석

  • Time Complexity
    • Best Case: O(n log n), 배열이 이미 정렬되었거나 거의 정렬된 경우.
    • Average Case: O(n log n), 배열이 무작위로 순서가 정해질 때.
    • Worst Case: O(n log n), 배열이 역순으로 정렬된 경우.
  • Space Complexity
    • O(n), 병합 중에 사용되는 임시 배열에 추가 공간이 필요합니다.

장점

  • 최악의 경우 성능 보장: 최악의 경우 시간 복잡도가 O(N logN)이며, 이는 대규모 데이터 세트에서도 우수한 성능을 발휘한다는 것을 의미한다.

단점

  • Space complexity: 정렬 과정에서 병합된 하위 배열을 저장하기 위해 추가 메모리가 필요하다.
  • Not in-place: Not in-place 정렬 알고리즘이기 때문에 정렬된 데이터를 저장하기 위해 추가 메모리가 필요하다. 이는 메모리 사용이 우려되는 응용 프로그램에서 단점이 될 수 있다.

특징

  • stable
  • not in-place(out-place)

5. Quick Sort 퀵 정렬

하나의 리스트를 피벗을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
1. Divide: 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽 = 피벗보다 작은 요소들, 오른쪽 = 피벗보다 큰 요소들)로 분할한다.
2. Conquer: 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
3. Combine: 정렬된 부분 배열들을 하나의 배열에 합병한다.

  • 순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

Java Code

package quicksort;

import arrayprinter.ArrayPrinter;

public class QuickSort {
    public static void sort(int[] array) {
        sort(array, 0, array.length - 1);
    }

    private static void sort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }

        int pivot = start;
        int low = start + 1;
        int high = end;

        while (low <= high) {
            while (low <= end && array[low] < array[pivot]) {
                low++;
            }

            while (high > start && array[high] > array[pivot]) {
                high--;
            }

            if (low < high) {
                swap(array, low, high);
            } else {
                swap(array, high, pivot);
            }
        }

        sort(array, start, high - 1);
        sort(array, high + 1, end);
    }

    private static void swap(int[] array, int x, int y) {
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }

    public static void main(String args[]) {
        int[] arr = {5, 7, 4, 10, 2, 3, 9, 8, 6, 1};
        sort(arr);
        ArrayPrinter.print(arr);
    }
}

복잡도 분석

  • Time Complexity
    • Best Case: O(n log n), 각 단계에서 선택한 피벗이 어레이를 거의 동일한 반으로 분할할 때 빠른 정렬에 대한 최상의 시나리오가 발생한다. 이 경우 알고리즘이 균형 잡힌 파티션을 만들어 효율적인 정렬을 유도한다.
    • Average Case: O(n log n), QuickSort의 평균 사례 성능은 일반적으로 실제로 매우 우수하여 가장 빠른 정렬 알고리즘 중 하나다.
    • Worst Case: O(n2n^2), 퀵 정렬의 최악의 시나리오는 각 단계에서 피벗이 일관되게 매우 불균형한 파티션을 만들 때 발생한다. 배열이 이미 정렬되어 있다면 피벗이 항상 가장 작거나 큰 요소로 선택된다. 최악의 시나리오를 완화하기 위해 적절한 피벗(예: 중앙값 3)을 선택하고 정렬하기 전에 요소를 섞기 위해 무작위 알고리즘(랜덤화 퀵 정렬)을 사용하는 등 다양한 기술이 사용된다.
  • Auxiliary Space: 재귀적 스택 공간을 고려하지 않는다면 O(1). 재귀적 스택 공간을 고려한다면 최악의 경우 O(n) 을 만들 수 있다.

장점

  • 더 쉽게 문제를 해결할 수 있는 분할 정복 알고리즘이다.
  • 대용량 데이터 셋에서 효율적이다.
  • 기능을 수행하기 위해 소량의 메모리만 필요하기 때문에 오버헤드가 낮다.
  • locality of reference 때문에 다른 알고리즘들 보다 빠르다.

단점

  • 최악의 경우 시간 복잡도는 O(n2n^2)이며, 이는 피벗을 잘못 선택했을 때 발생한다(정렬되어 있고 처음 값, 끝 값을 피벗으로 설정하는 경우).
  • 소규모 데이터 세트에는 적합하지 않다.

특징

  • in-place
  • not stable

6. Heap Sort 힙 정렬

힙 정렬은 이진 힙 데이터 구조를 기반으로 한 비교 기반 정렬 방법이다.

주어진 입력 배열로 힙을 만든다.
힙에 요소가 하나만 포함될 때까지 다음 단계를 반복한다:
힙의 루트 요소(가장 큰 요소)를 힙의 마지막 요소와 스왑한다.
힙의 마지막 요소를 제거한다(지금 올바른 위치에 있음. last index 의 크기를 1 줄인다).
힙의 나머지 요소를 힙화한다.

Max Heap 을 구성하는 경우 오름차순으로 정렬.
Min Heap 을 구성하는 경우 내림차순으로 정렬.

Java Code

package heapsort;

import arrayprinter.ArrayPrinter;

public class HeapSort {
    public static void sort(int[] array) {
        int size = array.length;

        for (int i = size / 2 - 1; i >= 0; i--) {
            heapify(array, size, i);
        }

        for (int i = size - 1; i > 0; i--) {
            swap(array, 0, i);
            heapify(array, i, 0);
        }
    }

    private static void heapify(int[] array, int size, int i) {
        int largest = i;
        int left = i * 2 + 1;
        int right = i * 2 + 2;

        if (left < size && array[left] > array[largest]) {
            largest = left;
        }

        if (right < size && array[right] > array[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(array, largest, i);
            heapify(array, size, largest);
        }
    }

    private static void swap(int[] array, int x, int y) {
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }

    public static void main(String args[]) {
        int[] arr = {5, 7, 4, 10, 2, 3, 9, 8, 6, 1};
        sort(arr);
        ArrayPrinter.print(arr);
    }
}

복잡도 분석

  • Time Complexity:
    • Best Case: O(n log n)
    • Average Case: O(n log n)
    • Worst Case: O(n log n)
  • Auxiliary Space: recursive call stack 때문에 O(log n). 그러나 반복으로 구현하면 O(1)이 될 수 있다.

장점

  • 효율적인 시간 복잡도: 힙 정렬은 모든 경우에 O(n log n)의 시간 복잡도를 갖습니다. 따라서 큰 데이터 세트를 정렬하는 데 효율적이다. 로그 n 인자는 이진 힙의 높이에서 나오며, 알고리즘이 많은 수의 요소를 사용하더라도 우수한 성능을 유지하도록 해준다.
  • 메모리 사용량 – 메모리 사용량은 (재귀 대신 반복적인 heapify()를 작성함으로써) 최소화할 수 있다. 따라서 정렬할 항목의 초기 목록을 유지하는 데 필요한 것 외에는 추가적인 메모리 공간이 필요하지 않다.
  • 가장 큰 혹은 가장 작은 데이터 몇 개만 추출할 때 유용하다.

단점

  • 데이터들의 상태에 따라 다른 정렬법들에 비해서 조금 느린편이다.
  • locality of reference가 부족해 일반적으로 잘 구현된 QuickSort보다 2-3배 느리다.

특징

  • in-place
  • not stable

7. Shell Sort 쉘 정렬

‘Donald L. Shell’이라는 사람이 제안한 방법으로, 삽입정렬을 보완한 알고리즘이다.
삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안

  • 삽입 정렬의 최대 문제점: 요소들이 삽입될 때, 이웃한 위치로만 이동
  • 즉, 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있다.
  • 삽입 정렬과 다르게 셸 정렬은 전체의 리스트를 한 번에 정렬하지 않는다.

정렬해야 할 리스트의 각 k번째 요소를 추출해서 부분 리스트를 만든다. 이때, k를 ‘간격(gap)’ 이라고 한다.
보통 간격을 n/2 로 줄이는데 n/3+1로 줄이는 것이 더 빠르다고 알려져있다.

과정

  1. 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류
  2. 연속적이지 않은 여러 개의 부분 리스트를 생성
  3. 각 부분 리스트를 삽입 정렬을 이용하여 정렬
  4. 모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 반복
  5. 위의 과정을 부분 리스트의 개수가 1이 될 때까지 반복

Java Code

package shellsort;

import arrayprinter.ArrayPrinter;

public class ShellSort {
    public static void sort(int[] array) {
        int size = array.length;
        for (int gap = size / 2; gap > 0; gap = gap / 2) {

            for (int i = gap; i < size; i++) {
                int tmp = array[i];
                int j;

                for (j = i; j >= gap && array[j - gap] > tmp; j = j - gap) {
                    array[j] = array[j - gap];
                }

                array[j] = tmp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 7, 4, 10, 2, 3, 9, 8, 6, 1};
        sort(arr);
        ArrayPrinter.print(arr);
    }
}

복잡도 분석

  • Time complexity
    • Best Case: O(n log n), 거의 정렬되어 있는 경우
    • Average Case: O(n1.25n^{1.25}) ~ O(n1.5n^{1.5})
    • Worst Case: O(n2n^2), 역순으로 정렬되어 있는 경우

특징

  • in-place
  • not stable
profile
이담호
이전 포스트

DBCP

다음 포스트

equals(), hashCode()

0개의 댓글