Bubble Sort(버블 정렬)

버블정렬 코드 입니다.

- i 와 i + 1을 비교하여 i 가 더 클 경우에 스왑하고 더 이상 필요 없을 때 까지 반복 합니다.

- 버블보다 삽입정렬의 복잡도가 더 좋습니다.

 

성능

- 최악의 경우 : O(n^2)

- 최선의 경우 : O(n)

- 평균 : O(n^2)

- 최악의 경우 공간 복잡도 : O(1)

static void BubbleSort(int[] a)
{
    for (int pass=a.Length-1; pass >= 0; pass--)
    {
        for (int i=0; i<pass; i++)
        {
            if (a[i] > a[i+1])
            {
                // swap
                int temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
            }
        }
    }
}

 

테스트

using System;

namespace BubbleSort
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Bubble sort");
            int[] numbers = { 2, 10, 3, 7, 1, 4, 3, 5, 8 };
            Print(numbers);
            BubbleSort(numbers);
            Print(numbers);
        }

        static void Print(int[] a)
        {
            string temp = "";
            for (int i = 0 ;i < a.Length; i++)
                temp += a[i].ToString();            
            Console.WriteLine(temp);
        }

        static void BubbleSort(int[] a)
        {
            for (int pass=a.Length-1; pass >= 0; pass--)
            {
                for (int i=0; i<pass; i++)
                {
                    if (a[i] > a[i+1])
                    {
                        // swap
                        int temp = a[i];
                        a[i] = a[i+1];
                        a[i+1] = temp;
                    }
                }
            }
        }
    }
}

 

결과