정렬 알고리즘의 종류와 자바의 정렬 알고리즘

안정 정렬과 불안정 정렬

• 정렬 후에도 같은 값을 가진 원소들의 상대적인 순서가 유지되는 정렬 알고리즘
• 안정 정렬(Stable Sort)이란 [5a, 3b, 5c]를 정렬해도 [3b, 5a, 5c]로 상대적인 순서가 유지되는 것을 말함
• 예를 들어 User라는 객체가 있고 나이순으로 정렬하고 싶은데 나머지는 기존 순서를 유지하고 싶다면 안정 정렬을 사용해야 함

선택정렬(Selection Sort)

• 1번째부터 끝까지 훑어서 가장 작은 1번째, 2번째부터 끝까지 훑어서 가장 작은게 2번째... 정렬이 끝날 때까지 반복함
• 

public static void main(String[] args) throws Exception {
    int[] arr = new int[]{8,3,1,5,6,2,9,7,4};

    int min = 0;
    for (int i = 0; i < arr.length; i++) {
        for (int j = i; j < arr.length; j++) {
            if(arr[j] < arr[min])min = j;
        }
        swap(arr, i, min);
    }

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

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

삽입정렬(Insertion Sort)

• 삽입 정렬은 현재 위치의 값은 TEMP에 저장한 뒤 TEMP보다 큰 값을 한 칸씩 뒤로 밀어내고, 앞의 빈자리에 TEMP가 들어가는 방식으로 정렬하는 알고리즘
• 

public static void main(String[] args) throws Exception {
    int[] arr = new int[]{8,3,1,5,6,2,9,7,4};

    for(int i = 1; i < arr.length; i++) {
        int tmp = arr[i];
        int j = i - 1;
        while(j >= 0 && arr[j] > tmp) {
            // 다음 칸으로 현재 값을 옮김
            arr[j + 1] = arr[j];
            j--;
        }
        // tmp 값을 현재 위치에 삽입
        // 현재 위치는 tmp보다 작은 값의 바로 뒤
        arr[j + 1] = tmp;
    }

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

버블정렬(Bubble Sort)

• 이중 반복을 돌면서 원소가 자기보다 더 큰 값이 없을 때까지 계속해서 위로 올라가는 방식으로 정렬하는 알고리즘
• 

public static void main(String[] args) throws Exception {
    int[] arr = new int[]{8,3,1,5,6,2,9,7,4};

    for(int i = 0; i < arr.length; i ++) {
        // -i를 하는 이유는 정렬함에 따라
        // i개의 가장 큰 원소를 가지기 때문
        for(int j = 0; j < arr.length - i - 1; j ++) {
            if(arr[j] > arr[j + 1]) swap(arr, j, j + 1);
        }
    }

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

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

버블정렬이 최선 케이스 O(n)인 이유

• 버블정렬에 아래와 같은 조건을 추가하면 최선 케이스가 O(n)이 됨

public static void main(String[] args) throws Exception {
    int[] arr = new int[]{8,3,1,5,6,2,9,7,4};
    boolean swapped = false;

    for(int i = 0; i < arr.length; i ++) {
        swapped = false;
        // -i를 하는 이유는 정렬함에 따라
        // i개의 가장 큰 원소를 가지기 때문
        for(int j = 0; j < arr.length - i - 1; j ++) {
            if(arr[j] > arr[j + 1]) {
                swapped = true;
                swap(arr, j, j + 1);
            }
            if(!swapped) break;
        }
    }

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

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

병합정렬

• 배열을 원소 1개짜리 배열로 계속해서 쪼개고 쪼개진 부분을 합치면서 정렬하는 방식
• 

public static void main(String[] args) throws Exception {
    int[] arr = new int[]{8, 3, 1, 5, 6, 2, 9, 7, 4};

    sorted = new int[arr.length];    // 정렬된 배열을 담을 공간
    mergeSort(arr, 0, arr.length - 1);

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

// Top-Down 방식 구현
private static void mergeSort(int[] a, int left, int right) {

    /*
     *  left==right 즉, 부분리스트가 1개의 원소만 갖고있는경우
     *  더이상 쪼갤 수 없으므로 return한다.
     */
    if (left == right) return;

    int mid = (left + right) / 2;    // 절반 위치

    mergeSort(a, left, mid);        // 절반 중 왼쪽 부분리스트(left ~ mid)
    mergeSort(a, mid + 1, right);    // 절반 중 오른쪽 부분리스트(mid+1 ~ right)

    merge(a, left, mid, right);        // 병합작업

}

/**
 * 합칠 부분리스트는 a배열의 left ~ right 까지이다.
 *
 * @param a     정렬할 배열
 * @param left  배열의 시작점
 * @param mid   배열의 중간점
 * @param right 배열의 끝 점
 */
private static void merge(int[] a, int left, int mid, int right) {
    int l = left;        // 왼쪽 부분리스트 시작점
    int r = mid + 1;    // 오른쪽 부분리스트의 시작점
    int idx = left;        // 채워넣을 배열의 인덱스

    while (l <= mid && r <= right) {
        /*
         *  왼쪽 부분리스트 l번째 원소가 오른쪽 부분리스트 r번째 원소보다 작거나 같을 경우
         *  왼쪽의 l번째 원소를 새 배열에 넣고 l과 idx를 1 증가시킨다.
         */
        if (a[l] <= a[r]) {
            sorted[idx] = a[l];
            idx++;
            l++;
        }
        /*
         *  오른쪽 부분리스트 r번째 원소가 왼쪽 부분리스트 l번째 원소보다 작거나 같을 경우
         *  오른쪽의 r번째 원소를 새 배열에 넣고 r과 idx를 1 증가시킨다.
         */
        else {
            sorted[idx] = a[r];
            idx++;
            r++;
        }
    }

    /*
     * 왼쪽 부분리스트가 먼저 모두 새 배열에 채워졌을 경우 (l > mid)
     * = 오른쪽 부분리스트 원소가 아직 남아있을 경우
     * 오른쪽 부분리스트의 나머지 원소들을 새 배열에 채워준다.
     */
    if (l > mid) {
        while (r <= right) {
            sorted[idx] = a[r];
            idx++;
            r++;
        }
    }

    /*
     * 오른쪽 부분리스트가 먼저 모두 새 배열에 채워졌을 경우 (r > right)
     * = 왼쪽 부분리스트 원소가 아직 남아있을 경우
     * 왼쪽 부분리스트의 나머지 원소들을 새 배열에 채워준다.
     */
    else {
        while (l <= mid) {
            sorted[idx] = a[l];
            idx++;
            l++;
        }
    }

    /*
     * 정렬된 새 배열을 기존의 배열에 복사하여 옮겨준다.
     */
    for (int i = left; i <= right; i++) {
        a[i] = sorted[i];
    }
}

힙 정렬(Heap Sort)

• 힙을 사용해서 정렬하는 방법
• 힙에 데이터를 삽입할 때 O(logN)의 시간복잡도를 가지기 때문에 해당 정렬의 시간 복잡도도 O(NlogN)임
• 

public static void main(String[] args) throws Exception {
    int[] arr = new int[]{8, 3, 1, 5, 6, 2, 9, 7, 4};
    Queue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o));
    pq.addAll(Arrays.stream(arr).boxed().toList());
    for (int i = 0; i < arr.length; i++) {
        if(!pq.isEmpty()) arr[i] = pq.poll();
    }

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

퀵 정렬

• pivot을 기준으로 왼쪽에 피벗보다 큰 값, 오른쪽의 피벗보다 작은 값을 swap하면서 피벗의 위치를 계속 변경함
• 이 때 피벗의 위치는 더 이상 쪼개지지 않을 때까지 반복함
• 

public static void main(String[] args) throws Exception {
    int[] arr = new int[]{8, 3, 1, 5, 6, 2, 9, 7, 4};
    quickSort(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
}

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

private static void quickSort(int[] arr, int left, int right) {
    int part = partition(arr, left, right);
    if (left < part - 1) {
        quickSort(arr, left, part - 1);
    }
    // 더 이상 쪼개지지 않을 때까지
    if (part < right) {
        quickSort(arr, part, right);
    }
}

private static int partition(int[] arr, int left, int right) {
    int pivot = arr[(left + right) / 2];
    while (left <= right) { // 해당 부분 배열에 대해 반복
        while (arr[left] < pivot) { //피벗보다 큰 left를 찾음
            left++;
        }
        while (arr[right] > pivot) { //피벗보다 작은 right를 찾음
            right--;
        }
        if (left <= right) { //left가 right보다 왼쪽에 있으면 둘이 자리 바꿈
            swap(arr, left, right);
            left++;
            right--;
        }
    }
    return left;
}

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

트리 정렬

• 이진 탐색 트리를 만들어 정렬하는 방식
• 추가될 값이 기존 노드 값보다 작으면 왼쪽 자식으로 크거나 같으면 오른쪽 자식 위치로 감

힙 정렬 vs 트리 정렬

• 힙은 완전 이진 트리의 일종으로 마지막 노드를 제외하면 모두 2개의 자식을 가지고 있는 트리 구조를 의미함
• 또한 부모의 값이 항상 더 큰 값을 가지는 최대 힙과 부모의 값이 항상 더 작은 값을 가지는 최소 힙이 있음
• 반면, 이진 탐색 트리의 경우 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 값을 가지는 트리 구조를 의미함
• 만약 아래와 같이 편향된 이진 탐색 트리가 만들어진다면 트리 정렬의 시간 복잡도는 O(n²)이 될 수 있음
  • 첫 번째 삽입: 트리가 비어 있으므로 탐색 비용은 (O(0)).
  • 두 번째 삽입: 트리의 높이가 1이므로 탐색 비용은 (O(1)).
  • 세 번째 삽입: 트리의 높이가 2이므로 탐색 비용은 (O(2)).
  • ...
  • (N)번째 삽입: 트리의 높이가 (N-1)이므로 탐색 비용은 (O(N-1)).
  • 이를 수식으로 표현하면 (N-1)N/2이므로 O(N²)이 됨

1
 \
  2
   \
    3
     \
      4
       \
        5

정렬 알고리즘 시간/공간 복잡도 및 안정성 비교

자바에서 사용하는 정렬 알고리즘

Arrays.sort()

• 타입에 따라서 다른 정렬 방식을 씀
  • Primitive -> Dual-Pivot Quicksort
  • Reference -> TimeSort
• ⚠️ 아래는 Dual-Pivot Quicksort 기준
• 두 개의 피벗으로 배열을 세 부분으로 나눠 정렬
• 시간 복잡도: 최선/평균 O(n log n), 최악 O(n^2)
• 공간 복잡도: O(log n)
• 안정 정렬 아님

Collections.sort()

• TimSort 사용
• 합병 정렬과 삽입 정렬의 하이브리드
• 시간 복잡도: 최선/평균/최악 O(n log n)
• 공간 복잡도: O(n)
• 안정 정렬
• 객체 데이터(List 등) 정렬에 적합

참고 자료

• https://www.youtube.com/watch?v=qzfeVeajuyc
• https://s-satsangi.medium.com/insertion-sort-selection-sort-and-bubble-sort-5eb16d55a4de
• https://velog.io/@kku64r/sort
• https://st-lab.tistory.com/233