[알고리즘] 버블 정렬 (Bubble Sort)

1. 개념

인접한 두 원소를 비교 하여 정렬하는 방법입니다.

단순히 A > B  라는 조건식을 이용하여 1회전 마다 큰 값이든 작은 값이든 하나씩 위치를 맞춰가는 방식으로

정렬하고자 하는 자료의 n의 2승만큼 반복하여 정렬합니다.

- 오름 차순 : 작은 값을 먼저 오게 만드는 정렬 방식 ( 1, 2, 3 ... )으로 A>B 라면 교환하여 정렬합니다.

- 내림 차순 :  큰 값을 먼저 오게 만드는 정렬 방식 ( ... 3, 2, 1 ) 으로 A<B 라면 교환하여 정렬합니다.

2. c# 코드

내림차순

using System;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] nArr = new int[]{ 1, 4, 3,  5, 9, 6, 2, 7, 8, 10 };

            int nTemp;
            int nCount = 0;
            for(int i = 0; i < nArr.Length-1; i++)
            {
                for (int j = 0; j < nArr.Length-1; j++)
                {
                    if(nArr[j] < nArr[j+1])  
                    {
                        nTemp = nArr[j+1];
                        nArr[j+1] = nArr[j];
                        nArr[j] = nTemp;
                    }
                    nCount++;
                }
            }

            Console.WriteLine("Count : {0}", nCount);

            for(int i = 0; i < nArr.Length; i++)
                Console.Write(nArr[i] + "\t");
        }
    }
}

결과

Count : 81 10  9  8  7  6  5  4  3  2  1

조건식만 바꿔준다면 오름차순으로 정렬됩니다. ( nArr[j] > nArr[j+1] )

결과에서 알수있듯 총 비교횟수는 81회입니다. 이는 데이터 총갯수 - 1의 2승 만큼 계산되어 진것으로 연산순서는

아래와 같습니다.

//------- 시작 --------
// 1 4 3 5 9 6 2 7 8 10
//------- 1 회 --------
// 4 1 3 5 9 6 2 7 8 10
// 4 3 1 5 9 6 2 7 8 10
// 4 3 5 1 9 6 2 7 8 10
// 4 3 5 9 1 6 2 7 8 10
// 4 3 5 9 6 1 2 7 8 10
// 4 3 5 9 6 2 1 7 8 10
// 4 3 5 9 6 2 7 1 8 10
// 4 3 5 9 6 2 7 8 1 10
// 4 3 5 9 6 2 7 8 10 1

//------- 2 회 --------
// 4 3 5 9 6 2 7 8 10 1
// 4 5 3 9 6 2 7 8 10 1
// 4 5 9 3 6 2 7 8 10 1
// 4 5 9 6 3 2 7 8 10 1
// 4 5 9 6 3 2 7 8 10 1
// 4 5 9 6 3 7 2 8 10 1
// 4 5 9 6 3 7 8 2 10 1
// 4 5 9 6 3 7 8 10 2 1
// 4 5 9 6 3 7 8 10 2 1
// ...

3. 장단점

장점

- 구현이 간단하다

단점

- 구조상 모든 요소들을 비교하고 이동시키기 때문에 효율적이지 못하다

일반적으로 자료의 이동 보다 교환 작업이 연산 작업이 복잡하기 때문에 구현의 단순성에도 불구하고

거의 쓰이지 않습니다.

정렬 알고리즘 테스트

종류	최소	최대	정렬시간 (10만개 테스트)
퀵 정렬	n log n	n2	32 ms
삽입 정렬	n	n2	8142 ms
선택 정렬	n2	n2	13499 ms
버블 정렬	n2	n2	53488 ms

4. 관련글

• 삽입 정렬 ( Insertion Sort ) Post 참고
• 선택 정렬 ( Selection Sort ) Post 참고
• 퀵 정렬 ( Quick Sort ) Post 참고