정렬 알고리즘(Sort Algorithm)정리[JAVA]

시간 복잡도(Time Complexity)

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)

- 최악의 경우에는 병합정렬이 빠르지만, 보통의 경우에는 퀵정렬이 빠르며, 병합 정렬은 메모리를 더 많이 차지한다.

- 여기서는 기수정렬은 다루지 않겠다.

 

Bubble Sort

• - 순서대로 근접한 두 수를 비교해서 오른쪽 수가 왼쪽보다 작으면 교환
• - 작업을 최대 n-1번 반복하면 정렬이 완료된다 -> 시간복잡도 O(n^2)

 

코드

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

 

Selection Sort

• - 가장 작은 값을 찾고, 맨 앞자리를 찾으면서 정렬
• - 작업을 최대 n-1 번 반복하면 정렬이 완료된다. -> 시간복잡도 O(n^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;
}

 

 

Insertion Sort

• - 반복문을 돌리면서 해당 index가 index 앞까지의 부분에서 삽입될 위치를 찾아 삽입
• - 작업을 최대 n-1 번 반복하면 정렬이 완료된다. -> 시간복잡도 O(n^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];
        }
    }
}

 

 

Quick Sort

• 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까지 모두 정렬 됨

코드

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

 

Merge Sort

• n개의 입력이 들어오면 , n개의 그룹으로 나누고, 2개씩 그룹을 합치면서 동시에 정렬 -> 2way merge sort
• 1개의 그룹이 남을때 까지 반복하면 정렬 완료
• 시간복잡도 : O(nlogn)

 

코드

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

 

Arrays.sort()

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

보통 입력수가 적은경우에 사용하며,

Arrays.sort(arr)

와 같은 형태로 쓰면 오름차순이 된다.

 

내림차순을 하고싶으면

Arrays.sort(arr, Collections.reverseOrder());

 식으로 하면 된다.

 

 

아래는 Arrays.sort를 이용한 정말간단한 문제이다.

(Baekjoon 2750)

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int arr[] = new int[N];

        for(int i=0;i<N;i++)
        {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);

        for(int i=0;i<N;i++)
        {
            System.out.println(arr[i]);
        }

    }
}

 

 

Collections.sort()

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

보통 시간초과를 고려한 문제에서 사용하며, 나도 백준 문제를 풀면서 알게된 함수이다. Collections.sort인 이유가 추측하건데, 자바에서Collection framework(List, Set, Map등)을 이용한 정렬이라서 Collections.sort인것 같다.

 

문제를 봐보면,

Baekjoon 2751

Arrays.sort 문제랑 같아보이지만 입력범위가 훨씬 크기때문에 시간초과를 고려해야하며, 배열이 아닌 컬렉션 프레임워크의 구조에서 사용이 가능하므로 코드를 보면

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer> list = new ArrayList<>();

        for(int i=0;i<N;i++)
        {
            list.add(Integer.parseInt(br.readLine()));
        }
        Collections.sort(list);

        for(int i : list)
        {
            sb.append(i).append('\n');
        }
        System.out.println(sb);

    }
}

와같이 조금더 신경써주어야 할 부분들이 있다.