정렬 #1) 버블 정렬

버블 정렬은 아래의 과정으로 이루어진다.

노란색으로 칠해진 칸은 비교중인 두 수를 의미한다.

 

---

---

 

수열 4, 3, 2, 1 을 오름차순으로 정렬하는 과정이다.

인접한 두 수를 반복해서 비교하며 가장 큰 수를 뒤로 이동시킨다.

버블 정렬이라는 이름이 붙게 된 이유가, 이러한 과정이 마치 거품이 수면 위로 올라오는 모습과도 같아서라는데 어찌보면 그럴듯하다.

큰 수들이 하나씩 올라오는 모습을 거품이 올라오는 것처럼 생각했을 수도 있겠다.

 

---

---

 

버블 정렬의 시간 복잡도는 O(n^2)이다.

이유는 위 그림을 통해 알 수 있는데, 길이가 4인 수열에서의 비교는 3 + 2 + 1 = 6번 이루어지는 것을 확인할 수 있다.

만약 길이가 n이라면? 분명 (n - 1) + (n - 2) + ... + 1번 이루어질 것이다. 이는 충분히 상상이 가능하다.

따라서, (n - 1) + (n - 2) + ... + 1을 등차수열 공식을 사용하여 정리하면 O(n^2)이 되는 것을 알 수 있다.

 

---

int[] num = { 4, 3, 2, 1 };

for (int i = 0; i < num.Length; i++)
{
    for (int j = 1; j < num.Length - i; j++)
    {
        if (num[j - 1] > num[j])
            (num[j - 1], num[j]) = (num[j], num[j - 1]); //Swap
    }
}

 

정렬 결과