Sort Algorithms

게시 2024/03/11

By INUK

15 min read

정렬 알고리즘

programmers 에서 정렬이 사용된 문제를 풀어보던 중에 어떤 분의 ‘라이브러리에 너무 의존하는 것 같다’ 라는 댓글(제 풀이 달린건 아닙니다)을 봤을 때, ‘과연 나는 라이브러리 없이 정렬을 구현할 수 있나?’ 라는 의문이 들었습니다.
물론 단순 정렬은 쉽게 하겠지만 배웠던 정렬 방법들의 구현은 쉽게 생각이 나지 않았습니다.
그래서 더 늦기 전에 다시 한번 상기시키는 느낌으로 여러 가지 정렬 방법에 대해 정리해보려 합니다.

종류

Keywords

제자리 정렬 : 정렬을 수행할 때 추가적인 메모리를 거의 사용하지 않고, 입력 배열 내에서 데이터 요소들의 위치를 바꿈으로써 정렬을 수행하는 알고리즘
- 원래의 배열을 수정하여 정렬을 수행합니다.
- 메모리 사용이 효율적이고 구현이 간단합니다.
- 때론 속도나 다른 최적화 측면에서 제약이 있을 수 있습니다.
안정 정렬 : 동일한 키 값을 가진 요소들의 상대적인 순서가 정렬 후에도 유지되는 정렬 방법
- 두 요소의 키 값이 같을 때, 정렬 전의 순서가 정렬 후에도 그대로 유지되는 것을 의미합니다.
- 다중 조건으로 정렬할 때 유용합니다.
불안정 정렬 : 동일한 키 값을 가진 요소들의 상대적인 순서가 정렬 과정에서 변경될 수 있는 정렬 방법
- 동일한 값에 대해 특정한 순서를 유지해야 하는 경우에는 적합하지 않습니다.
- 보통 구현이 더 간단하거나, 정렬 속도가 빠른 경우가 많습니다.

Bubble Sort

출처 : Jinhyy’s 개발일기

인접한 두 개의 원소를 비교하여 자리를 교환하며 정렬

구현 방식

i 번째 값과 i+1 번째 값을 비교하여 비교 방법에 따라 위치 유지 또는 교환
전체 자료의 끝 부분까지 반복
n 번째 값 결정 (가장 큰 값)
n 번째 값을 제외하고 [1 ~ 3] 반복

  
public class BubbleSort {

    public void bubbleSort(int[] array) {
        
        for(int i = 0; i < array.length - 1; i++) {
            for(int j = 0; j < array.length -i -1; j++) {
                if(array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }
}

특징

한번 순회할 시 마지막 원소 하나가 정렬, 원소들이 거품 올라오는 것처럼 보여 Bubble Sort 라고 합니다.
구현이 매우 간단하며, 제자리 정렬 로 정렬 과정에서 추가 메모리가 필요하지 않습니다.
비효율적인 비교 방식으로 인해 시간 복잡도가 높습니다.
거의 모든 상황에서 최악의 성능을 보여줍니다.
거의 정렬된 배열에서도 많은 비교와 교환이 이루어집니다.
이미 정렬된 자료에서는 1번만 순회하기에 최선의 성능을 보여줍니다.

성능

시간 복잡도
- O($nlogn$) - 평균
- O($n^2$) - 최악의 경우
공간 복잡도
- O(1)

Selection Sort

출처 : Jinhyy’s 개발일기

정렬할 index에 적합한 자료를 찾아 교환

구현 방식

현재 위치 확인 - i, value[i]
해당 위치 다음 차례부터 끝 부분에서 Min 값 (가장 작은 값) 탐색
i 번째 값과 Min 값의 위치 교환
전체 자료의 끝 부분까지 반복

  
public class Selection Sort {

    public void selectionSort(int[] array) {
        
        for(int i = 0; i < array.length - 1; i++) {
            int min_index = i;

            for(int j = i + 1; j < array.length; j++) {
                if(array[j] < array[min_index]) {
                    min_index = j;
                }
            }

            int temp = array[i];
            array[i] = array[min_index];
            array[min_index] = temp;
        }
    }

}

특징

배열을 순회하면서 각 위치에 올바른 요소를 선택하여 배치하는 방식입니다.
제자리 정렬 로 추가적인 메모리 사용이 없습니다.
현재 자료가 정렬이 되어있던말던 무조건 전체 리스트를 순회하며 검사합니다.
비교 횟수는 많으나 교환 횟수는 적습니다.
불안정 정렬 입니다.
데이터 양이 많을수록 성능 저하가 큽니다.

성능

시간 복잡도
- O($n^2$) - 모든 경우
공간 복잡도
- O(1)
버블 정렬과 비슷한 성능이나 교환의 횟수가 더 적습니다.

Insertion Sort

출처 : Jinhyy’s 개발일기

이미 정렬된 배열 부분에서 자신의 위치를 찾아 삽입

구현 방식

i 번째 값을 정렬된 부분 (i의 왼쪽)과 i-1부터 비교하여 삽입될 위치를 탐색합니다.
위치를 찾으면 해당 부분까지 정렬된 값을 한칸씩 뒤로 물립니다.
해당 위치에 i 번째 값 삽입
전체 자료의 끝 부분까지 반복

  
public class Insertion Sort {

    public void insertionSort(int[] array) {
        
        for(int i = 1; i < array.length; i++) {
            int key = array[i];
            int j = i - 1;

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

            array[j + 1] = key;
        }
    }

}

특징

작은 데이터셋 또는 거의 정렬된 데이터에 효율적입니다.
구현이 간단하고, 제자리 정렬 이자 안정 정렬 입니다.
대부분 정렬된 배열에 대해서는 매우 빠릅니다.
성능 편차가 심하고 대규모 데이터셋에는 부적합합니다.

성능

시간 복잡도
- O($n^2$) - 평균 및 최악의 경우
- O($n$) - 이미 정렬된 배열인 경우
공간 복잡도
- O(1)

Quick Sort

출처 : Jinhyy’s 개발일기

Pivot 값을 기준으로 더 작은 요소와 큰 요소를 분리하여 재귀적으로 정렬

구현 방식

왼쪽에서부터 Pivot 값보다 큰 값 탐색
오른쪽애서부터 Pivot 값보다 작은 값 탐색
두 값 위치 교환
진행이 불가능 할 때까지 [1 ~ 3] 반복
왼쪽의 마지막 탐색값과 Pivot 값 교환
왼쪽 부분과 오른쪽 부분에 대해 Pivot 값을 선택하여 [1 ~ 5] 반복

  
public class QuickSort {

    public void quickSort(int[] array, int left, int right) {
        
        if(left < right) {
            int pivot = partition(array, left, right);

            quickSort(array, left, pivot - 1);
            quickSort(array, pivot + 1, right);
        }
    }

    public int partition(int[] array, int left, int right) {
        
        int pivot = array[right];
        int i = left - 1;

        for(int j = left; j < right; j++) {
            if(array[j] < pivot) {
                i++;

                int temp = arr[i];
                array[i] = arr[j];
                array[j] = temp;
            }
        }

        int temp = array[i + 1];
        array[i + 1] = array[right];
        array[right] = temp;

        return i + 1;
    }
}

특징

분할 정복 알고리즘 중 하나로 평균적으로 매우 빠른 성능을 보입니다.
분할 단계에서 중요한 작업들을 수행하고 병합 단계에서는 아무것도 하지 않습니다.
대규모 데이터셋에도 효율적입니다.
추가 메모리 사용이 적습니다.
불안정 정렬 로 Pivot 값 선택 방법에 따라 시간 복잡도가 달라집니다.
동일 시간 복잡도일 때는 먼 거리 교환 처리, 캐시 효율 (사용된 Pivot 값 제외한 탐색) 등으로 더 빠르게 동작합니다.

성능

시간 복잡도
- O($nlogn$) - 평균
- O($n^2$) - 최악의 경우
공간 복잡도
- O($nlogn$) - 재귀적 호출

Merge Sort

출처 : Jinhyy’s 개발일기

Divide and Conquer

구현 방식

배열을 더는 쪼갤 수 없을 때까지 반씩 나눔
두 배열을 합치면서 정렬
- 합치는 두 배열을 비교하면서 작은 값부터 배열에 삽입하는 방식으로 정렬

  
public class MergeSort {

    public void mergeSort(int[] array, int left, int right) {

        if(left < right) {
            int mid = (left + right) / 2;

            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);

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

    public void merge(int[] array, int left, int mid, int right) {

        int left_size = mid - left + 1;
        int right_size = right - mid;

        int[] left_array = new int[left_size];
        int[] right_array = new int[right_size];

        for(int i = 0; i < left_size; i++) {
            left_array[i] = array[left + 1];
        }
        for(int i = 0; i < right_size; i++) {
            right_array[i] = array[right + 1];
        }

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

        while(i < left_size && j < right_size) {
            if(left_array[i] <= right_array[j]) {
                array[k] = left_array[i];
                i++;
            } else {
                array[k] = right_array[j];
                j++;
            }

            k++;
        }

        while(i < left_size) {
            array[k] = left_array[i];
            i++;
            k++;
        }

        while(j < right_size) {
            array[k] = right_array[j];
            j++;
            k++;
        }
    }
}

특징

안정적인 분할 정복 알고리즘으로 대규모 데이터셋에도 효율적입니다.
분할 단계에서는 아무것도 하지 않고 병합 단계에서 정렬을 수행합니다.
정렬 과정에서 배열의 크기만큼의 추가 공간이 필요합니다.
1. 복사를 하기 위한 큰 배열 하나를 미리 할당해두고 계속 사용
2. Merge 가 담당하는 구간의 크기 (right - left + 1) 만큼만 할당
LinkedList 와 같은 자료구조의 정렬에 유용합니다.
- 삽입, 삭제 용이
- 순차 접근이 아닌 임의의 인덱스 탐색은 어려움

성능

시간 복잡도
- O($nlogn$) - 모든 경우
공간 복잡도
- O($n$)

Heap Sort

출처 : 지점1

완전 이진트리를 기반으로 정렬

구현 방식

완전 이진트리 생성
Route 값과 배열의 마지막 요소 교환
Heap Size 를 줄이고 새로운 Route 에 대해 다시 Heap 구성
Heap Size 가 1이 될 때까지 [1 ~ 3] 반복

  
public class HeapSort {

    public void heapSort(int[] array) {

        int n = array.length;

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

        for(int i = n - 1; i > 0; i--) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;

            heapify(array, i, 0);
        }
    }

    public void heapify(int[] array, int n, int i) {

        int max = i;
        int left = (2 * i) + 1;
        int right = (2 * i) + 2;

        if(left < n && array[left] > array[max]) {
            max = left;
        }

        if(right < n && array[right] > array[max]) {
            max = right;
        }

        if(max != i) {
            int temp = array[i];
            array[i] = array[max];
            array[max] = temp;

            heapify(array, n, max);
        }
    }
}

특징

제자리 정렬 이자 불안정 정렬 입니다.
최대 Heap 으로 내림차순 정렬, 최소 Heap 으로 오름차순 정렬 수행이 가능합니다.
배열을 미리 정렬할 필요가 없으므로, 입력 데이터가 무작위로 분포되어 있을 때 좋은 성능을 보입니다.

성능

시간 복잡도
- O($nlogn$) - 모든 경우
공간 복잡도
- O(1)

Reference

✔ Evans Library | Evan’s
✔ 지점1 | 지점1
✔ Jinhyy’s | Jinhyy’s

CS, Algorithm

cs algorithm sort

정렬 알고리즘

종류

Bubble Sort

구현 방식

특징

성능

Selection Sort

구현 방식

특징

성능

Insertion Sort

구현 방식

특징

성능

Quick Sort

구현 방식

특징

성능

Merge Sort

구현 방식

특징

성능

Heap Sort

구현 방식

특징

성능

Reference

인기 태그