[JAVA] 정렬을 코드로 구현하기. (삽입, 선택, 버블, 셸, 퀵, 합병, 힙, 기수)

시작하기에 앞서,

이 글은 발표자료용으로써,

실제로는 말로써 설명을 덧붙이기 때문에,

글만 보고는 이해가 어려울 수 있습니다만,

자료 자체는 검증을 했기 때문에,

이상은 없습니다. 그러나 더 좋은 방향으로

수정할 부분이 있다면

알려주시면 감사하겠습니다.

 

삽입정렬 (Insertion Sort)

삽입 정렬은 다 그런지는 모르겠지만,

제가 처음 배운 정처기 책에선

현재 인덱스와 앞선 인덱스를 순서대로 비교할 때,

맨 앞의 인덱스부터 순서대로 비교한다고 나와있습니다.

헌데 코드를 짜다보니,

현재 인덱스의 바로 앞 인덱스부터 비교를 해야했습니다.

이 점에 유의하여 코드를 확실히 작성해보고

그에 맞게 개념을 정리하는 것도 좋을것 같습니다.

import java.util.Arrays;

public class InsertionSort {
    public static void main(String[] args) {
        //삽입 정렬을 구현한 코드입니다.
        int[] arr = new int[10];
        for (int n = 0; n < arr.length; n++) {
            arr[n] = (int) (Math.random() * 10);
        }
        // 임의의 순서로 나열된 배열 할당.
        int key; // 조건이 맞으면 삽입할 변수 생성
        // 변수명이 key 인 이유는,
        // 삽입정렬에서 key 값은 고정된 채로,
        // 자신보다 앞선 인덱스들과 차례대로 비교를 하기 때문입니다.
        for (int i = 1; i < arr.length; i++) {
            key = arr[i]; // 현재 인덱스의 값을 key 로 할당.
            int j = i - 1; // 맨 처음 비교를 시작할 key 값의 바로 앞 인덱스.
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
                // key 값의 바로 앞 인덱스부터 비교해서,
                // 비교를 통해 삽입될 위치를 찾아갑니다.
            }
            arr[j + 1] = key;
            // while 문이 종료되면 위치를 찾은 것이기 때문에,
            // 맞는 위치에 key 값을 삽입합니다.
        }
        System.out.println(Arrays.toString(arr));
    }
}

이중 for 문을 쓰기 때문에 시간복잡도가 O(n²) 입니다.

 

 

선택정렬 (Selection Sort)

선택 정렬은,

아무런 알고리즘을 학습하지 않았을 때

가장 먼저 떠올릴 수 있는 정렬법입니다.

따라서 구현하기가 굉장히 쉽습니다.

import java.util.Arrays;

public class SelectionSort {
    public static void main(String[] args) {
        // 선택 정렬을 구현한 코드입니다.
        int[] arr = new int[10];
        for (int n = 0; n < arr.length; n++) {
            arr[n] = (int) (Math.random() * 10);
        }
        // 임의의 순서로 나열된 배열 할당.
        int swap; // 조건에 맞으면 swap 하기 위한 변수 생성
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    swap = arr[i];
                    arr[i] = arr[j];
                    arr[j] = swap;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

마찬가지로 이중 for 문을 써서 시간복잡도가 O(n²) 입니다.

 

 

버블정렬 (Bubble Sort)

버블 정렬은,

인접한 두 값을 비교하는 정렬법이기 때문에,

매 반복마다 배열의 끝부분에 하나씩 정렬이 되므로,

외부 for 문의 범위를

매번 하나씩 줄어드는 형태로 작성합니다.

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        // 버블 정렬을 구현한 코드입니다.
        int[] arr = new int[10];
        for (int n = 0; n < arr.length; n++) {
            arr[n] = (int) (Math.random() * 10);
        }
        // 임의의 순서로 나열된 배열 할당.
        int swap; // 조건에 맞으면 swap 하기 위한 변수 생성
        for (int i = arr.length - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = swap;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

역시나 이중 for 문이라 시간복잡도가 O(n²) 입니다.

 

셸정렬 (Shell Sort)

셸 정렬은 특이하게 

코드로 작성하게 되면 3중 for 문을 써야합니다.

이유는,

1. gap 의 간격이 줄어들기 위한 반복문,

2. gap 간격으로 분리된 배열 만큼 반복문을 수행,

3. 그 반복문 안에서 정렬을 수행하는 것입니다. 

 

따라서 얼핏 느끼기엔 쓸데없이 복잡한 것 같습니다만,

쓸데없진 않고 복잡하긴 합니다.

아래에 코드로 보여드리겠습니다.

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        // 셸 정렬을 구현한 코드입니다.
        int[] arr = new int[10];
        for (int n = 0; n < arr.length; n++) {
            arr[n] = (int) (Math.random() * 10);
        }
        // 임의의 순서로 나열된 배열 할당.
        int swap; // 조건에 맞으면 swap 하기 위한 변수 생성
        // 셸정렬은 gap 을 이용해서 배열을 부분정렬하고,
        // 매 반복마다 gap 을 반씩 줄여나가며 정렬을 수행합니다.
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            // 매 반복시의 갭 간격 설정
            for (int i = 0; i < arr.length - gap; i++) {
                // 각 반복에서 필요한 만큼만 순환하게끔 범위 설정
                for (int j = i + gap; j < arr.length; j += gap) {
                    // 분리된 각 배열을 오름차순 정렬
                    if (arr[i] > arr[j]) {
                        // 조건에 맞으면 swap
                        swap = arr[i];
                        arr[i] = arr[j];
                        arr[j] = swap;
                    }
                }
            }
        }

        System.out.println(Arrays.toString(arr));
    }
}

위와 같이 정렬을 수행했을 때의 시간복잡도는,

평균적으로 O(n¹·⁵), 최악일 때  O(n²) 입니다.

 

 

퀵정렬 (Quick Sort)

퀵 정렬은,

정렬법중에 가장 빠릅니다.

재귀형으로 코드를 구현하는 것이 보통인데,

이유는 배열이 pivot 을 기준으로

계속 분할하며 정렬되기 때문입니다.

따라서 꼭 종료구문을 넣어줘야 함에

신경써서 코드를 작성해야 합니다.

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        // 퀵 정렬을 구현한 코드입니다.
        int[] arr = new int[10];
        for (int n = 0; n < arr.length; n++) {
            arr[n] = (int) (Math.random() * 10);
        }
        // 임의의 순서로 나열된 배열 할당.

        quickSort(arr, 0, arr.length - 1);
        // 퀵 정렬은 low 와 high 를 기준으로
        // 서로 교차하는 방향으로 탐색하면서 분할 정렬합니다.

        System.out.println(Arrays.toString(arr));

    }

    static void quickSort(int[] arr, int low, int high) {
        // 원본 배열의 원소를 직접 swap 하기 때문에,
        // 원본 배열인 arr 과,
        // pivot 을 기준으로 분할해서 정렬할
        // low 와 high 를 인자로 받습니다.
        if (low >= high) return;
        // low 와 high 가 같아졌다는 건
        // 더이상 분할이 안된다는 의미이므로,
        // 재귀형의 종료 구문을 작성해줍니다.
        int pivot = low + (high - low) / 2;
        // pivot 은 각각 분할된 low 와 high 의
        // 범위 내라면 아무거나 상관없고,
        // 성능을 높이려면 원소들 중 몇 개를 확인한 뒤,
        // 그 중 중간인 값을 지정하는 게 가장 좋습니다만,
        // 아직 거기까진 구현하지 못해 중간지점으로 합니다.
        int pValue = arr[pivot];
        // swap 되는 과정에서 pivot 이 바뀔 수 있기 때문에,
        // 따로 변수를 할당받습니다.
        int left = low;
        int right = high;
        // low 와 high 는 범위로써 작용해야 하고,
        // 증가 혹은 감소하는 인덱스의 역할로써
        // left 와 right 를 지정합니다.

        while (left <= right) {
            // left 와 right 가 같아지면
            // 서로 위치가 교차하는 것이기 때문에,
            // 반복을 종료합니다.
            while (arr[left] < pValue) {
                left++;
            }
            while (arr[right] > pValue) {
                right--;
            }
            // 각 while 문에서는
            // pivot 값을 기준으로 교체해야 하는 값이 나올 때까지
            // 인덱스를 옮겨가며 비교를 합니다.
            if (left <= right) {
                // 교체하기 전에,
                // 두 인덱스의 위치가 교차하지 않았는지
                // 확인합니다.
                int swap = arr[left];
                arr[left] = arr[right];
                arr[right] = swap;
                left++;
                right--;
            }
        }

        quickSort(arr, low, right);
        quickSort(arr, left, high);
        // 왼쪽과 오른쪽을 분할해서 같은 작업을 수행합니다.
    }
}

이미 정렬된 배열의 경우엔 pivot 의 좌우가 불균형해져서,

최악일 땐 O(n²), 평균적으론 O(nlog₂n) 의 시간복잡도를 가집니다.

 

 

합병정렬 (Merge Sort)

병합 정렬은 일반적으로,

배열을 2개씩 나눌수 없을 때까지 분할하고,

분할된 배열을 비교해서,

합쳐질 배열에 조건에 맞는 순서대로 담아서 정렬합니다.

마찬가지로 합치는 과정을 반복하면 배열이 1개가 되는데,

이렇게 되면 정렬이 완료됩니다.

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        // 합병 정렬을 구현한 코드입니다.
        int[] arr = new int[11];
        for (int n = 0; n < arr.length; n++) {
            arr[n] = (int) (Math.random() * 10);
        }
        // 임의의 순서로 나열된 배열 할당.

        mergeSort(arr, arr.length);
        // 병합 정렬은 더이상 나눌 수 없을 때까지
        // 분할한 뒤, 합치면서 정렬하는 방식입니다.

        System.out.println(Arrays.toString(arr));
    }

    static void mergeSort(int[] arr, int size) {
        if (size < 2) return;
        // 병합 정렬은 재귀형을 띄기 때문에,
        // 분할된 배열의 크기가 1이면 더 이상 나눌 수 없으니 종료 구문을 넣습니다.

        int middle = size / 2;
        int[] l = new int[middle];
        int[] r = new int[size - middle];
        // 절반으로 나눈 뒤, 분할된 배열을 생성합니다.

        for (int i = 0; i < middle; i++) {
            l[i] = arr[i];
        }
        for (int i = middle; i < size; i++) {
            r[i - middle] = arr[i];
        }
        // 각 분할 배열에 원래 배열의 값을 담습니다.

        mergeSort(l, middle);
        mergeSort(r, size - middle);
        merge(arr, l, r, middle, size - middle);
        // 재귀형으로 호출하여 분할하고,
        // 합치는 메소드를 사용하여 정렬합니다.
    }

    static void merge(int[] arr, int[] l, int[] r, int left, int right) {
        // 원본배열 arr, 비교하며 조건에 맞는 순서대로 들어갈 배열 l 과 r,
        // 각 배열의 크기를 나타내는 left 와 right 를 인자로 받습니다.

        int arrIdx = 0, lIdx = 0, rIdx = 0;
        // l, r 의 원소들 중 조건에 맞는 것이 먼저 들어가고,
        // 그 다음 비교를 하기 위해 lIdx, rIdx 를 따로 변수로 지정합니다.
        // arrIdx 는 비교될 때마다 값이 증가하며,
        // 원본 배열에 순차적으로 담기기 위한 변수입니다.

        while (lIdx < left && rIdx < right) {
            // l 과 r 이 서로 비교하며 조건에 맞는 값이 먼저 들어가는데,
            // 둘 중 하나라도 더이상 비교할 값이 없으면 반복문이 종료됩니다.
            if (l[lIdx] > r[rIdx]) arr[arrIdx++] = r[rIdx++];
            else arr[arrIdx++] = l[lIdx++];
        }
        while (lIdx < left) arr[arrIdx++] = l[lIdx++];
        while (rIdx < right) arr[arrIdx++] = r[rIdx++];
        // 처음 while 문에서 비교되지 못하고 남은 원소가 
        // l 의 것인지 r 의 것인지 모르기 때문에,
        // 두개의 while 을 넣어줘서 둘 다 확인합니다.
    }
}

합병정렬의 좋은 점은, 아무리 배열의 길이가 길어도,

2개씩 분할하면 배열이 log₂n 번 만에 분할이 완료되고,

합쳐지는 과정에서도 n번만에 합쳐지는게 끝나기 때문에,

시간복잡도가 무조건 O(nlog₂n)이 됩니다.

단점으론,

당연하게도 분할될 배열을 추가적으로 생성해야 해서

메모리가 추가로 필요합니다.

 

 

힙정렬 (Heap Sort)

힙 정렬은, 완전 이진트리를 사용해서,

부모 노드와 자식노드를 비교하고,

최대힙 혹은 최대힙을 만드는 과정인

"heapify" 를 통해 원하는 힙을 만들고,

최상위 인덱스와 최하위 인덱스를 교환한 뒤,

다시 heapify 를 반복 수행함으로써 정렬을 합니다.

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        // 힙 정렬을 구현한 코드입니다.
        int[] arr = new int[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 10);
        }
        // 임의의 순서로 나열된 배열 할당.
        heapSort(arr, arr.length);
        // 힙 정렬은 이진트리를 구현해서 정렬하는 방식으로,
        // 부모 root 와 자식과의 비교를 통해서 정렬하고,
        // 자식 노드가 다시 부모가 돼서 비교하는 형태로
        // 최대힙 또는 최소힙을 만든 뒤,
        // 최상위 인덱스와 최하위 인덱스를 맞바꾸고,
        // 최하위 인덱스를 제외하고 위 과정을 반복해서
        // 오름차순 혹은 내림차순 정렬을 완성합니다.
        System.out.println(Arrays.toString(arr));
    }

    static void heapSort(int[] arr, int size) {
        // 원본 배열을 직접 참조해서 최대힙을 만들고 정렬하기 때문에
        // arr 을 인자로 받고,
        // 마지막 부모 노드의 위치를 구하고,
        // 최대힙 완성 이후에 반복 작업을 수행하기 위해
        // arr 의 length 를 인자로 받고,
        // 가독성을 위해 size 라고 표현합니다.
        for (int i = size / 2 - 1; i >= 0; i--) {
            // 자식노드 위치의 배열크기를 2로 나눈 후 1을 빼면
            // 부모 인덱스의 값이 나오는데,
            // 이것을 이용하면 현재 i 가 root 노드가 되고,
            // 이것을 이용해 heapify(= 이진트리를 힙구조로 재배열) 를
            // root 를 감소시키며 수행함으로써
            // 최대힙 또는 최소힙을 만드는 반복문 입니다.
            heapify(arr, size, i);
        }
        for (int i = size - 1; i > 0; i--) {
            // 최초 힙 재배열이 끝난 이후,
            // 최상위와 최하위 인덱스를 교환하고,
            // 최하위 인덱스는 제외한 heapify 를
            // 반복해서 수행함으로써 원하는 정렬을 완성합니다.
            int swap = arr[0];
            arr[0] = arr[i];
            arr[i] = swap;

            heapify(arr, i, 0);
        }
    }

    static void heapify(int[] arr, int size, int root) {
        // 원본 배열인 arr 과
        // heapify 를 수행할 범위를 지정할 size 를 인자로 받고,
        // 비교 및 재배열을 위해 root 를 인자로 받습니다.
        int largest = root;
        int l = root * 2 + 1;
        int r = root * 2 + 2;
        // root 값이 최대힙 혹은 최소힙을 만들기 위해
        // 비교 과정에서 교체 될 수 있는데,
        // 나중에 교체 됐는지 여부를 확인하기 위해
        // root 값을 복사한 변수 largest 를 만들고,
        // 자식노드 l 과 r 을 만듭니다.

        if (l < size && arr[l] > arr[largest]) largest = l;
        if (r < size && arr[r] > arr[largest]) largest = r;
        // root 에 자식노드가 존재하지 않을 수 있기 때문에,
        // size 와 비교를 해서 예외를 방지하고,
        // l 이나 r 값이 부모 노드 값보다 크면
        // largest 값을 바꿈으로써
        // 비교 대상이 되는 인덱스를 바꿉니다.

        if (largest != root) {
            // 원래 인덱스인 root 와
            // 그것을 복사한 largest 가 같지 않으면
            // 자식 노드와 인덱스 교체가 일어난 것입니다.
            int swap = arr[root];
            arr[root] = arr[largest];
            arr[largest] = swap;
            // 따라서 실제 값을 교체해줌으로써,
            // 최대힙 또는 최소힙을 만드는 heapify
            // 를 수행합니다.

            heapify(arr, size, largest);
            // 그리고 교체된 자식 노드에서 같은 과정을 반복합니다.
        }
    }
}

코드를 구현하는 것이 꽤 복잡하지만, 

평균, 최악, 최선 시간 복잡도가 모두 O(nlog₂n) 이며,

추가적인 배열 생성이 없어서 메모리 효율도 좋습니다.

 

 

기수정렬 (Radix Sort)

기수 정렬은, 개념은 쉽고 재밌지만,

마찬가지로 구현하는 것은 약간 복잡합니다.

이미 존재하는 Queue 를 이용할 수도 있지만,

주어진 배열에서 Queue 로 옮기는 것부터가

추가적인 메모리를 쓰는 것이기 때문에,

같은 기능을 하는 코드를 구현함으로써

기수 정렬을 만들 수 있습니다.

import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        // 기수 정렬을 구현한 코드입니다.
        int[] arr = new int[10];
        for (int i = 0; i < arr.length; i++)
            arr[i] = (int) (Math.random() * 1000);
        // 임의의 순서로 나열된 배열 할당.
        radixSort(arr, arr.length);
        // 기수 정렬은 큐를 이용하거나,
        // 큐의 개념과 비슷한 로직을 사용해서
        // 정렬하는 방법입니다.
        System.out.println(Arrays.toString(arr));
    }

    static void radixSort(int[] arr, int size) {
        // arr 정렬하고자 하는 배열,
        // 여기서 size 는 따로 받지 않아도 되지만,
        // 가독성을 위해 arr 의 length 를 인자로써 받습니다.
        int max = arr[0];
        // 기수 정렬은 숫자의 단위를 X10 씩 옮겨가며 정렬합니다.
        // 따라서 몇 자리 단위 까지 정렬해야 하는지
        // 알기 위해 최대값을 받을 변수를 할당합니다.
        for (int i = 0; i < size; i++)
            // 최대값을 찾는 간단한 반복문입니다.
            if (max < arr[i]) max = arr[i];

        for (int scope = 1; max / scope > 0; scope *= 10)
            // 확인한 최대값을 이용해,
            // 1의 단위부터 정렬을 시작하는 반복문입니다.
            // scope 는 지정된 단위를 가리키는 변수이고,
            // max 의 단위보다 커지면 종료됩니다.
            countSort(arr, size, scope);
        // countSort 라고 이름 지은
        // 내부 메소드를 반복적으로 호출해서,
        // 해당 scope 별로 정렬을 수행합니다.

    }

    static void countSort(int[] arr, int size, int scope) {
        // 정렬할 배열 arr 과, 가독성을 위해 인자로 받은 size,
        // 현재 scope 에 해당하는 자리를 정렬하기 위해
        // scope 를 인자로 받습니다.
        int[] bucket = new int[10];
        int[] sorted = new int[size];
        // 숫자는 0부터 9까지 있기 때문에,
        // 각 숫자를 차곡차곡 담을 배열 bucket 을 만들고,
        // 원본 arr 의 자리 값을 bucket 에 담은 것을
        // 기준으로 삼아서 정렬할 배열 sorted 를 생성합니다.
        int i;
        // 반복문이 많이 등장해서 가독성을 위해 변수를
        // 위에서 먼저 만들었습니다.

        for (i = 0; i < size; i++) bucket[(arr[i] / scope) % 10]++;
        // arr[i] 의 현재 자리 값만 필요하기 때문에,
        // scope 로 나눠서 현재 정렬할 자리를 1의 자리로 오게 하고,
        // % 10 으로 1의 자리 값만을 받아서,
        // 해당 bucket 의 인덱스를 증가시키는 반복문입니다.

        for (i = 1; i < 10; i++) bucket[i] += bucket[i - 1];
        // 큐의 FIFO 를 구현하기 위해
        // 누적합을 먼저 만드는 반복문입니다.

        for (i = size - 1; i >= 0; i--) {
            sorted[bucket[arr[i] / scope % 10] - 1] = arr[i];
            bucket[arr[i] / scope % 10]--;
            // 복잡해 보이고 실제로도 약간 복잡한데,
            // (arr[i] / scope) % 10 는 위에서 설명한 대로,
            // 현재 자리 값만 받아오는 것이고,
            // 그것의 bucket 인덱스를 확인하면,
            // 어느 자리에 위치해야 하는지를 알 수 있는데,
            // -1 을 하는 이유는
            // bucket 에는 개수로써 값이 담기기 때문에
            // sorted 에 다시 인덱스로 담기 위해 -1 을 하고,
            // 그 인덱스에 원래 정렬하려 했던
            // arr[i] 값을 담아서 정렬합니다.
        }

        for (i = 0; i < size; i++) arr[i] = sorted[i];
        // 현재 scope 가 정렬된 sorted 배열은
        // 지역 변수이기 때문에,
        // arr 값을 변경하기 위한 반복문입니다.
    }
}

O(nw) 라는 아주 폭력적인 시간복잡도가 장점이고,

bucket 을 활용하기 때문에 추가 메모리가 필요한 단점이 있습니다.

 

어려운 정렬법들은

다른 코드들을 많이 참조하고 배웠지만,

아마 약간 다를텐데 그 이유가,

쓸데 없는 부분은 덜어내고,

가독성이 떨어지는 변수명은 변경하고,

이런 저런 수정을 해서 저같은 초보도

이해하기 좋게 코드를 만들어봤습니다.