기수정렬(Ridix Sort)

개념

Radix Sort란 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘입니다. 기수 정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요합니다.

로직

1. 데이터 중 가장 큰 자리수를 구합니다.
2. 가장 작은 자리수부터 가장 큰 자리수까지 해당 자리수만을 보고 Conting Sort를 진행합니다.

위 GIF 이미지는 Queue를 사용한 방식을 더 잘 표현하는 것 같다.

코드

RadixSort.java

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class RadixSort {

    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        radixSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

    private static void radixSort(int[] arr) {
        // 최대값 구하기
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i])
                max = arr[i];
        }

        // Counting Sort를 사용하여 해당 자리 정렬하기.
        for (int digit = 1; digit <= max; digit *= 10) {
            countingSort(arr, digit);
        }
    }

    private static void countingSort(int[] arr, int digit) {
        int[] temp = new int[N]; // 임시로 사용할 공간
        int[] counting = new int[10]; // 카운팅 배열

        for (int i = 0; i < N; i++) {
            int num = (arr[i] / digit) % 10; // 해당 자리수의 숫자 추출
            counting[num]++;
        }

        // 누적합 배열로 만들기
        for (int i = 1; i < counting.length; i++) {
            counting[i] += counting[i - 1];
        }

        // 뒤에서 부터 시작 >> 값이 큰것이 뒤로 가야하기 때문
        for (int i = 0; i < N; i++) {
            int num = (arr[i] / digit) % 10;
            int index = counting[num];

            temp[index - 1] = arr[i];
            counting[num]--;
        }

        // 복사
        for (int i = 0; i < N; i++) {
            arr[i] = temp[i];
        }
    }

}

console

정렬 전: [40, 58, 27, 29, 95, 33, 76, 93, 39, 36]
정렬 후: [29, 27, 39, 36, 33, 40, 58, 76, 95, 93]

시간복잡도

배열에서 가장 큰 자리수의 값만큼 Counting Sort를 수행한다. 만약 배열의 최대 원소의 값이 1350이라면 총 4번을 수행하게 됩니다.

한번의 Counting Sort는 $O(n+k)$의 시간복잡도를 같으며 $k=10$으로 $O(n)$으로 표현이 가능합니다.

따라서 정렬할 숫자의 자릿수를 $d$라고 하면 시간 복잡도는 $O(dn)$으로 표현 할 수 있습니다.

기수 정렬은 비교 연산을 하지 않으며, 무엇보다도 전체 시간 복잡도 역시 $O(dn)$이어서, 정수와 같은 자료의 정렬 속도가 매우 빠릅니다.

데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다. 기수 정렬은 정렬 방법의 특수성 때문에, 부동소수점실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없지만, 사용 가능할 때에는 매우 좋은 알고리즘이다.

장점

1. 자리수를 비교해 정렬하기때문에 문자열도 정렬이 가능하다.
2. $O(dn)$의 빠른시간으로 정렬이 가능
3. 안정 정렬 이다.

단점

1. 자릿수가 없는 것은 정렬이 불가능 하다.
2. 추가적인 메모리 공간이 필요하다.

계수정렬(Counting Sort)

개념

Counting Sort는 숫자들간 비교를 하지 않고 정렬을 하는 알고리즘이다. 각 숫자가 몇개 있는지 개수를 세어 저장한 후에 정렬하는 방식이다.

로직

1. 정렬하고자 하는 배열의 최대값을 구한다.
2. 최대값 크기의 배열에 각 원소를 순회하며 해당 값이 몇개인지 저장한다.
3. 저장된 데이터를 순서대로 출력한다.

코드

CountingSort.java

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class CountingSort {

    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        countingSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

    private static void countingSort(int[] arr) {
        // 최대값 구하기
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i])
                max = arr[i];
        }

        int[] counting = new int[max + 1]; // 카운팅 배열

        for (int i = 0; i < N; i++) {
            counting[arr[i]]++;
        }

        int index = 0;
        for (int i = 0; i < counting.length; i++) {
            while (counting[i]-- > 0) {
                arr[index++] = i;
            }
        }
    }
}

console

정렬 전: [71, 89, 39, 93, 92, 27, 19, 15, 74, 76]
정렬 후: [15, 19, 27, 39, 71, 74, 76, 89, 92, 93]

시간복잡도

$O(N+K)$ : 이때, $K$는 배열의 최대값이다.

장점

1. $O(N)$의 매우 빠른 속도로 정렬이 가능하다.

단점

1. 음수나 실수는 정렬할 수 없다.
2. 추가적인 메모리 공간이 필요하며 값의 분포의 따라 메모리 낭비가 심할 수 있다.

힙 정렬(Heap Sort)

개념

Heap Sort는 Heap를 이용한 정렬 방법입니다.

Heap

Heap는 최대값 또는 최소값을 빠르게 찾기 위해 고안된 완전이진트리를 기본으로한 자료구조입니다.

Heap의 종류로 최대힙과 최소힙이 있습니다.

최대힙이라면 부모노트의 키값보다 자식노드의 키값이 작다는 특징이 있습니다.

로직

최대 힙이나 최소 힙을 구성하여 정렬을 하는 방법

1. 정렬해야 할 n개의 데이터를 최대 힙또는 최소힙으로 구성
2. 힙의 root노드에서 값을 순서대로 추출한다.
   • root노드의 값을 heap을 구성하는 마지막 노드와 교환한뒤 힙의 크기를 1만큼 줄이는 방식

코드

HeapSort.java

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class HeapSort {

    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

    private static void heapSort(int[] arr) {
        int n = arr.length;

        // maxHeap을 구성
        // n/2-1 : 부모노드의 인덱스를 기준으로 왼쪽(i*2+1) 오른쪽(i*2+2)
        // 즉 자식노드를 갖는 노트의 최대 개수부터
        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); // 요소를 제거한 뒤 다시 최대힙을 구성
        }
    }

    private static void heapify(int[] arr, int n, int i) {
        int p = i;
        int l = i * 2 + 1;
        int r = i * 2 + 2;

        // 왼쪽 자식노드
        if (l < n && arr[p] < arr[l])
            p = l;
        // 오른쪽 자식노드
        if (r < n && arr[p] < arr[r])
            p = r;

        // 부모노드 < 자식노드
        if (i != p) {
            swap(arr, p, i);
            heapify(arr, n, p);
        }
    }

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

console

정렬 전: [65, 83, 96, 81, 38, 48, 29, 45, 89, 51]
정렬 후: [29, 38, 45, 48, 51, 65, 81, 83, 89, 96]

시간복잡도

힙생성(heapify) 알고리즘의 시간 복잡도는 $O(logN)$

장점

1. 추가적인 메모리를 필요로 하지 않으면서 항상 $O(NlogN)$으로 빠른 편이다.

단점

1. 불안정 정렬이다.

병합정렬(Merge sort)

개념

정렬할 배열을 반으로 나누어 좌측과 우측 배열을 계속하여 분할해 나간 후 각 배열내에서 정렬 후 병합하는 과정을 통해 정렬하는 알고리즘입니다.

분할 정복

큰 문제를 작은 문제 단위로 쪼개면서 해결해 나가는 방식

로직

데이터의 크기를 계속 반으로 나누고 이를 정렬하면서 다시 합치는 방법

Merge Sort는 배열의 길이가 1이하이면 이미 정렬된 것으로 본다.

정렬되지 않은 경우에

1. 분할(Divide) : 배열을 반으로 나눈다.
2. 정복(conquer) : 나누어진 배열이 여전히 분할이 가능하다면 분할을 수행한다. 그렇지 않으면 결합하여 정렬을 수행한다.
3. 결합 (combine): 두 부분의 배열을 다시 하나의 정렬된 리스트로 병합한다. 이때 결과는 임시배열에 저장된다.
4. 복사(copy) : 임시배열에 저장된 결과를 원래 배열에 복사한다.

와 같은 과정을 통해 정렬한다.

코드

MergeSort.java

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class MergeSort {

    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        mergeSort(0, N - 1, arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

    // divide
    private static void mergeSort(int start, int end, int[] arr) {
        if (start >= end)
            return;

        int mid = (start + end) / 2;
        mergeSort(start, mid, arr); // left
        mergeSort(mid + 1, end, arr); // right

        merge(start, mid, end, arr);
    }

    // conquer
    private static void merge(int start, int mid, int end, int[] arr) {
        int[] temp = new int[end - start + 1];
        int i = start, j = mid + 1, k = 0;

        // combine
        while (i <= mid && j <= end) {
            if (arr[i] < arr[j])
                temp[k++] = arr[i++];
            else
                temp[k++] = arr[j++];
        }
        while (i <= mid)
            temp[k++] = arr[i++];
        while (j <= end)
            temp[k++] = arr[j++];

        // copy
        while (k-- > 0)
            arr[start + k] = temp[k];
    }
}

console

정렬 전: [1, 48, 3, 51, 19, 17, 38, 64, 72, 69]
정렬 후: [1, 3, 17, 19, 38, 48, 51, 64, 69, 72]

시간복잡도

분할하는 과정에서 $O(logN)$의 시간이 병합하는 과정에서 $O(N)$의 시간이 소요된다.

최선 최악 평균 모두 $O(NlogN)$의 시간 복잡도를 갖는다.

장점

1. Quick Sort와 달리 pivot을 설정하는 방법에 따라 성능의 차이가 없이 $O(NlogN)$의 성능을 낸다.
2. 안정 정렬이다.

단점

1. 병합하는 과정에서 데이터의 개수만큼의 추가적인 공간이 필요하다.

퀵정렬(Quick Sort)

개념

분할정복 방식으로 고안된 정렬방법으로 먼저 임의의 기준을 선택하여 그 기준보다 작은 값은 왼쪽에, 큰 값을 오른쪽에 위치시킨 후 다시 임의의 기준을 선택하여 왼쪽과 오른쪽을 반복하여 나누어 가며 정렬하는 방법

재귀호출을 사용

로직

1. 배열에서 임의의 원소 pivot을 선택한다.
2. 남아 있는 원소들은 pivot보다 큰 것과 작은 것의 두 가지로 구분된다.
3. 각 리스트는 다시 스스로를 정렬하는 메소드를 호출한다.

결론적으로 리스트는 pivot에 의해 작은 원소들과 큰 원소들로 정렬된다.

코드

QuickSort.java

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        quickSort(0, N - 1, arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

    private static void quickSort(int start, int end, int[] arr) {
        if (start >= end)
            return;

        int left = start + 1, right = end;
        int pivot = arr[start];

        while (left <= right) {
            while (left <= end && arr[left] <= pivot)
                left++;
            while (right > start && arr[right] >= pivot)
                right--;

            if (left <= right) {
                swap(arr, left, right);
            } else {
                swap(arr, start, right);
            }
        }
        quickSort(start, right - 1, arr);
        quickSort(right + 1, end, arr);
    }

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

console

정렬 전: [34, 1, 6, 10, 42, 24, 0, 30, 10, 78]
정렬 후: [0, 1, 6, 10, 10, 24, 30, 34, 42, 78]

시간복잡도

원소들은 두 개의 리스트로 분리하는 시간 복잡도는 $O(N)$이고 각각의 재귀 호출은 각 리스트의 숫자의 절반의 횟수가 발생한다. 그래서 이 알고리즘의 시간 복잡도는 $O(NlogN)$이다. 이건 평균적인 성능이다.

최악의 경우에는 $O(N^2)$이다.

정렬하고자 하는 배열의 상태와 pivot을 결정하는 방법에 따라 재귀 호출의 횟수가 최대 $N$번이 발생할 수 있기 때문이다.

pivot을 선택하는 방법(난수 분할, 중위값 선택)에 따라 어느정도 개선은 가능하다.

장점

1. 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 $O(NlogN)$를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠릅니다.
2. 정렬을 위한 추가적인 메모리 공간을 필요로 하지 않는다.

단점

1. 불안정 정렬이다.
2. 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 $O(N^2)$의 시간복잡도를 갖는다.

선택정렬(Selection Sort)

개념

Selection Sort는 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘입니다.

로직

최소값을 찾아 왼쪽으로 이동시키는데 데이터의 크기만큼 반복하여 정렬하는 방법

1. 주어진 배열에서 최소값을 찾습니다.
2. 그 값을 맨앞에 위치한 값과 교채합니다.
3. 맨처음 위치를 뺀 나머지 배열에 1~2의 과정을 반복합니다.

코드

SelectionSort.java

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class SelectionSort {

    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        selectionSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

    private static void selectionSort(int[] arr) {
        int index;
        for (int i = 0; i < arr.length; i++) {
            index = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[index] > arr[j]) {
                    index = j;
                }
            }
            swap(arr, index, i);
        }
    }

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

console

정렬 전: [56, 11, 41, 96, 29, 9, 19, 13, 39, 28]
정렬 후: [9, 11, 13, 19, 28, 29, 39, 41, 56, 96]

시간복잡도

주어진 데이터의 개수가 $n$개 일때
$$
\sum_{i=1}^{n-1}n-i=(n-1)+(n-2)+(n-3)+...+1=\frac{n(n-1)}{2}
$$
번의 비교를 하게 된다.

최선, 최악, 평균 모두 $O(N^2)$의 동일한 시간복잡도를 갖습니다.

장점

1. 알고리즘이 단순하여 구현이 쉽다.
2. Bubble Sort와 실제로 비교하는 횟수는 같지만 교환하는 횟수가 작기때문에 Bubble Sort에 비해 비교적 효율적입니다.
3. 추가적인 메모리 공간이 필요하지 않다.

단점

1. 시간복잡도가 $O(N^2)$으로 비효율적이다.
2. 불완전 정렬이다.

삽입정렬(Insertion Sort)

개념

손 안의 카드를 정렬하는 방법과 유사합니다.

Insertion Sort는 Selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘입니다.

Insertion Sort는 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬하는 알고리즘입니다.

로직

데이터가 정렬되어 있음을 가정하고 값을 해당 위치에 삽입하여 정렬하는 방법

1. 정렬은 2번째 위치(index)의 값을 temp에 저장합니다.
2. temp와 이전에 있는 원소들과 비교하며 삽입해나갑니다.
3. '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복합니다.

코드

InsertionSort.java

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class InsertionSort {

    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

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

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

console

정렬 전: [81, 14, 9, 34, 0, 88, 41, 89, 71, 26]
정렬 후: [0, 9, 14, 26, 34, 41, 71, 81, 88, 89]

시간복잡도

주어진 데이터의 개수가 $n$개일때
$$
\sum_{i=1}^{n-1}i=1+2+3+...+(n-1)=\frac{n(n-1)}{2}
$$
번의 비교를 하게 된다.

삽입정렬의 시간복잡도는 최악의 경우 $O(N^2)$이며

최선의 경우 $O(N)$이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘입니다.

삽입 정렬의 평균 시간복잡도는 $O(N^2)$입니다.

장점

1. 알고리즘이 단순하여 구현이 쉽다
2. 대부분의 원소가 이미 정렬되어 있는 경우 매우 효율적일 수 있다.
3. 추가적인 메모리 공간을 필요로 하지않는다
4. 안정 정렬이다.
5. 다른 $O(N^2)$의 시간복잡도를 갖는 알고리즘에 비해 효율적이다.

단점

1. 평균과 최악의 시간복잡도가 $O(N^2)$으로 비효율적이다.

거품정렬(Bubble Sort)

개념

Bubble Sort는 서로 인접한 두 원소의 대소를 비교하여 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘입니다.

로직

인접한 데이터 간에 교환이 계속일어나면서 정렬이 이루어지는 방법

1. 인접한 2개의 데이터를 비교하여 크기가 순서대로 정렬되어 있지 않으면 서로 교환한다
2. 교환이 이루어지지 않을 때까지 반복한다.

1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하는 특징이 있다.

코드

BubbleSort.java

아래 작성된 코드는 개선된 버전의 Bubble Sort이다.

1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하는 특징이 있기 때문에 탐색하는 범위를 줄였으며

버블정렬의 각 단계에서 데이터의 교환이 일어나지 않으면 정렬이 끝난 것을 의미하므로 다음단계를 실행하지 않고 정렬을 종료할 수 있다.

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class BubbleSort {
    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

    private static void bubbleSort(int[] arr) {
        boolean flag = true;
        int temp;
        for (int n = arr.length - 1; n > 0 && flag; n--) {
            flag = false;
            for (int i = 0; i < n; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                    flag = true;
                }
            }
        }
    }

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

console

정렬 전: [75, 28, 51, 92, 75, 15, 45, 97, 70, 79]
정렬 후: [15, 28, 45, 51, 70, 75, 75, 79, 92, 97]

시간복잡도

비교 횟수

주어진 데이터의 개수가 $n$개 일때
$$
\sum_{i=1}^{n-1}n-i=(n-1)+(n-2)+(n-3)+...+1=\frac{n(n-1)}{2}
$$
번의 비교를 하게 된다.

최선, 최악, 평균 모두 $O(N^2)$의 동일한 시간복잡도를 갖습니다.

교환 횟수

최악의 경우 원소를 비교할때마다 자리 교환이 일어나므로 최대 ${n(n-1)\over2}$번의 교환이 발생합니다.

장점

1. 알고리즘이 단순하여 구현이 쉽다.
2. 추가적인 메모리 공간이 필요하지 않다.
3. 안정 정렬이다.

단점

1. 시간복잡도가 $O(N^2)$으로 비효율적이다.
2. 정렬 되어있지 않은 원소를 정렬하기 위해 교환(swap)이 많이 일어난다.
   • 같은 시간복잡도 Selection Sort는 1번의 교환으로 정렬이 가능하다.