Chapter 10. 단순한 정렬 알고리즘

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

 

다음과 같이 네 개의 숫자가 나열되어 있다고 가정하겠습니다.

3

2

4

1

위와 같이 나열된 숫자를 오름차순으로 정렬해 보겠습니다. 먼저 맨 앞의 3과 그 다음의 2를 비교합니다. 비교 결과 오름차순에 위배되면 두 숫자의 위치를 바꿉니다. 따라서 다음과 같이 됩니다.

2

3

4

1

이번에는 두 번째 숫자와 그 다음 숫자를 비교합니다. 비교하면 3과 4로 오름차순에 위배되지 않으므로 두 숫자의 위치를 바꾸지 않습니다.

바로 다음으로 넘어가 이번에는 세 번째 숫자와 그 다음의 숫자를 비교합니다. 비교 결과 오름차순에 위배되므로 두 숫자의 위치를 바꿉니다. 그럼 다음과 같이 됩니다.

2

3

1

4

물론 정렬이 모두 끝난 것은 아닙니다. 위와 같은 과정을 한 번 더 수행합니다. 다만, 전에는 세 번째 숫자까지 비교한 반면, 이번에는 두 번째 숫자까지만 비교대상에 넣습니다.

 

먼저, 첫 번째 숫자와 그 다음 숫자를 비교합니다. 비교 결과 오름차순에 위배되지 않으므로 두 숫자의 위치를 바꾸지 않습니다. 바로 이어서 이번에는 두 번째 숫자와 그 다음의 숫자를 비교합니다. 비교 결과 오름차순에 위배되므로 두 숫자의 위치를 바꿉니다. 그럼 다음과 같이 됩니다.

2

1

3

4

두 번째 숫자까지 비교를 했지만 아직 정렬이 끝이 난 것은 아닙니다. 위와 같은 방법으로 한 번 더 수행합니다. 다만, 전에는 두 번째 숫자까지 비교를 했던 반면, 이번에는 첫 번째 숫자만 비교합니다.

 

첫 번째 숫자와 그 다음 숫자를 비교합니다. 비교 결과 오름차순에 위배되므로 두 숫자의 위치를 바꿉니다. 그럼 다음과 같이 됩니다.

1

2

3

4

이로써 오름차순으로 정렬이 완벽하게 되었습니다.

 

이러한 방식의 정렬을 '버블 정렬'이라고 합니다. 버블 정렬은 보는 바와 같이 정말 단순한 알고리즘으로 정렬을 수행합니다. 

---

버블 정렬의 성능을 한 번 평가해 보겠습니다. 보통 정렬 알고리즘의 성능은 다음 두 가지를 근거로 판단하는 것이 일반적입니다.

• 두 데이터 간의 비교 연산의 횟수
• 위치의 변경을 위한 데이터의 이동 횟수

실제로 시간 복잡도에 대한 빅-오를 결정하는 기준은 '비교의 횟수'입니다. 하지만 '이동의 횟수'까지 살펴보면 동일한 빅-오의 복잡도를 갖는 알고리즘 간의 세밀한 비교가 가능합니다.

 

버블 정렬의 시간 복잡도를 구하는 과정은 설명하지 않겠습니다. 버블 정렬의 시간 복잡도를 계산하면 빅-오는 다음과 같이 됩니다.

버블 정렬의 빅-오를 확인 해 보면 성능이 좋지 못한 알고리즘이라는 것을 알 수 있습니다.

 

이번에는 버블 정렬의 데이터의 이동 횟수를 계산해 보겠습니다. 이동 횟수는 데이터가 이미 정렬되어 있을 경우 0회에서 최악의 경우에는 비교 연산의 횟수와 동일한 횟수를 가집니다. 따라서 데이터 이동 횟수에 대한 빅-오는 최악의 경우를 기준으로 하여 다음과 같이 판단합니다.

---

이번에는 다른 정렬 방법을 소개하겠습니다.

똑같이 다음과 같이 네 개의 숫자가 나열되어 있습니다.

3

2

4

1

이번에는 첫 번째 숫자부터 시작해서 하나씩 값을 들여다보며 최솟값을 찾아냅니다. 그리고 찾아낸 최솟값을 첫 번째 자리에 저장하고, 첫 번째 자리에 있던 데이터를 빈자리에 저장합니다. 즉, 최솟값인 데이터와 첫 번째 데이터의 교환이 일어나는 것입니다. 그럼 다음과 같이 됩니다.

1

2

4

3

바로 이어서 이번에는 두 번째 숫자부터 시작해서 하나씩 값을 들여다보며 최솟값을 찾아냅니다. 그리고 찾아낸 최솟값을 두 번째 자리에 저장하고, 두 번째 자리에 있던 데이터를 빈자리에 저장합니다. 즉, 최솟값인 데이터와 두 번째 데이터의 교환이 일어나는 것입니다. 그럼 다음과 같이 됩니다.

1

2

4

3

결과적으로 교환된 데이터는 없습니다. 다음으로 이번에는 세 번째 숫자부터 시작해서 위와 같은 과정을 수행합니다. 그럼 다음과 같이 됩니다.

1

2

3

4

이로써 정렬이 끝이 났습니다. 이와 같은 정렬 방법을 '선택 정렬'이라고 합니다. 언뜻 보기에는 선택 정렬이 버블 정렬보다 더 효율적으로 보입니다. 정말로 그러한지 성능을 평가해 보겠습니다.

 

먼저, 비교 연산의 횟수의 빅-오를 구해봅니다. 선택 정렬의 경우 첫 번째 요소로부터 마지막 요소까지 비교하고, 다시 두 번째 요소로부터 마지막 요소까지 비교하는 과정을 반복합니다. 따라서 비교 연산 횟수의 빅-오는 다음과 같습니다.

버블 정렬과 빅-오가 같습니다. 이제 실제 데이터가 이동하는 횟수의 빅-오를 구해봅니다. 최선의 경우 데이터의 이동 횟수는 0회가 되겠지만 최악의 경우에는 첫 번째 요소, 두 번째 요소에 값을 저장하는 연산이 차례로 일어나 결국 데이터의 이동 횟수의 빅-오는 다음과 같이 됩니다.

데이터 이동 횟수의 빅-오는 버블 정렬보다도 좋은 모습을 보여주고 있습니다. 하지만 이것도 그다지 좋은 알고리즘이라고 볼 수는 없습니다.

---

다음 정렬 방법을 소개하겠습니다.

이번에도 역시 다음과 같은 네 개의 숫자가 나열되어 있습니다.

3

2

4

1

먼저 첫 번째 요소와 두 번째 요소를 비교하여 오름차순에 위배되면 둘의 위치를 바꿉니다. 그럼 다음과 같이 됩니다.

2

3

4

1

이렇게 되면 첫 번째 요소와 두 번째 요소는 오름차순으로 '정렬된 영역'으로 볼 수 있습니다. 그리고 이 영역의 바로 다음 요소부터는 '정렬이 안 된 영역'으로 간주합니다. 그리고 정렬된 영역의 바로 다음 요소의 값을 정렬된 영역의 요소들과 하나씩 비교해갑니다 비교해서 오름차순에 위배되면 서로 위치를 바꾸고, 위배되지 않으면 그대로 값을 두어 그 요소까지 정렬된 영역으로 포함시킵니다.

 

위의 경우에서 2와 3은 정렬된 영역입니다. 그 바로 다음 요소인 4부터는 정렬이 안 된 영역으로 간주합니다. 정렬된 영역의 바로 다음 요소인 4와 정렬된 영역의 3을 비교합니다. 비교 결과 오름차순에 위배되지 않으므로 값을 그대로 두고 4까지 정렬된 영역으로 포함시킵니다.

2

3

4

1

이어서 정렬된 영역의 바로 다음 요소인 1을 정렬된 영역의 4와 비교합니다. 오름차순에 위배되므로 서로 위치를 바꿉니다. 그럼 다음과 같이 됩니다.

2

3

1

4

이번에는 1과 3을 비교합니다. 오름차순에 위배므로 둘의 위치를 바꿉니다. 그럼 다음과 같이 됩니다.

2

1

3

4

이번에는 1과 2를 비교합니다. 오름차순에 위배되므로 둘의 위치를 바꿉니다. 그럼 다음과 같이 됩니다.

1

2

3

4

더 이상 1과 비교할 대상이 없으므로 비교 연산을 멈추고 1부터 4까지를 정렬된 영역으로 포함시킵니다. 이로써 네 개의 숫자가 오름차순으로 정렬되었습니다. 이런 방식의 정렬 방법을 '삽입 정렬'이라고 합니다.

 

이제 삽입 정렬의 성능을 평가해 보겠습니다. 먼저 비교 연산 횟수의 빅-오를 구해 보겠습니다. 계산 과정은 설명하지 않겠습니다. 삽입 정렬의 비교 연산 횟수의 빅-오를 구해 보면 다음과 같습니다.

최악의 경우 데이터 이동 횟수는 비교 연산의 횟수와 같아지기 때문에 데이터 이동 횟수의 빅-오도 위와 같습니다.