정렬 정리(선택 정렬, 버블 정렬, 삽입 정렬, 합병 정렬, 퀵 정렬, 힙 정렬)

• 비효율 : 선택 정렬, 버블 정렬, 삽입 정렬
• 효율 : 합병 정렬, 퀵 정렬, 힙 정렬

---

 

선택 정렬

넣을 위치는 정해져있고 어떤 원소를 넣은지 선택하는 알고리즘

• 시간 복잡도: O(N^2)

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

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

---

버블 정렬

인접한 두 원소를 검사하여 정렬하는 알고리즘, 마지막 인덱스부터 큰 수들을 나열합니다.

• 시간 복잡도: O(N^2)

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

---

삽입 정렬

2번째 원소부터 시작하여 앞 원소들과 비교하여 삽입하는 정렬 알고리즘

• 시간 복잡도
  • 최선: O(N)
  • 평균,최악: O(N^2)

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

            //앞에 원소들 보다 삽입하려는 원소가 작으면 해당 원소들을 뒤로 미룬다.
            while (0 <= j && tmp < arr[j]) {
                arr[j + 1] = arr[j];
                j--;
            }

            /**
             * 반복문을 빠져나왔다는 것은 삽입하려는 원소가 앞에 원소들보다 크다는 것
             */
            arr[j + 1] = tmp;
        }
    }

---

합병 정렬

요소를 이분 분할하고, 다시 합병시키는 정렬 알고리즘

• 시간 복잡도: O(NlogN)
• 안정 정렬 (중복된 원소의 순서가 정렬 후에도 동일한 정렬)

    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 leftIndex = left;
        int rightIndex = (mid + 1);
        int index = left;

        /* *
         * 분할한 배열들을 비교하며 더 작은 수를 sorted 배열에 채워넣는다.
         * 한쪽 배열이 빌 때까지 반복
         */
        while (leftIndex <= mid && rightIndex <= right) {
            if (arr[leftIndex] < arr[rightIndex]) {
                sorted[index++] = arr[leftIndex++];
            }
            else{
                sorted[index++] = arr[rightIndex++];
            }
        }

        /* *
         * 왼쪽 부분 배열이 전부 비었으면
         * 오른쪽 부분 배열의 나머지 원소들을 새 배열에 채워준다.
         * 오른쪽 부분 배열이 전부 비었으면
         * 왼쪽 부분 배열의 나머지 원소들을 새 배열에 채워준다.
         */
        if (mid < leftIndex) {
            while(rightIndex <= right) {
                sorted[index++] = arr[rightIndex++];
            }
        } else {
            while(leftIndex <= mid) {
                sorted[index++] = arr[leftIndex++];
            }
        }

        //분할된 배열을 담기 위한 임시 배열인 sorted를 원본 배열인 arr에 옮겨줍니다.
        //이 부분은 merge안에 선언할 필요없이 마지막에 해주셔도 됩니다.
        for (int i = left; i <= right; i++) arr[i] = sorted[i];
    }

---

퀵 정렬

분할 정복 방법을 통해 주어진 배열을 정렬하는 알고리즘

좀 더 자세하게 설명하자면 배열에서 하나의 원소(피벗이라 칭함)를 기준으로 배열의 길이가 1이 될때 까지 두 개의 부분 배열로 계속 나눈 후에 인접 부분 배열끼리 합치는 방식입니다.

이때 피벗을 무엇으로 선택하냐에 따라 구현 방법이 약간 달라집니다.(원리는 같아서 차이는 거의 없음)

피벗을 선택하는 경우의 수는 총 3가지로 가장 왼쪽 혹은 가장 오른쪽 원소를 피벗으로 선택하는 경우, 중간에 있는 원소를 피벗으로 선택하는 경우가 있습니다. 만약 퀵 정렬을 적용할 배열이 이미 오름차순 혹은 내림차순 정렬되어 있다면 가장 왼쪽 혹은 가장 오른쪽 원소를 피벗으로 선택한 경우 O(N^2) 시간복잡도를 갖게 될 것입니다. 때문에 중가 피벗을 선호합니다. 여기도 중간 피벗을 선택한 경우로 예제 코드를 작성하겠습니다.

• 시간 복잡도
  • 평균, 최선: O(NlogN)
  • 최악: O(N^2)
• 불안정 정렬, 단순 비교 정렬
• 합병 정렬과 달리 배열을 비균등하게 분할합니다.
• 특정 조건이 아닌 경우 같은 시간 복잡도(O(NlogN))을 갖는 정렬 알고리즘에 비해 빠릅니다. (ex. 합병 정렬)

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

    private static void sort(int[] arr, int low, int high) {
        if (low >= high) return;

        int mid = partition(arr, low, high);
        sort(arr, low, mid - 1);
        sort(arr, mid, high);
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[(low + high) / 2];
        while (low <= high) {
            //pivot 왼쪽 원소들 중 pivot 보다 큰 요소
            while (arr[low] < pivot) low++;

            //pivot 오른쪽 원소들 중 pivot 보다 작은 요소
            while (arr[high] > pivot) high--;

            //low와 high이 교차하거나 넘지 않았다면 둘의 위치를 바꿔줍니다.
            if (low <= high) {
                if (low != high) {
                    swap(arr, low, high);
                }
                low++;
                high--;
            }
        }
        //분할 기준점 index 반환
        return low;
    }

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

---

힙 정렬

완전 이진 트리 형태인 힙 자료구조를 기반으로 한 정렬 알고리즘

힙 정렬로  만든 다음에 최대값을 순서대로 정렬하는 것이다. 기존에 있는 힙 자료구조를 통해 저장한 뒤 반환하면 될텐데 왜 따로 구현할까? 바로 추가적인 메모리를 생성하지 않고 바로 배열 안에서 정렬하기 위함입니다. 때문에 힙 정렬은, 최대 힙을 구현한 다음에 최대값(루트 노드)을 배열에 채워넣고 삭제하며 정렬하는 방법입니다.

• 시간 복잡도: O(NlogN)

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

    public static void heapify(int[] arr, int n, int i) {
        int curNode = i; // 현재 노드
        int leftNode = i * 2 + 1; // 왼쪽 자식 노드.
        int rightNode = i * 2 + 2; // 오른쪽 자식 노드.

        // 왼쪽 자식 -> 오른쪽 자식 순으로 현재 노드를 비교하여 현재 노드보다 크면 swap
        if (leftNode < n && arr[curNode] < arr[leftNode]) curNode = leftNode;
        if (rightNode < n && arr[curNode] < arr[rightNode]) curNode = rightNode;
        if (i != curNode) {
            swap(arr, curNode, i);

            // 현재 노드가 자식 노드보다 클때까지 반복
            heapify(arr, n, curNode);
        }
    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }