[정렬 연습] 버블 정렬과 선택 정렬의 원리 및 구현 - Java

버블 정렬이란?

버블 정렬은 정렬 알고리즘 중에서 가장 원시적인 방법으로서 주어진 데이터들을 순회하면서 서로 붙어있는 2개의 데이터씩 비교해, 하나씩 맨 뒤에 차곡차곡 옮겨놓는 방식으로 정렬한다.

 

그림으로 버블 정렬의 원리 이해하기

아래와 같이 최초 정렬되지 않은 크기 10의 정수형 배열이 있다고 가정했을 때, 버블 정렬을 통해 오름차순으로 정렬해보자.

 

 

우선 맨 앞에서부터 서로 붙어있는 2개의 데이터씩 비교를 하는데, 작은 값을 왼쪽에 큰 값을 오른쪽에 옮겨나가면서 배열을 순회한다. 이때 순회의 마지막 지점에서 이루어지는 비교는 주어진 배열에서 가장 큰 값을 배열 맨 뒤에 옮겨놓는 것이 된다.

 

즉, 맨 마지막 요소는 정렬이 되었다고 볼 수 있으므로 맨 마지막 인덱스 직전까지 앞선 작업들을 반복해나간다.

 

 

이처럼 버블 정렬은 주어진 데이터들이 오른쪽에서 왼쪽으로 차근차근 정렬된다.

 

 

자바로 버블 정렬 구현하기

앞선 원리를 적용해 버블 정렬을 자바로 구현해보면 다음과 같다.

 

import java.util.Arrays;

public class BubbleSort {

    public static void bubbleSort(int[] array) {
        for (int i = array.length; i > 1; i--) { // i = 1이면 2개 비교가 불가능 하닌까 제외
            for (int j = 1; j < i; j++) {
                if (array[j - 1] > array[j]) {
                    swap(array, j - 1, j);
                }
            }
        }
    }

    private static void swap(int[] array, int i, int minIndex) {
        int temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
}

 

위 소스 코드는 2중 for문으로 버블 정렬을 구현했는데, 재귀 함수를 이용해서도 버블 정렬을 구현할 수 있다.

 

import java.util.Arrays;

public class BubbleSort {

    public static void recursiveBubbleSort(int[] array) {
        recursiveBubbleSort(array, array.length);
    }

    private static void recursiveBubbleSort(int[] array, int i) {
        if (i > 1) {
            for (int j = 1; j < i; j++) {
                if (array[j - 1] > array[j]) {
                    swap(array, j - 1, j);
                }
            }
            recursiveBubbleSort(array, i - 1);
        }
    }

    private static void swap(int[] array, int i, int minIndex) {
        int temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
}

 

 

선택 정렬이란?

선택 정렬 역시 버블 정렬과 마찬가지로 원시적인 방법으로서 주어진 데이터들을 순회하면서 가장 작은 것을 선택해, 하나씩 맨 앞에 차곡차곡 옮겨놓는 방식으로 정렬한다.

 

그림으로 선택 정렬의 원리 이해하기

아래와 같이 최초 정렬되지 않은 크기 10의 정수형 배열이 있다고 가정했을 때, 선택 정렬을 통해 오름차순으로 정렬해보자.

 

 

선택 정렬은 가장 작은 것을 선택해 맨 앞에 옮겨 놓는다고 했다. 하지만 처음에는 가장 작은 것을 모르므로, 우선 맨 앞에 있는 값(7)을 선택해 이를 기준으로 배열의 나머지 요소(element)들을 순회하면서 가장 작은 값을 찾도록 한다.

 

 

이때, 7을 기준으로 이후의 배열 요소들에서 1이 가장 작은 값으로, 1을 선택해 맨 앞(7의 위치)으로 옮겨주고, 7을 1이 있던 자리로 옮겨준다. 이때 전체 배열에서 가장 작은 값이 선택되어 맨 앞으로 옮겨졌으므로 맨 앞에 요소는 정렬이 되었다고 볼 수 있다.

 

 

이번엔 맨 앞에서 두 번째 값을 선택해 이를 기준으로 다시 배열의 나머지 요소를 순회하면서 가장 작은 값을 찾아 마찬가지로 자리를 바꿔준다.

 

 

이러한 작업을 계속 반복하면 최종적으로 마지막 데이터를 선택하게 되는데, 그 이후로는 더이상 순회할 배열 요소가 없다. 하지만 이미 앞선 작업들로 인해 앞선 데이터들은 모두 오름차순으로 정렬되었고 마지막에 선택된 데이터가 가장 큰 값이 남게 되므로, 그대로 작업을 종료한다. 따라서 마지막 데이터를 굳이 선택할 필요도 없다.

 

 

이처럼 선택 정렬 수행 시 각각의 순회 작업으로 주어진 데이터들이 왼쪽에서 오른쪽으로 차근차근 정렬된다.

 

 

자바로 선택 정렬 구현하기

앞선 원리를 적용해 선택 정렬을 자바로 구현해보면 다음과 같다.

 

import java.util.Arrays;

public class SelectionSort {

    public static void selectionSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) { // 마지막 데이터는 선택할 필요가 없다.
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) { // 선택한 데이터 이후의 데이터들을 순회한다.
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            swap(array, i, minIndex);
        }
    }

    private static void swap(int[] array, int i, int minIndex) {
        int temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
}

 

버블 정렬과 마찬가지로 선택 정렬 역시 재귀 함수를 이용하여 구현할 수도 있다.

 

import java.util.Arrays;

public class SelectionSort {

    public static void recursiveSelectionSort(int[] array) {
        recursiveSelectionSort(array, 0);
    }

    private static void recursiveSelectionSort(int[] array, int i) {
        if (i < array.length - 1) { // 마지막 데이터는 선택할 필요가 없다.
            int minIndex = i;

            for (int j = i + 1; j < array.length; j++) { // 선택한 데이터 이후의 데이터들을 순회한다.
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            swap(array, i, minIndex);
            recursiveSelectionSort(array, i + 1);
        }
    }

    private static void swap(int[] array, int i, int minIndex) {
        int temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
}

 

 

버블 정렬과 선택 정렬 비교

시간 복잡도

지금까지 다루었던 버블 정렬과 선택 정렬의 시간 복잡도를 알아보자. 참고로 2중 for문으로 구현하든 재귀 함수로 구현하든 시간 복잡도는 동일하다.

 

주어진 데이터의 크기가 N이라고 할 때, 버블 정렬과 선택 정렬은 모두 공통적으로 주어진 데이터들을 순회하는 작업을 N - 1번 반복한다. 이때 순회 작업을 마칠 때마다 다음에 순회할 요소는 하나씩 줄어 총 연산 횟수는 (N - 1) + (N - 2) + (N - 3) + ... + 1 라고 볼 수 있다. 이를 수식으로 나타내면, (N - 1) * N / 2 로 나타낼 수 있는데, 이를 빅오 표기법으로 나타내면 O(N^2)으로 나타낼 수 있다.

 

결론적으로 버블 정렬과 선택 정렬의 시간 복잡도는 모두 O(N^2)이다.

 

시간 성능 비교

빅오 표기법 상의 시간 복잡도는 같지만 사실 시간 성능은 버블 정렬 보다 선택 정렬이 조금 더 낫다. 왜냐하면 선택 정렬은 순회 시 각각의 요소를 비교하며 최소 값인 인덱스를 찾고 swap은 순회 마지막에 한 번 일어나는 반면, 버블 정렬은 순회 시 두 개의 요소를 비교하여 if문 조건이 true일 때마다 swap을 한다.

 

(왼쪽) 선택 정렬, (오른쪽) 버블 정렬

단순히 인덱스를 찾는 것 보다는 swap을 하는 게 비용이 크므로, 똑같은 데이터를 정렬하더라도 선택 정렬과 버블 정렬은 다른 시간 성능을 보인다.

 

3만개의 무작위 정수 데이터를 선택 정렬과 버블 정렬로 각각 정렬했을 때 실행되는 시간은 다음과 같았다.

 

        // 3만개의 무작위 정수 데이터
        int[] array = new int[30000];
        Random random = new Random(1000);
        for (int i = 0; i < 30000; i++) {
            array[i] = random.nextInt(1000);
        }

 

실행 결과

 

빅오 표기법 상의 시간 복잡도는 O(N^2)로 같지만 선택 정렬이 버블 정렬보다 확연히 시간 성능이 낫다는 것을 확인할 수 있다.

 

버블 정렬과 선택 정렬은 모두 비효율적인 방법

버블 정렬과 선택 정렬은 나름대로 직관적이고, 이해하기 쉬운 정렬 방식이다. 하지만 기존 데이터가 정렬되어 있든 정렬되어있지 않든 항상 정해진 방식대로 데이터들을 순회하는 등 비효율적이라는 단점이 있다.

 

 

참고자료

• 한빛 미디어 출판 "이것이 취업을 위한 코딩테스트다"
• 유튜브 엔지니어대한민국