정렬 알고리즘

1. 버블 정렬

버블 정렬은 가장 기본적인 알고리즘 중 하나로 인접한 모든 값을 비교해서 작은 값이 앞으로 이동하도록 교환하는 알고리즘이다. 모든 값을 비교하기 때문에 데이터가 많을수록 처리시간이 오래걸리는 단점이 있다.

버블 정렬 구현예제

public class BubbleSort {
    public static void main(String[] args) {
        int[] a = {10, 3, 1, 4, 2};

        // 시작 위치를 하나씩 뒤로 하는 반복
        for (int i = 0; i < a.length - 1; i++) {
            // 시작 위치를 하나씩 앞으로 하는 반복
            for (int j = a.length - 1; j > i; j--) {
                // 만약 인접한 두 값 중 뒤쪽 값이 더 작다면 값 교환
                if (a[j] < a[j - 1]) {
                    int temp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = temp;
                }
            }
        }
        for (int i : a) {
            System.out.print(i + " "); // 1 2 3 4 10
        }
    }
}

2. 선택 정렬

선택 정렬은 최솟값을 찾아 앞에서부터 차례대로 나열하는 알고리즘이다. 버블 정렬과 비슷하지만 최솟값을 찾고 나서 교환하기 때문에 교환 횟수가 적고 처리속도도 약간 빠르다.

선택 정렬 구현예제

public class SelectionSort {
    public static void main(String[] args) {
        int[] a = {10, 3, 1, 4, 2};
        // 최솟값을 넣을 위치를 앞에서부터 차례대로 반복
        for (int i = 0; i < a.length - 1; i++) {
            // 1. 최솟값을 구하는 알고리즘
            // 임시 최솟값과 위치
            int min = a[i];
            int k = i;
            // 마지막 값까지 임시 최솟값과 비교
            for (int j = i + 1; j < a.length; j++) {
                // 만약 임시 최솟값보다 작은 최솟값을 찾았다면
                // 최솟값과 위치 저장
                if (min > a[j]) {
                    min = a[j];
                    k = j;
                }
            }
            // 2. 교환 알고리즘
            // 임시 최솟값과 최솟값 교환
            int temp = a[i];
            a[i] = a[k];
            a[k] = temp;
        }
        for (int i : a) {
            System.out.print(i + " ");
        }
    }
}

3. 삽입 정렬

삽입 정렬은 데이터를 빼내 올바른 위치에 삽입하는 알고리즘으로 버블, 선택 정렬 중 가장 빠르다는 특징이 있다. 정렬되지 않은 부분에서 삽입할 값을 차례로 하나씩 꺼내서 정렬된 부분의 어느 곳에 삽입할지 조사하는 반복을 수행하며 정렬한다.

삽입 정렬 구현예제

public class InsertSort {
    public static void main(String[] args) {
        int[] a = {10, 3, 1, 4, 2};
        // 정렬되지 않은 부분에서 차례대로 하나씩 꺼내기 반복
        for (int i = 1; i < a.length; i++) {
            // 삽입할 값 임시로 temp에 저장
            int temp = a[i];
            // 삽입할 위치 변수 초기화
            int ins = 0;
            // 값을 어디에 삽입할지 뒤에서부터 차례대로 탐색
            for (int j = i - 1; j >= 0; j--) {
                // 만약 삽입할 값이 정렬되어 있는 부분의 값보다 작다면
                if (a[j] > temp) {
                    // 해당 위치에 값을 삽입할 수 있도록 배열을 하나씩 뒤로 보냄
                    a[j + 1] = a[j];
                    // 만약 삽입할 값이 정렬되어 있는 부분의 값보다 크다면
                } else {
                    // 삽입할 위치를 ins에 저장 후 반복 종료
                    ins = j + 1;
                    break;
                }
            }
            // 밀어내는 처리 종료 후 끝난 위치에 값 삽입
            a[ins] = temp;
        }
        for (int i : a) {
            System.out.print(i + " ");
        }
    }
}

4. 퀵 정렬

앞서 소개한 세 가지 알고리즘은 O(N^2)의 시간 복잡도를 가져 비효율적이다. 이번에 소개할 퀵 정렬은 가장 빠른 정렬 알고리즘으로 O(nlogn)을 갖는다.

1. 배열의 한 가운데 있는 값(=pivot)을 기준으로 두 개의 대소 그룹으로 나눈다.
2. 왼쪽에서 피벗보다 큰 값을 찾고 오른쪽에서 피벗보다 작은 값을 찾아 두 값을 교환한다.
3. 나눈 그룹안에서 같은 처리를 재귀적으로 반복한다.

퀵 정렬 구현예제

public class QuickSort {
    public static void main(String[] args) {
        int[] a = {10, 3, 1, 9, 7, 6, 8, 2, 4, 5};
        quickSort(a, 0, a.length - 1);
        for (int i : a) {
            System.out.print(i + " ");
        }
    }

    public static void quickSort(int[] a, int start, int end) {
        // 범위 한가운데에 있는 값을 피벗으로 선언
        int pivot = a[(int) (start + end) / 2];
        // 왼쪽 위치를 시작 위치로 선언
        int left = start;
        // 오른족 위치를 종료 위치로 선언
        int right = end;
        while (true) {
            // 왼쪽 값이 피벗보다 작다면
            while (a[left] < pivot) {
                // 왼쪽을 오른쪽으로 한 칸 이동
                left++;
            }
            // 오른쪽 값이 피벗보다 크다면
            while (pivot < a[right]) {
                // 오른쪽을 왼쪽으로 한 칸 이동
                right--;
            }
            // 만약 왼쪽과 오른쪽이 만나면 반복종료
            if (right <= left) {
                break;
            }
            // 교환 알고리즘
            // 왼쪽과 오른쪽이 만나지 않는다면 왼쪽 값과 오른쪽 값 교환
            int temp = a[left];
            a[left] = a[right];
            a[right] = temp;
            // 왼쪽을 오른쪽으로 한 칸 이동
            left++;
            // 오른쪽을 왼쪽으로 한 칸 이동
            right--;
        }
        // 만약 왼쪽에 나눌 데이터가 있다면
        if (start < left - 1) {
            // 재귀
            quickSort(a, start, left - 1);
        }
        // 만약 오른쪽에 나눌 데이터가 있다면
        if (right + 1 < end) {
            // 재귀
            quickSort(a, right + 1, end);
        }
    }
}

출처

• 즐겁게 배우는 알고리즘과 프로그래밍 도감 - 모리 요시나오, 마쓰무라 마키오 지음