정렬 알고리즘 - 버블 정렬 (Bubble sort)

 

 

버블 정렬 (Bubble sort) 이란?

 

 

버블 정렬은 간단하고 직관적인 정렬 알고리즘 중 하나로, 인접한 두 원소를 비교하여 필요에 따라 위치를 교환하여 정렬하는 방식입니다. 이 알고리즘은 이름 그대로, 가장 큰(또는 작은) 원소가 "거품"처럼 계속해서 위로 올라가는 모습을 닮았기 때문에 '버블' 정렬이라고 불립니다.

 

버블 정렬은 아래와 같은 과정을 거칩니다:

1. 리스트의 첫 번째 원소부터 시작하여 인접한 두 원소를 비교합니다.
2. 인접한 원소가 순서에 맞지 않으면 위치를 교환합니다.
3. 리스트의 끝까지 도달할 때까지 위 과정을 반복합니다.
4. 위 과정을 한 번 수행할 때마다 가장 큰(또는 작은) 원소가 마지막으로 이동하므로, 정렬된 부분을 제외하고 다시 처음부터 반복합니다.

 

 

버블 정렬 코드 예시 (C#)

 

아래 코드는 C#으로 작성된 버블 정렬 알고리즘의 예시입니다. 입력된 배열 {64, 34, 25, 12, 22, 11, 90}을 버블 정렬 알고리즘을 사용하여 오름차순으로 정렬한 결과를 출력합니다.

 

using System;

class BubbleSort {
    static void Bubble_Sort(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;
                }
            }

            // Print intermediate result
            Console.Write("Iteration " + (i + 1) + ": ");
            foreach (int num in arr) {
                Console.Write(num + " ");
            }
            Console.WriteLine();
        }
    }

    static void Main() {
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
        Console.WriteLine("Original array:");
        foreach (int num in arr) {
            Console.Write(num + " ");
        }
        Console.WriteLine();

        Bubble_Sort(arr);

        Console.WriteLine("Sorted array:");
        foreach (int num in arr) {
            Console.Write(num + " ");
        }
    }
}

 

 

위 코드를 실행한 결과는 다음과 같습니다:

 

Original array:
64 34 25 12 22 11 90 
Iteration 1: 34 25 12 22 11 64 90 
Iteration 2: 25 12 22 11 34 64 90 
Iteration 3: 12 22 11 25 34 64 90 
Iteration 4: 12 11 22 25 34 64 90 
Iteration 5: 11 12 22 25 34 64 90 
Iteration 6: 11 12 22 25 34 64 90 
Sorted array:
11 12 22 25 34 64 90

 

 

버블 정렬 장단점

 

- 장점

• 구현이 간단하고 이해하기 쉽습니다.
• 추가적인 메모리 공간이 필요하지 않습니다.
• 이미 정렬된 리스트에 대해서도 성능이 좋습니다.

- 단점

• 시간 복잡도가 O(n^2)으로 비효율적입니다. 따라서 큰 규모의 리스트에 대해서는 성능이 좋지 않습니다.
• 정렬되지 않은 리스트에서도 인접한 원소를 계속하여 비교하므로 비효율적입니다.

 

버블 정렬 사용 사례

 

• 작은 규모의 리스트를 정렬해야 할 경우: 구현이 간단하고 이해하기 쉬운 버블 정렬은 작은 규모의 리스트를 정렬하는 데 적합합니다.
• 이미 정렬된 리스트에 대해서도 성능이 좋기 때문에 이미 정렬된 리스트를 정렬할 필요가 없는 경우에도 사용할 수 있습니다.
• 추가적인 메모리 공간이 제한된 환경에서 사용될 수 있습니다.

 

버블 정렬은 단순하고 직관적인 정렬 알고리즘으로, 작은 규모의 리스트를 정렬하는 데 적합합니다. 그러나 큰 규모의 리스트에 대해서는 효율성이 떨어지므로, 대규모 데이터를 정렬해야 할 때는 다른 정렬 알고리즘을 고려하는 것이 좋습니다.