자바 정렬 알고리즘 기본 형태 | 버블, 선택, 삽입, 합병, 퀵

# 버블정렬 | O(N^2)

    public static void bubbleSort(int[] arr) { // O(n^2)
        for(int i = 0; i < arr.length; i++) {
            for(int j = 0; j < arr.length - 1 - i; j++) {
                if(arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }

 

# 선택정렬 | O(N^2)

    public static void selectedSort(int[] arr) { // O(n^2)
        for(int i = 0; i < arr.length - 1; i++) {
            int minidx = i;
            for(int j = i + 1; j < arr.length; j++) {
                if(arr[j] < arr[minidx]) {
                    minidx = j;
                }
            }
            swap(arr, i, minidx);
        }
    }

 

# 삽입정렬 | O(N^2)

    public static void insertionSort(int[] arr) { // O(n^2)
        for(int i = 1; i < arr.length; 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;
        }
    }

 

# 합병정렬 / 병합정렬 | O(NlogN)

   static int[] tmp; // 추가적인 배열 공간이 필요함

    public static void merge_sort(int[] arr) {
        tmp = new int[arr.length];
        merge_sort(arr, 0, arr.length - 1);
        tmp = null;
    }

    public static void merge_sort(int[] arr, int left, int right) {
        if(left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int p1 = left;
        int p2 = mid + 1;
        int idx = left;
        while(p1 <= mid && p2 <= right) {
            // stable sort를 구현하기 위해서는 우선순위가 같은경우 앞의 배열값이 들어가야함
            if(arr[p1] <= arr[p2]) { // 그러므로 "arr[p1] < arr[p2]"로 하면 안됨
                tmp[idx++] = arr[p1++];
            } else {
                tmp[idx++] = arr[p2++];
            }
        }
        while(p1 <= mid) {
            tmp[idx++] = arr[p1++];
        }
        while(p2 <= right) {
            tmp[idx++] = arr[p2++];
        }
        for(int i = left; i <= right; i++) {
            arr[i] = tmp[i];
        }
    }

* merge sort는 "Stable sort(안정 정렬)"이다

 

---

★★ Stable Sort란? ★★

Stable Sort란 동일한 정렬기준을 가진(중복된) 키들은 순서가 바뀌지 않은채로 정렬되는 정렬을 의미한다.

(정렬 전과 정렬 후의 순서가 같다)

 

[1, 3, 2, 5, 1', 6]  --> [1, 1', 2, 3, 5, 6] 

(1과 1'의 순서는 정렬 전과 정렬 후가 동일하다. 이런 방식의 정렬을 stable sort, 아닌것을 unstable sort라고 함)

 

- 장점 : 정렬의 결과가 항상 동일하다 (문자열을 사전순 정렬할 때 특히 중요하게 작용)

https://stackoverflow.com/questions/1517793/what-is-stability-in-sorting-algorithms-and-why-is-it-important

What is stability in sorting algorithms and why is it important?

[peach, straw, apple, spork]를 맨 앞글자 하나를 기준으로 사전순 정렬한다고 했을 때,

 

Stable Sort -> [apple, peach, straw, spork] 단 한가지 경우만 생긴다

Unstable Sort -> [apple, peach, straw, spork] or [apple, peach, spork, straw] 두가지 경우가 생길 수 있다

 

정렬 기준이 두가지 존재하는 경우(ex, Last name을 기준으로 정렬하고, 같은경우 First name을 기준으로 정렬)

First name을 기준으로 [Stable/Unstable] 정렬을 먼저 한 이후 Last name을 기준으로 Stable sort 정렬할 수 있는데,

(Stable 정렬의 경우는 우선순위가 같은 키의 경우 순서가 바뀌지 않으므로 last name 기준 정렬을 나중에 해도 last name이 같은 경우는 미리 정렬된 first name 순으로 고정됨.)

last name를 기준으로 Unstable sort를 할 경우는 미리 정렬해둔 순서가 다시 뒤바뀌어 버릴 수 있으므로 사용할 수가 없다.

 

생각보다 차이가 꽤 큰 방식이다..!!

 

<Stable Sort> : 버블정렬 / 삽입정렬 / 합병정렬

<Unstable Sort> : 선택정렬 / 퀵정렬 / 힙정렬

---

# 퀵정렬 | O(NlogN)

    public static int partition(int[] arr, int left, int right) {
        int lo = left;
        int hi = right;
        int pivot = arr[left]; // 제일 왼쪽 원소를 pivot으로 잡는 방법(제일 간단)

        while(lo < hi) {
            while(arr[hi] > pivot && lo < hi) {
                hi--;
            }
            while(arr[lo] <= pivot && lo < hi) {
                lo++;
            }
            swap(arr, lo, hi);
        }
        swap(arr, left, lo);
        return lo;
    }

    public static void quickSort(int[] arr, int left, int right) {
        if(left >= right) {
            return;
        }
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }

    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

* hi, lo 부등호에 유의!  (pivot < hi / pivot >= low)

* 퀵정렬은 pivot을 어떻게 잡느냐에 따라 성능 차이가 클 수 있다. 

* 이미 정렬된 상태의 배열을 퀵정렬을 이용해 정렬하려고 하면 최악의 경우 O(N^2)의 시간복잡도가 생긴다.

- 최악의 경우를 피하기 위해 좌/우 고정방식이 아닌 랜덤위치 피봇 or 듀얼 피봇을 사용하는 경우가 많음.

* O(N)의 비교작업 * O(logN)의 분할 = O(NlogN)의 시간복잡도

* Arrays.sort() 메소드를 보면 퀵정렬을 기반으로 짜여져있다