📒 갈무리 - 버블정렬(Bubble Sort)

📌 버블정렬이란?

- 서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내는 정렬방식 이다.

 

📌 버블정렬 진행 순서

1. 첫번째 데이터와 두번째 데이터를 비교하여 첫번째 값이 더 크면 두번째 데이터와 교환한다.

2. 두번째 데이터와 세번째 데이터를 비교하여 더 큰 수를 뒤로 보낸다.

3. 위 순서를 반복하면 제일 큰 숫자가 맨 뒤로가게 된다.

- 이렇듯, 처음부터 n-1번째 데이터까지 반복하며 비교해서 정렬하는 알고리즘이다.

 

📌 직접 구현해 보자...

// C#
        public void BubbleSort(int[] data)
        {
            for (int i = 0; i < data.Length - 1; i++)
            {
                for (int j = 0; j < data.Length - 1 - i; j++)
                {
                    if (data[j] > data[j + 1])
                    {
                        Swap(ref data[j], ref data[j + 1]);
                    }
                }
            }
        }

        public void Swap(ref int number1, ref int number2)
        {
            int temp = number1;
            number1 = number2;
            number2 = temp;
        }
        // 가독성을 위해 각 기능마다 함수로 분리하면 좋지만, 지금은 편의상 간단하게 구현함

 

📌 버블정렬의 특징

- 구현은 단순하지만 비교적 성능이 좋지 않다.

- 데이터의 모든 요소와 교환해야 한다.

- 이미 정렬된 데이터도 교환되는 일이 발생한다.

- 선택정렬과 동일하게 O(n²)의 시간 복잡도 이지만, 실제로는 선택정렬보다 좋지 않은 효율을 띈다.

- 선택정렬은 최솟값을 찾아서 매 회차마다 한 번씩만 Swap이 일어나지만, 버블정렬은 회차마다 여러 번의 Swap이 발생하기 때문이다.