C# 버블 정렬(Bubble Sort)에 대해서

버블 정렬(Bubble Sort)

누구나 한 번쯤은 들어봤을 버블 정렬(혹은 거품 정렬이라고도 불린다)에 대해서 알아보려고 한다.

 

버블 정렬은 구현이 직관적이고 간단하다.

 

• 아래의 과정을 배열의 길이 - 1번 반복한다.
  • n번째 원소와 n + 1번째 원소를 비교한다.
  • n번째 원소가 더 크다면 자리를 바꾼다. (Swap)
  • n + 1번째 원소와 n + 2번째 원소를 비교한다.
  • n + 1번째 원소가 더 크다면 자리를 바꾼다. (Swap)
  • 배열 끝까지 이 과정을 반복한다.
  • 이 과정을 통해 가장 오른쪽에 가장 큰 원소가 위치하게 된다.

가장 큰 원소인 8이 배열 맨 마지막에 위치하게 된다.

 

오른쪽에 차례대로 큰 원소들이 쌓이게 된다.

 

시간 복잡도와 공간 복잡도

• 최고 시간 복잡도: O(n)
• 평균 시간 복잡도: O(n^2)
• 최악 시간 복잡도: O(n^2)
• 최고 공간 복잡도: O(1)

 

수도 코드(Pseudo Code)

Initialize n = Length of Array

BubbleSort(Array, n)
{
    for i = 0 to n-2
    {
        for j = 0 to n-2
        {
            if Array[j] > Array[j+1]
            {
                swap(Array[j], Array[j+1])
            }
        }
    }
}

 

예제 코드

static void Main(string[] args)
{
    var array = new int[] { 3, 2, 1 };

    Console.WriteLine(string.Join(" ", BubbleSort(array))); // 1 2 3
}

public static int[] BubbleSort(int[] array)
{
    for (int i = 0; i < array.Length - 1; i++)
    {
        for (int j = 0; j < array.Length -1; j++)
        {
            if (array[j] > array[j + 1])
            {
                var temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
            }
        }
    }

    return array;
}

 

버블 정렬의 시간 복잡도는 이차 시간 O(n^2)의 복잡도를 가진다. 모든 원소를 순회하면서 n의 원소와 n + 1의 원소를 비교해야 하기 때문이다.

 

함께 읽으면 좋은 글

빅-오(Big-O) 표기법

C# String.Join에 대해서

 

참고 사이트

Bubble Sort Java