[JAVA] 다양한 정렬 알고리즘 개념 및 시간 복잡도 비교

1. 정렬 알고리즘 별 시간 복잡도

정렬 알고리즘	시간 복잡도
Bubble Sort (버블 정렬)	O(n^2)
Selection Sort (선택 정렬)	O(n^2)
Insertion Sort (삽입 정렬)	O(n^2)
Quick Sort (퀵 정렬)	평균 : O(nlogn) / 최악 : O(n^2)
Merge Sort (병합 정렬)	O(nlogn)
Radix Sort (기수 정렬)	O(kn) / k : 최대 데이터의 자릿수
Arrays.sort()	평균 : O(nlogn) / 최악 : O(n^2)
Collections.sort()	O(nlogn)

• 위 표를 보면 병합정렬이 퀵정렬보다 빠르다고 생각할 수 있음
• 최악의 상황에선 퀵정렬이 느리지만, 보통은 퀵정렬이 더 빠르고, 병합 정렬은 메모리를 더 많이 차지함
• 이제 이 정렬들의 개념과 코드 정리해보자
  • 모든 개념들은 오름차순 정렬을 기준으로 정리

2. Bubble Sort

2.1. 개념

• 순서대로 근접한 두 수를 비교해서 오른쪽 수가 왼쪽 수보다 더 작으면 교환
• 이 작업을 한 번 수행 할때마다 맨 끝자리에 가장 큰 수가 가게 됨
• 이 작업을 최대 n - 1 번 반복하면 정렬 완료 -> 시간복잡도 : O(n^2)
• ex) 3 4 1 5 2 를 정렬한다고 가정
  • 1번째 loop => 3 4 1 5 2 -> 3 1 4 5 2 -> 3 1 4 2 5 => 5 확정
  • 2번째 loop => 3 1 4 2 5 -> 1 3 4 2 5 -> 1 3 2 4 5 => 4 확정
  • 3번째 loop => 1 3 2 4 5 -> 1 2 3 4 5 => 3확정
  • 4번째 loop => 1 2 3 4 5 => 2확정, 1확정

2.2. 코드

for(int i = 0 ; i < n - 1 ; i ++) {
    boolean change = false;
    for(int j = 0 ; j < n - 1 - i ; j ++){
        if(arr[j] > arr[j + 1]) {
            change = true;
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
    if(change == false) break;
}

3. Selection Sort

3.1. 개념

• for문을 통해 가장 작은 값을 찾고, 맨 앞자리와 교환
• 다음 for문에선 맨 앞자리값을 제외한 값 중 가장 작은 값을 찾고, 두번째 앞자리와 교환
• 이 작업을 최대 n - 1 번 반복하면 정렬 완료 -> 시간복잡도 : O(n^2)
• ex) 3 4 1 5 2 를 정렬한다고 가정
  • 1번째 loop => 최소값 = 1 -> 1 4 3 5 2 => 1 확정
  • 2번째 loop => 최소값 = 2 -> 1 2 3 5 4 => 2 확정
  • 3번째 loop => 최소값 = 3 -> 1 2 3 5 4 => 3 확정
  • 4번째 loop => 최소값 = 4 -> 1 2 3 4 5 => 4확정, 5확정

3.2. 코드

for(int i = 0 ; i < n - 1 ; i ++) {
    int min_index = i;
    for(int j = i + 1 ; j < n ; j ++) {
        if(arr[min_index] > arr[j]) {
            min_index = j;
        }
    }
    int temp = arr[min_index];
    arr[min_index] = arr[i];
    arr[i] = temp;
}

4. Insertion Sort

4.1. 개념

• for문을 돌리면서 해당 index가 index 앞까지의 부분에서 삽입될 위치를 찾아 삽입
• 이 작업을 최대 n - 1 번 반복하면 정렬 완료 -> 시간복잡도 : O(n^2)
  • 삽입될 위치를 찾을때 이진탐색으로 탐색하면 시간복잡도를 줄일 수 있음
• ex) 3 4 1 5 2 를 정렬한다고 가정
  • 2번째 index = 4 -> 3 4 1 5 2
  • 3번째 index = 1 -> 1은 3, 4 보다 앞에 삽입되야 함 -> 1 3 4 5 2
  • 4번째 index = 5 -> 1 3 4 5 2
  • 5번째 index = 2 -> 2는 1과 3 사이에 삽입되야 함 -> 1 2 3 4 5

4.2. 코드

for(int i = 1 ; i < n ; i ++) {
    int temp = arr[i];
    for(int j = i ; j >= 0 ; j --) {
        if(j == 0) {
            arr[0] = temp;
        }else if(arr[j - 1] <= temp) {
            arr[j] = temp;
            break;
        } else {
            arr[j] = arr[j - 1];
        }
    }
}

5. Quick Sort

5.1. 개념

• pivot(기준점)을 정함 -> 아무기준으로 정해도 상관없음 -> 중간 지점을 기준점으로 지정하고 진행해봄
• quickSort(Start, End) 호출 -> 처음에는 Start = 0, End = n - 1
• Left는 Start에서 시작해 pivot보다 크거나 같은 수를 만날때까지 증가
• Rigth는 End에서 시작해 pivot보다 작거나 같은 수를 만날때까지 감소
• Left와 Right가 정해졌을 때
  • Left <= Right 이면 두 수를 바꾸고, Left 증가, Right 감소 후 다시 Left, Right를 증감하며 구함
  • Left > Right가 되었을 때
    • Right > Start이면 quickSort(Start, Right) 호출
    • Left < End이면 quickSort(Left, End) 호출 (구간 분리)
• 이 작업을 모든 분리된 구간의 길이가 1이 될 때 까지 진행 -> 정렬 완료
• 시간복잡도 : O(nlogn), 최악의 경우 : O(n^2)
• ex) 5 1 6 3 4 2 7 을 정렬한다고 가정
  • quickSort(0,6) => Start = 0, End = 6, pivot = arr[ (0 + 6) / 2 ] = arr[ 3 ] = 3
  • Left는 0에서 시작해서 3보다 큰 수를 만날때 까지 증가, 5를 만나면 멈춤 -> Left = 0
  • Right는 6에서 시작해서 3보다 작은 수를 만날때 까지 감소, 2를 만나면 멈춤 -> Right = 5
  • Left <= Right 이기 때문에 두 수를 바꾸면 2 1 6 3 4 5 7 이 되고, Left = 1, Right = 4 에서 다시 진행
  • Left는 1에서 시작해서 6을 만나면 멈춤 -> Left = 2
  • Right는 4에서 시작해서 3을 만나면 멈춤 -> Right = 3
  • Left <= Right 이기 때문에 두 수를 바꾸면 2 1 3 6 4 5 7 이 되고, Left = 3, Right = 2 에서 다시 진행
  • Left > Right 가 되었음 -> Start < Right, Left < End 임으로 quickSort(0,2), quickSort(3,6) 호출
    • quickSort(0,2) => Start = 0, End = 2, pivot = arr[ (0 + 2) / 2] = arr[ 1 ] = 1
    • Left는 0에서 시작해서 2를 만나면 멈춤 -> Left = 0
    • Right는 2에서 시작해서 1을 만나면 멈춤 -> Right = 1
    • Left <= Right 이기 때문에 두 수를 바꾸면 1 2 3 6 4 5 7 이 되고, Left = 1, Right = 0 에서 다시 진행
    • Left > Right 가 되었음 -> Start = Right, Left < End 임으로 quickSort(1,2)만 호출
      • quickSort(1,2) = > Start = 1, End = 2, pivot = arr[ (1 + 2) / 2 ] = arr [ 1 ] = 2
      • Left는 1에서 시작해서 2를 만나면 멈춤 -> Left = 1
      • Right는 2에서 시작해서 2를 만나면 멈춤 -> Right = 1
      • Left <= Right 이기 때문에 두 수를 바꾸면 1 2 3 6 4 5 7 이 되고, Left = 2, Right = 0 에서 다시 진행
      • Left > Right 가 되었음 -> Start > Right, Left = End 임으로 더 이상 호출 X
• 이 때의 결과값을 보면 1 2 3 6 4 5 7 인데, 이는 index 0~2 까지는 정렬된 것을 확인할 수 있음
• 마찬가지로 index 3~6까지도 다음과 같이 진행하면 index 0~6까지 모두 정렬 됨

5.2. 코드

public static void quickSort(int Start, int End) {
    if(Start >= End) { return; }

    int pivot = arr[ ( Start + End ) / 2 ];
     int Left = Start;
    int Right = End;

    while(Left <= Right) {
        while(arr[Left] < pivot) Left ++;
        while(arr[Right] > pivot) Right --;

        if(Left <= Right) {
            int temp = arr[Right];
            arr[Right] = arr[Left];
            arr[Left] = temp;
            Left ++;
            Right --;
        }
    }

    if(Start < Right) quickSort(Start, Right);
    if(Left < End) quickSort(Left, End);
}

5.3. 시간 단축 방법

• Quick Sort는 pivot이 어떻게 정해지느냐에 따라 시간복잡도가 달라짐
• n개의 pivot이 모두 가장 작은 수 혹은 가장 큰 수로 뽑혔을 때 가장 오랙 걸리고 이 때의 시간 복잡도가 O(n^2)
• 따라서 pivot을 정하는 방식이 중요할 수 있음
• 위에서 구현한 코드는 중앙의 pivot을 무작위로 정했었는데 이 방법이 아닌 처음, 중간, 끝 값 중 2번째로 큰 값으로 pivot을 정하는 방법, 3개의 구간을 나눠 중간값을 구하고 그 값의 중간값을 pivot을 정하는 방법 등이 있음

6. Merge Sort

6.1. 개념

• n개의 입력이 들어오면, n개의 그룹으로 나누고, 2개씩 그룹을 합치면서 동시에 정렬
• 1개의 그룹이 남을때 까지 반복하면 정렬 완료
• 시간복잡도 : O(nlogn)
• ex) 3 4 1 5 2 8 7 6 를 정렬한다고 가정
  • 8개 그룹 -> 3, 4, 1, 5, 2, 8, 7, 6
  • 4개 그룹 -> (3, 4), (1, 5), (2, 8), (6, 7)
  • 2개 그룹 -> (1, 3, 4, 5), (2, 6, 7, 8)
  • 1개 그룹 -> (1, 2, 3, 4, 5, 6, 7, 8)
• (1, 3, 4, 5) 그룹과 (2, 6, 7, 8) 그룹을 합치는 법
  1. 첫번째 그룹의 첫번째 숫자와 두번째 그룹의 첫번째 숫자를 비교했을 때, 1이 더 작음
  2. 합치는 그룹의 첫번째에는 1을 넣어줌
  3. 첫번째 그룹의 두번째 숫자와 두번째 그룹의 첫번째 숫자 비교 후 더 작은 숫자를 넣어줌
  4. 합치는 그룹의 두번째에는 2가 들어감
  5. 첫번째 그룹의 두번째 숫자와 두번째 그룹의 두번째 숫자 비교 후 더 작은 숫자를 넣어줌
  • 이런 식으로 그룹을 합침

6.2. 코드

public static void mergeSort(int Start, int End) {
    if(End - Start < 1) return;

    int Middle = ( End + Start ) / 2;
    mergeSort(Start, Middle);
    mergeSort(Middle + 1, End);

    for(int i = Start ; i <= End ; i ++) {
        temp[i] = arr[i];
    }
    int k = Start;
    int x = Start;
    int y = Middle + 1;
    while(x <= Middle && y <= End) {
        if(temp[x] < temp[y]) {
            arr[k ++] = temp[x ++];
        } else {
            arr[k ++] = temp[y ++];
        }
    }
    while(x <= Middle) {
        arr[k ++] = temp[x ++];
    }
    while(y <= End) {
        arr[k ++] = temp[y ++];
    }
}

7. Radix Sort

7.1. 개념

• 기수정렬은 입력되는 수의 개수가 많지만, 수의 범위가 적을때 사용하면 유용
• 10개의 Queue(FIFO)가 필요, 0~9번째 Queue라고 생각
• 처음에는 0번째 Queue에는 일의 자리가 0인숫자, 1번째 Queue에는 일의 자리가 1인 숫자, ... 이런 식으로 삽입
• 0번째 Queue부터 9번째 Queue까지 돌면서 순서대로 모두 poll해줌
• 다음에는 십의 자리 숫자 기준, 그 다음에는 백의 자리 숫자 기준 이런식으로 해줌
• 결과적으로 이 작업을 최대 k(최대 숫자의 자릿수)번 반복하면 정렬 완료
• 시간복잡도 : O(kn)
• ex) 195 10 5 7 25 61 255 36 4 를 정렬한다고 가정
  • 일의 자리 기준
    • 0번째 Queue : 10
    • 1번째 Queue : 61
    • 4번째 Queue : 4
    • 5번째 Queue : 195 5 25 255
    • 6번째 Queue : 36
    • 7번째 Queue : 7
    • 2, 3, 8, 9번째 Queue : 비어있음
  • Queue 순서대로 모두 poll 하면 10 61 4 195 5 25 255 36 7 이 됨
  • 십의 자리 기준으로 같은 작업을 마치고 나면 4 5 7 10 25 36 255 61 195
  • 백의 자리 기준으로 같은 작업을 마치고 나면 4 5 7 10 25 36 61 195 255
  • 정렬 완료

7.2. 코드

// 자리수 구하기
int max = 0, max_size = 1;
while(max >= 10) {
    max_size ++;
    max /= 10;
}

// Queue 배열 생성
LinkedList[] queues = new LinkedList[10];
for(int i = 0 ; i <= 9 ; i ++) {
    queues[i] = new LinkedList();
}

// 기수정렬
int t = 1, index;
for(int i = 1 ; i <= max_size ; i ++) {
    for(int j = 0 ; j < n ; j ++) {
        queues[ ( arr[j] / t ) % 10 ].add(arr[j]);
    }
    index = 0;
    for(int j = 0 ; j <= 9 ; j ++) {
        while(!queues[j].isEmpty()) {
            arr[index ++] = Integer.parseInt( queues[j].poll().toString() );
        }
    }
    t *= 10;
}

8. Arrays.sort()

8.1. 개념

• java.util.Arrays 클래스에서 제공하는 Method
• Dual Pivot QuickSort를 사용한 정렬 방식으로 보통 QuickSort보다 더 빠르지만, 최악의 경우 O(n^2)이 발생할 수 있음

8.2. 코드

Arrays.sort(arr);

9. Collections.sort()

9.1. 개념

• java.util.Collections 클래스에서 제공하는 Method
• TimeSort 라는 삽입정렬과 병합정렬을 결합한 정렬방식을 사용
• 시간복잡도는 평균, 최악의 상황에 상관없이 O(nlogn)을 갖음
• 대신 배열에서 사용할 수 없고, List, Map 등의 컬렉션 프레임워크의 구조에서 사용 가능

9.2. 코드

Collections.sort(numList);

10. Arrays.sort() : Index와 같이 정렬

• 코딩을 하게 되면 Arrays.sort()를 쓰는 상황이 매우 많음
• 만약 정렬을 해야되는데 정렬된 값이 정렬 전에 몇번째 index였는지 알아야 되는 상황이 발생할 수도 있음
• 이런 상황에서는 이 방법을 사용해 index와 값을 같이 묶어 정렬하면 됨

import java.util.Arrays;
import java.util.Scanner;

public class Test {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        myFormat[] arr = new myFormat[n];

        for(int i = 0 ; i < n ; i ++) {
            arr[i] = new myFormat(i, sc.nextInt());
        }
        Arrays.sort(arr);

        for(int i = 0 ; i < n ; i ++) {
            System.out.println(arr[i].value + " ( 정렬 전 index : " + arr[i].index + ")");
        }
    }

    public static class myFormat implements Comparable<myFormat> {
        int index, value;

        public myFormat(int index, int value) {
            this.index = index;
            this.value = value;
        }

        @Override
        public int compareTo(myFormat o) {
            return this.value - o.value;
        }
    }
}

10.1. 결과

5
1 4 3 2 5
1 ( 정렬 전 index : 0)
2 ( 정렬 전 index : 3)
3 ( 정렬 전 index : 2)
4 ( 정렬 전 index : 1)
5 ( 정렬 전 index : 4)