정렬 알고리즘(Sorting Algorithm)

이동엽·2023년 9월 11일

자료구조 및 알고리즘 / 자바

목록 보기
18/21

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. 각 정렬 알고리즘 설명

1. Bubble Sort (버블 정렬)

순서대로 근접한 두 수를 비교해서 오른쪽 수가 왼쪽 수보다 더 작으면 교환한다.
이 작업을 한 번 수행 할때마다 맨 끝자리에 가장 큰 수가 가게 된다.
이 작업을 최대 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확정

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;
}

2. Selection Sort(선택 정렬)

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확정

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;
}

3. Insertion Sort(삽입 정렬)

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

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];
        }
    }
}

4. Quick Sort(퀵 정렬)

pivot(기준점)을 정한다. 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이 될 때 까지 진행한다. 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까지 모두 정렬 된다

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);
}

Quick Sort 시간 단축 방법

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

아래의 그림은 다른 예시로 Quick Sort를 하는 것을 나타냈다.





5. Merge Sort(병합 정렬)

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가 들어감
  • 첫번째 그룹의 두번째 숫자와 두번째 그룹의 두번째 숫자 비교 후 더 작은 숫자를 넣어줌
    이런 식으로 그룹을 합침
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 ++];
    }
}

6. Radix Sort(기수 정렬)

기수정렬은 입력되는 수의 개수가 많지만, 수의 범위가 적을때 사용하면 유용하다.
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
정렬 완료

// 자리수 구하기
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;
}

7. Arrays.sort()

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

Arrays.sort(arr);

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;
        }
    }
}

/* 출력
5
1 4 3 2 5
1 ( 정렬 전 index : 0)
2 ( 정렬 전 index : 3)
3 ( 정렬 전 index : 2)
4 ( 정렬 전 index : 1)
5 ( 정렬 전 index : 4)
*/

8. Collections.sort()

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

Collections.sort(numList);
profile
이동엽
이전 포스트

해시셋(Hash Set)

다음 포스트

분할 정복(Divide and Conquer)

0개의 댓글