Stability

이 레슨에서는 버블 정렬 알고리즘의 안정성(stable nature)에 대해 확인해 보겠습니다.

안정성(stability)이란 무엇일까요?

정렬 알고리즘은 동일한 키를 가진 두 객체가 정렬 전의 입력 배열에서와 동일한 순서로 정렬 후의 출력 결과에도 나타날 때 안정적이라고 합니다.

예를 들어, [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] 배열을 정렬해야 한다고 가정해 봅시다. 여기에는 8₁과 8₂로 표시된 두 개의 8이 있습니다. 정렬 후에는 두 가지 가능한 배열을 얻을 수 있습니다. 바로 [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]와 [1,2,4,6,<strong>8<sub>2</sub></strong>,<strong>8<sub>1</sub></strong>]입니다. 두 배열 모두 정렬된 상태이지만, 두 번째 배열에서는 두 8의 순서가 바뀐 반면, 첫 번째 배열에서는 입력 배열과 순서가 동일합니다.

이제 버블 정렬 알고리즘에 대해 이를 확인해 봅시다.

첫 번째 패스(First Pass): [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] -> [2,4,<strong>8<sub>1</sub></strong>,6,1,<strong>8<sub>2</sub></strong>]

두 번째 패스(Second Pass): [2,4,<strong>8<sub>1</sub></strong>,6,1,<strong>8<sub>2</sub></strong>] -> [2,4,6,1,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

모든 패스가 끝난 후의 최종 출력은 다음과 같습니다: [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

출력 배열과 입력 배열 모두에서 8의 순서가 동일하다는 점에 주목해 보세요.

따라서, 버블 정렬 알고리즘은 안정적(Stable)입니다!