정렬 알고리즘

정렬(Sorting)

데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미한다. 정렬 알고리즘은 엄청 다양하지만 보통 사용하는 알고리즘중에는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 등이 있다. 그리고 자바에는 배열의 정렬을 제공하는 라이브러리와 컬렉션 프레임워크에서도 적용할 수 있는 정렬 라이브러리가 있어서 같이 활용해도 좋다.

배열의 정렬 라이브러리

int[] arr = new int[]{3,2,1,5,4};

Arrays.sort(arr);

for(int a: arr){
	System.out.print(a + " ");	//1 2 3 4 5
}

ArrayList 정렬 라이브러리

import java.util.*;

ArrayList<Integer> list = new ArrayList<>();
list.add(3);
list.add(2);
list.add(1);
list.add(5);
list.add(4);

Collections.sort(list);

for(Integer l: list){
	System.out.println(l + " ");	//1 2 3 4 5
}

선택 정렬

선택 정렬 동작원리

1. 데이터가 무작위로 배열이나 리스트에 있다고 가정한다.
2. 데이터 중 가장 작은 데이터를 선택해서 맨 앞의 데이터와 바꾼다.
3. 그다음 두번째 작은 데이터를 선택해서 맨 앞에서 두번째 데이터와 바꾼다.
4. 이 순서를 반복한다.

        int[] arr = new int[]{2,4,9,8,1,6,5,7,3};

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

        for(int a: arr){
            System.out.print(a + " ");	//1 2 3 4 5 6 7 8 9
        }

선택 정렬의 시간 복잡도

빅오 표기법으로 O(N^2) 으로 표현할 수 있다. 2중 반복문이 사용되었으므로 시간 복잡도가 상당히 높다. 따라서 선택 정렬은 기본 라이브러리보다 시간 복잡도가 매우 클 것이라고 예상할 수 있다.

삽입 정렬

선택 정렬은 알고리즘 문제 풀이에 사용하기에는 느린 편이다. 삽입 정렬은 선택 정렬보다 알고리즘 구현 난이도가 높은 편이지만 선택 정렬에 비해서 시간 측면에서 효율이 높은편이다. 삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬이 되었을 때 시간적으로 효율적이다. 삽입 정렬은 특정 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬이라고 부른다.

삽입 정렬 동작원리

1. 삽입 정렬은 두번째 데이터부터 시작한다. 따라서 두번째 데이터가 첫번째 데이터와 비교되어 첫번째 데이터의 왼쪽, 오른쪽 중 어디로 들어갈 까 판단한다.
2. 다음 세번째 데이터를 본다. 세번째 데이터는 두번째와 세번째 데이터와 비교되어 어디 위치에 들어갈까 판단하여 삽입된다.
3. 이를 반복한다.

        int[] arr = new int[]{2,4,9,8,1,6,5,7,3};

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

        for(int a: arr){
            System.out.print(a + " ");	//1 2 3 4 5 6 7 8 9
        }

삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도는 선택 정렬과 마찬가지로 O(N^2) 인데 선택 정렬과 시간 효율이 같다고 생각할 수도 있다. 그러나 삽입 정렬은 데이터가 거의 정렬되면 될수록 시간 복잡도가 낮아져서 선택 정렬 알고리즘보다 더 효율적인 알고리즘이라고 할 수 있다.

퀵 정렬

퀵 정렬은 가장 많이 사용하는 알고리즘이다. 퀵 정렬은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이기도 하다. 퀵 정렬은 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방식의 원리를 이용한다.

퀵 정렬 동작원리

1. 리스트의 첫 번째 데이터를 피벗으로 설정한다.
2. 피벗을 제외한 리스트의 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 리스트의 오른쪽에서부터 피벗보다 작은 데이터를 찾아서 두 데이터의 위치를 바꾼다.
3. 데이터를 찾다가 피벗보다 큰 데이터의 위치보다 작은 데이터의 위치가 왼쪽에 있다면 작은 데이터와 피벗의 위치를 바꾼다.
4. 이제 엇갈린 부분이 기준이 되어서 왼쪽부분과 오른쪽 부분만 다시 퀵 정렬을 수행하면 되므로 각각 퀵 정렬을 반복 수행한다.

public class Main {

    public static int[] arr= new int[]{2,4,9,8,1,6,5,7,3};

    public static void quickSort(int start, int end){
        if(start >= end) return;    //원소가 한개인 경우 종료
        int pivot = start;
        int left = start + 1;
        int right = end;
        //왼쪽 탐색부분이 오른쪽 탐색 부분을 넘어가면 종료
        while(left <= right){
            //피벗보다 큰 데이터를 찾을 때 까지 반복
            while(left <= end && arr[left] <= arr[pivot]) left++;
            //피벗보다 작은 데이터를 찾을 때 까지 반복
            while(right > start && arr[right] >= arr[pivot]) right--;
            //left 와 right 가 엇갈리면
            if(left > right){
                int temp = arr[right];
                arr[right] = arr[pivot];
                arr[pivot] = temp;
            }
            //엇갈리지 않았다면
            else {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
            //왼쪽 오른쪽 부분 다시 수행
            quickSort(start, right - 1);
            quickSort(right + 1, end);
        }


    }

    public static void main(String[] args) {

        quickSort(0,arr.length - 1);

        for(int a: arr){
            System.out.print(a + " ");	//1 2 3 4 5 6 7 8 9
        }
    }

}

퀵 정렬의 시간 복잡도

퀵 정렬의 평균 시간 복잡도는 O(NlogN)이다. 앞의 선택 정렬과 삽입 정렬에 비해 매우 빠른 알고리즘이다. 실제로 알고리즘을 짤 때 처리해야 할 데이터가 많을 경우에는 퀵 정렬을 사용하는 것이 효율적일 것 이다.

계수 정렬

계수 정렬 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 알고리즘이다. 계수 정렬은 데이터의 크기 범위가 제한 되어 정수 형태로 표현할 수 있을 때만 사용할 수 있다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1000000 을 넘지 않을 때 효과적으로 사용할 수 있다.

계수 정렬 동작원리

1. 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 배열을 생성한다.
2. 주어진 배열을 한바퀴 돌면서 생성한 배열의 값을 요소의 갯수만큼 올린다.

동작 원리를 말로 설명하기 힘드니 코드로 바로 보여주면 다음과 같다.

public class Main {

    public static int[] arr= new int[]{7,5,9,0,3,1,6,2,9,1,4,8,0,5,2};

    public static void main(String[] args) {
        int[] check = new int[10];

        for(int i = 0; i < arr.length; i++){
            check[arr[i]] += 1;
        }

        for(int i = 0; i < check.length; i++){
            for(int j = 0; j < check[i]; j++){
                System.out.print(i + " ");
            }
        }
    }

}

계수 정렬의 시간 복잡도

모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N+K)이다.