Bubble Sort, Selection Sort, Insertion Sort: 알고리즘 비교

Bubble Sort, Selection Sort, Insertion Sort: 알고리즘 비교

컴퓨터 과학에서 정렬 알고리즘은 데이터를 순서대로 배열하는 방법을 의미합니다. 여러 종류의 정렬 알고리즘이 존재하지만, 그 중에서도 버블 정렬(Bubble Sort), 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort)은 가장 기본적인 정렬 알고리즘으로 자주 다뤄집니다. 이 세 가지 알고리즘은 모두 비교 기반의 정렬 방식이며, 그 동작 방식에 차이가 있습니다.

이번 글에서는 버블 정렬, 선택 정렬, 삽입 정렬의 동작 원리와 성능을 비교해보겠습니다.

---

1. Bubble Sort (버블 정렬)

동작 원리

버블 정렬은 리스트의 인접한 두 원소를 비교하여, 크기가 더 큰 원소를 뒤로 보내는 방식입니다. 이 과정을 리스트 끝까지 반복하면서 점차 가장 큰 원소가 맨 뒤로 "버블"처럼 떠오릅니다. 이런 방식으로 정렬이 이루어집니다.

• 최소 1회 반복: 첫 번째 비교 후, 가장 큰 값이 맨 뒤로 이동
• 시간 복잡도: O(n^2)

알고리즘 흐름

1. 리스트의 첫 번째 원소부터 마지막 원소까지 인접한 두 원소를 비교합니다.
2. 큰 원소를 뒤로 보냅니다.
3. 한 번의 반복이 끝나면, 가장 큰 원소가 맨 뒤에 위치하게 됩니다.
4. 이 과정을 리스트 크기만큼 반복합니다.

장점

• 구현이 매우 간단합니다.

단점

• 성능이 매우 비효율적입니다. 최악의 경우에도 O(n^2)의 시간 복잡도를 가집니다.

---

2. Selection Sort (선택 정렬)

동작 원리

선택 정렬은 주어진 리스트에서 최소값 또는 최대값을 선택하여 그 값을 맨 앞에 놓는 방식입니다. 이 과정을 리스트의 끝까지 반복하면서 점차 정렬된 구간이 늘어납니다.

• 최소값을 선택하여 맨 앞에 두는 방식으로, 각 순회마다 가장 작은 값을 찾아낸 후 그것을 올바른 위치에 배치합니다.
• 시간 복잡도: O(n^2)

알고리즘 흐름

1. 리스트에서 가장 작은 원소를 찾아서 맨 앞에 놓습니다.
2. 두 번째로 작은 원소를 찾아서 두 번째 위치에 놓습니다.
3. 이 과정을 반복하여, 모든 원소가 정렬될 때까지 계속합니다.

장점

• 불필요한 교환을 줄일 수 있습니다.
• 구현이 간단하고 직관적입니다.

단점

• 여전히 O(n^2) 복잡도를 가지기 때문에, 대량의 데이터를 처리할 때 비효율적입니다.

---

3. Insertion Sort (삽입 정렬)

동작 원리

삽입 정렬은 정렬된 부분 리스트에 새로운 원소를 삽입하는 방식입니다. 정렬된 리스트에 새로운 원소를 적절한 위치에 삽입하여, 리스트가 점차 정렬되는 방식입니다.

• 시간 복잡도: 최악의 경우 O(n^2), 최선의 경우 O(n) (이미 정렬되어 있을 때)

알고리즘 흐름

1. 두 번째 원소부터 시작하여, 각 원소를 정렬된 부분 리스트와 비교합니다.
2. 적절한 위치를 찾아 원소를 삽입합니다.
3. 이 과정을 리스트의 끝까지 반복합니다.

장점

• 이미 정렬된 리스트나 거의 정렬된 리스트에서 효율적입니다.
• O(n)의 시간 복잡도를 가질 수 있습니다.

단점

• 최악의 경우 O(n^2)로 비효율적입니다.

---

성능 비교

알고리즘 평균 시간 복잡도 최악 시간 복잡도 공간 복잡도 설명

버블 정렬	O(n^2)	O(n^2)	O(1)	가장 큰 값을 맨 뒤로 보내며 정렬
선택 정렬	O(n^2)	O(n^2)	O(1)	가장 작은 값을 선택해 맨 앞에 배치
삽입 정렬	O(n^2)	O(n^2)	O(1)	정렬된 부분에 원소를 삽입하며 정렬

---

정리

• 버블 정렬: 직관적이고 간단한 구현, 하지만 비효율적입니다.
• 선택 정렬: 버블 정렬보다는 조금 더 효율적이지만, 여전히 O(n^2)의 시간 복잡도를 가집니다.
• 삽입 정렬: 이미 정렬된 리스트에 대해서는 효율적이며, 일부 데이터에서는 O(n) 시간이 걸릴 수 있습니다.

이 세 가지 정렬 알고리즘은 모두 간단한 정렬 방식으로 학습용으로 유용하지만, 실제로 대량의 데이터를 처리할 때는 퀵 정렬이나 병합 정렬처럼 더 효율적인 알고리즘을 사용하는 것이 좋습니다.

---

참고 문헌

• 위키백과 - 버블 정렬
• 위키백과 - 선택 정렬
• 위키백과 - 삽입 정렬

 

---

1. Bubble Sort (버블 정렬)

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap arr[j] and arr[j + 1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("Sorted array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

2. Selection Sort (선택 정렬)

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("Sorted array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

3. Insertion Sort (삽입 정렬)

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        insertionSort(arr);
        System.out.println("Sorted array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

---

각 코드 설명

버블 정렬 (Bubble Sort)

시간 복잡도: O(n^2)

동작 원리: 두 원소를 비교하고, 큰 값을 뒤로 보내는 과정을 반복하여 리스트를 정렬합니다.

 

선택 정렬 (Selection Sort)

시간 복잡도: O(n^2)

동작 원리: 각 순회마다 최소값을 찾아 맨 앞에 배치하는 방식으로 정렬합니다.

 

삽입 정렬 (Insertion Sort)

시간 복잡도: 최선의 경우 O(n), 최악의 경우 O(n^2)

동작 원리: 정렬된 부분에 새로운 원소를 삽입하여 점진적으로 리스트를 정렬합니다.

---

이 코드들은 각 알고리즘의 기본적인 구현을 보여줍니다. 예제 배열을 정렬한 뒤 결과를 출력합니다. 각 알고리즘의 시간 복잡도를 고려하여, 작은 배열에서는 차이를 크게 느끼기 어렵지만, 큰 배열에서는 성능 차이가 뚜렷하게 나타날 것입니다.