정렬 알고리즘 정리

백준 사다리 문제에서 다뤘던 삽입정렬과 버블 정렬을 제외하고
나머지 정렬 알고리즘에 대해 정리하고 직접 구현해보려고 한다
2~3개씩 정렬 알고리즘을 정리할 계획이다.

힙 정렬

말 그대로 힙 자료구조를 활용하여 정렬하는 방법으로 힙 자료구조에 대한 이해가 필요하다
힙 자료구조에 대한 정리와 구현은 정렬 알고리즘 이후에 작성할 계획이다

힙 정렬 방법은 최소힙 또는 최대힙으로 주어진 배열을 정렬한 뒤, 추가적인 작업을 통해 정렬한다

힙의 형태

먼저 힙은 완전 이진 트리 형태로 구성되어 있다
부모와 자식간의 비교만 진행하며 형제간의 비교는 하지 않는다.

다음은 최소힙과 최대힙에 대한 설명이다.

최소힙

부모노드의 값 <= 자식 노드의 값인 경우이다.

최대힙

부모노드의 값 >= 자식 노드의 값인 경우이다

힙의 성질

• 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2
• 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2 + 1
• 부모 노드 인덱스 = 자식 노드 인덱스 / 2

위 3가지 성질은 완전 이진 트리의 핵심적인 성질이며, 변하지 않는 성질이니 미리 알아두고 가자

힙 정렬의 진행 순서

1 . 먼저 최대 힙 또는 최소힙으로 배열을 재정렬한다
2 . 이어서 오름차순 정렬 혹은 내림차순 정렬을 위해 최대힙과 최소힙의 root 노드를 하나씩 삭제해서 뒤에 배치하거나 앞에 배치하는 방법이다.

각 방법에 대해 직접 코드로 구현해보려고한다.
해당 구현에서는 최대힙과 오름차순 정렬을 선택하여 구현하였다.

public class HeapSort{

        private static int getParent(int child){
            return (child-1)/2;
        }

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

        private static void heapify(int[] arr, int parentIdx, int lastIdx){
            /**
             * 재귀 구현 방식
             */
//            int leftChild = 2 * parentIdx ;
//            int rightChild = 2 * parentIdx + 1;
//            int largestIdx = parentIdx;
//
//
//            if(leftChild <= lastIdx && arr[largestIdx] < arr[leftChild]){
//                largestIdx = leftChild;
//            }
//
//            if(rightChild <= lastIdx && arr[largestIdx] < arr[rightChild]){
//                largestIdx = rightChild;
//            }
//
//            if(parentIdx != largestIdx){
//                swap(arr, largestIdx, parentIdx);
//                heapify(arr, largestIdx, lastIdx);
//            }

            /**
             * 반복문 구현 방식 -> 정렬에서 일반적으로 재귀보다는 반복문으로 구현하는 것이 더 효율적이다!
             */
            while((parentIdx * 2) <= lastIdx){
                int leftChild = 2 * parentIdx;
                int rightChild = 2 * parentIdx + 1;
                int largestIdx = parentIdx;

                if(arr[leftChild]  > arr[largestIdx]){
                    largestIdx = leftChild;
                }

                if(rightChild <= lastIdx && arr[rightChild] > arr[largestIdx]){
                    largestIdx = rightChild;
                }

                if(largestIdx != parentIdx){
                    swap(arr, parentIdx, largestIdx);
                    parentIdx = largestIdx;
                }else{
                    return;
                }

            }


        }
        public static void heapSort(int[] arr, int size){
            if(size < 2){
                return;
            }

            int parentIdx = getParent(size-1);

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

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

        }

    }

코드 설명

메소드를 기준으로 각각에 대해 설명하겠다

int getParent(int child)

자식 인덱스 정보를 넘겨주면 부모 인덱스 정보를 반환하는 메소드다
이때 완전 이진 트리의 성질을 이용하여 child / 2에 해당하는 값을 부모 인덱스로 반환하였다

void swap(int[] arr, int i, int j)

두 수를 swap하는 메소드다.

void heapify(int[] arr, int parentIdx, int lastIdx)

최대힙으로 재정렬하는 메소드다.
처음에는 재귀로 구현하였는데, 재귀함수 호출이 많아질 경우 스택오버플로우가 발생할 수 있어서
반복문으로 최적화하였다

• 처음은 부모 인덱스인 parentIdx를 largestIdx로 초기화한다
• 이어서 공통적으로 왼쪽, 오른쪽 자식 인덱스가 lastIdx의 범위를 벗어나지 않으면서,
  largestIdx값보다 큰 경우에는 largestIdx를 해당 자식 인덱스로 변경해준다
• 마지막에 자식 인덱스로 변경되었는지 확인을 해준다.
  largestIdx랑 parentIdx가 같지 않으면 바뀐 것이므로
  parentIdx랑 largestIdx를 swap해서 배열의 값을 바꿔주고
  parentIdx 변수에는 largestIdex로 변경해준다

void heapSort(int[] arr, int size)

힙정렬의 모든 과정이 들어있는 메소드이다

• size가 2보다 작으면 원소가 한개나 0개 있다는 것인데 그런 경우 정렬이 필요없으므로 종료한다
• 위 조건을 넘어서면 먼저 부모 인덱스를 가져온 뒤, 최대힙 정렬을 진행한다
• 이어서 size-1부터 차례대로 보면서 swap을 하고 heapfify로 재졍렬한다.

시간복잡도

힙정렬의 시간복잡도는 최선, 평균, 최악 모두 O(nlogn)이다

• 일단 이진 트리에서 트리의 높이를 모두 탐색하는데는 O(logn)의 시간복잡도가 발생한다
• 이어서 뒤에서부터 재정렬하는 과정을 진행한다고 했는데,
  이 과정에서 logn의 과정을 n번 반복하므로 시간복잡도는 O(nlogn)이 발생한다

병합정렬

분할정복과 비슷하게 배열을 여러 부분으로 나눠서 정렬하고 합치는 방식이다
부분 배열의 길이가 1이 될때까지 절반으로 계속 나누고, 인접한 배열과 정렬한 뒤 합친다

    public class MergeSort{

        private static int[] sorted = new int[10];


        private static void mergeSort(int[] arr, int left, int right){
            for(int size = 1; size <= right; size += size) {
                for (int l = 0; l <= right - size; l += (2 * size)) {
                    int low = l;
                    int mid = l + size - 1;
                    int high = Math.min(l + (2*size) - 1, right);
                    merge(arr, low, mid, high);
                }
            }

        }


        private static void merge(int[] arr, int left, int mid, int right){
            int l = left;
            int r = mid + 1;
            int idx = left;

            while(l <= mid && r <= right){
                if(arr[l] <= arr[r]){
                    sorted[idx++] = arr[l++];
                }else{
                    sorted[idx++] = arr[r++];
                }
            }

            if(l > mid){
                while(r <= right){
                    sorted[idx++] = arr[r++];
                }
            }else{
                while(l <= mid){
                    sorted[idx++] = arr[l++];
                }
            }

            for (int i = left; i <= right; i++) {
                arr[i] = sorted[i];
            }
        }

    }

코드 설명

void merge(arr[], int left, int mid, int right)

왼쪽 오른쪽 배열의 시작점을 각각 left, mid+1로 한다
그리고 두 지점의 값을 비교해서 더 큰 값을 sorted 임시 배열에 넣어준다
한쪽이 범위를 벗어나서 종료되면 남은 배열의 값을 모두 넣어준다

void mergeSort(int[] arr, int left, int right)

사이즈 크기만큼 두 배열을 비교하여 합치고 정렬하는 메소드다
사이즈의 크기는 right보다 작거나 같으며, 각각 right-size만큼 순회를 돌아서 merge해준다

이때 첫번째 포문에서는 크기만큼 잘라서 순회하는 것이고,
두번째 포문에서는 그 잘린 배열들끼리 비교하는 과정이다'

low는 left 역할, high는 l + (2*size) - 1로 left위치에서 두배 크기 - 1만큼인 right이다
이때 high에는 배열의 크기를 넘어설 수 있으므로,
전체 배열의 끝 위치인 파라미터 right와 비교하여 더 작은 값을 넣어준다

시간복잡도

최선 최악 평균 모두 O(nlogn)이라는 시간복잡도가 발생한다

분할하는 과정은 총 n개의 노드를 이진 트리로 분할하는 과정이며,
이것을 봤을 때트리의 높이인 logn만큼의 복잡도가 발생하는 것을 알 수 있다.

따라서 O(nlogn)이라는 시간 복잡도가 발생한다.

참고

힙 정렬 참고
병합 정렬 참고