[Algorithm] 버블 정렬(Bubble Sort)에 대해 알아보자!

이번에 다룰 내용은 여러 정렬 알고리즘 중 하나인 버블정렬이다.

 

바로 버블정렬의 개념부터 알아보자.

 

버블정렬이란?

인접한 값을 순차적으로 계속 비교하여 위치를 바꾸면서 최대, 최소값을 구해가는 정렬 방식이다. 다시 말해, A>B or A<B의 조건식을 이용하여 1회전 할 때마다 큰 값이든 작은 값이든 하나씩 위치를 맞춰가는 정렬인 것이다.

따라서 시간 복잡도는 O(n^2)가 된다.

여기서 오름차순으로 정렬을 하고싶다 하면 A>B, 내림차순으로 정렬을 하고싶다 하면 A<B로 조건식을 맞춰주면 된다.

 

아래의 이미지를 한번 봐보자.

위의 이미지에 쓰여져있는 설명을 한번 읽어보면 어느 형식으로 진행되는지 알 수 있을 것이다.

 

이제 이 버블정렬의 장 단점을 알아보자.

 

장점

• 소스 구현이 간단한 편이다.

단점

• 구조상 모든 요소들을 비교하고 이동시키기 때문에 시간에 있어서 효율적이지 못하다.

 

정렬 알고리즘 테스트 결과

 

이제 버블 정렬 구현 소스로 한번 봐보자.

 

(C# Source)

using System;

namespace Jeongkyun_BubbleSort
{
    public class Program
    {
        public static void Main(string[] args)
        {
            int[] nArr = new int[] { 1, 7, 5, 34, 5, 2, 23, 54, 1 };
            nArr = arr_swap_bubble_sort(nArr);
            Print(nArr);

            Console.ReadKey();
        }

        /// <summary>
        /// 버블 정렬 + SWAP 함수
        /// </summary>
        /// <param name="arr">배열 변수</param>
        static int[] arr_swap_bubble_sort(int[] arr)
        {
            int temp = -1;

            //인덱스 1번부터 검사
            for (int i = 1; i < arr.Length; i++)
            {
                // i+1 ~ arr.Length의 길이까지 검사
                for (int j = i+1; j < arr.Length; j++)
                {
                    //arr[j]보다 비교대상이 크면 Swap 진행
                    if (arr[i] > arr[j])
                    {
                        temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }

                }
            }
            return arr;
        }

        /// <summary>
        /// Print 함수
        /// </summary>
        /// <param name="arr_val"></param>
        static void Print(int[] arr_val)
        {
            for (int i = 0; i < arr_val.Length; i++)
            {
                Console.Write(arr_val[i].ToString() + "\t");
            }
        }
    }
}