버블정렬 (C#)

📌 버블정렬 (Bubble Sort) 란?

버블 정렬은 인접한 두 원소를 비교하여 큰 원소를 뒤로 보내는 방식으로 정렬하는 알고리즘이다. 이 과정을 배열의 모든 원소에 대해 반복하며, 가장 큰 원소부터 차례대로 배열의 끝으로 이동하게 된다. 버블 정렬은 구현이 간단하지만, 평균 및 최악의 경우 시간 복잡도가 O(n^2)으로 비효율적이다.

 

비효율적이라고 써놓긴 했지만 기초 알고리즘이므로 알고리즘 이해를 위해

반드시 공부해야 하니 진행해 보도록 하자!

 

다음과 같은 배열이 있다고 할 때 오름차순으로 정렬을 해보자.

 

버블 정렬은 다음과 같이 이루어진다.

 

위처럼 첫 사이클에서 원소가 n개의 배열일 때 0 ~ n-1 번째 원소와 인접한 원소를 비교해 정렬을 한다.

이때, 오름차순 기준 한 사이클을 돌면 배열에서 가장 큰 원소가 마지막 원소가 된다.

 

• i = 0번 원소부터 n개의 원소일 때 i < n - 1까지 반복한다 
• j = 0번 원소부터 비교를 하고,
  한 사이클을 돌면 i번 사이클의 마지막 원소는 정렬이 돼있으므로 j < n - i - 1까지 반복한다.

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