[CS50] 알고리즘: 버블 정렬
❄️ David Malan 교수의 모두를 위한 컴퓨터 과학(CS50 2019)을 바탕으로 정리한 내용입니다.
버블 정렬
정렬되지 않은 리스트를 탐색하는 것 보다 정렬한 뒤 탐색하는 것이 더 효율적입니다.
정렬 알고리즘 중 하나는 버블 정렬입니다.
버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말합니다.
버블 정렬은 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중합니다.
이 접근법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있습니다.
예시 1
아래와 같은 8개의 숫자가 임의의 순서로 나열되어 있습니다.
이 숫자들을 오름차순으로 정렬하기 위해 바로 옆의 있는 숫자들과 비교하는 방법을 사용해 보겠습니다.
먼저 가장 앞의 6과 3을 비교해서 순서를 바꿉니다.
다음 쌍인 6과 8을 비교해보면 교환할 필요가 없으므로 그대로 둡니다.
바로 다음에 있는 쌍인 8과 5를 비교해서 순서를 바꿉니다.
이런 식으로 숫자 끝까지 진행하면 아래와 같이 정렬이 됩니다.
하지만 아직 오름차순으로 정렬이 되지 않았기 때문에, 다시 처음부터 동일한 작업을 반복합니다.
조금 더 잘 정렬이 되었습니다. 이 과정을 총 (n-1)번 반복하면 최종적으로 아래와 같이 오름차순 정렬이 될 것입니다.
예시 2
이러한 정렬 방식을 ‘버블 정렬’이라고 합니다.
마치 거품이(비교 및 교환이) 터지면서 위로 올라오는 (배열의 옆으로 이동하는) 방식이기 때문입니다.
아래와 같이 의사 코드로 나타낼 수 있습니다.
Repeat n–1 times
For i from 0 to n–2
If i'th and i+1'th elements out of order
Swap them
중첩 루프를 돌아야 하고, n개의 값이 주어졌을 때 각 루프는 각각 n-1번, n-2번 반복되므로 (n-1) * (n-2) = n^2 - 3n + 2 번의 비교 및 교환이 필요합니다.
여기서 가장 크기가 큰 요소는 n^2 이므로 위와 같은 코드로 작성한 버블 정렬 실행 시간의 상한은 O(n^2)이라고 말할 수 있습니다.
정렬이 되어 있는지 여부에 관계 없이 루프를 돌며 비교를 해야 하므로,
위와 같은 코드로 작성한 버블 정렬의 실행 시간의 하한도 여전히 Ω(n^2)이 됩니다.
생각해보기
버블 정렬이 효율적인 경우는 어떤 경우인가요? 반대로 어떤 경우에 비효율적이게 될까요?
- 효율적인 경우는 데이터양이 작고 데이터가 정렬 되어 있지 않을 때입니다.
- 비효율적인 경우는 정렬 되어 있는 배열을 정렬하거나 데이터 양이 많을 때입니다.
버블정렬은 이미 정렬이 되어 있는 배열의 경우에도 동일하게 배열의 요소를 하나씩 비교하며 정렬하기 때문입니다.
💛 개인 공부 기록용 블로그입니다. 👻