알고리즘 | 버블 정렬

✔ 학습목표

버블 정렬의 원리와 실행 시간을 설명하고 구현할 수 있다.

 

정렬

어떤 배열이 주어졌을 때, 그 배열이 미리 정렬되어 있다면 훨씬 빠른 속도로 검색이 가능하다. 정렬하기 위한 방법은 여러 가지가 있으며 각각의 효율성도 다르다. 이번 글에서는 그중 하나인 버블 정렬에 대해 공부한다.

 

버블 정렬

버블 정렬(bubble sort)은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말한다. 마치 거품이 터지면서(서료 비교 및 교환하면서) 위로 올라가는(옆으로 이동하는) 것처럼 말이다. 이는 접근법이 간단하다는 장점이 있지만, 자칫하면 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있다.

 

버블 정렬은 아래와 같은 의사 코드로 나타낼 수 있다.

 

Repeat n–1 times

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

 

이해를 위해 간단한 GIF를 보자.

 

 

예제는 다음과 같다.

 

Bubble sort - Wikipedia

 

 

다섯 자리의 숫자(5 1 4 2 8)를 오름차순으로 버블 정렬시키는 예제다(예제의 굵게 표시된 숫자는 비교 단계에 있다는 것을 의미한다). 설명에 나와있듯이 버블 정렬의 경우 이미 정렬이 끝났음에도 정해진 비교를 진행한다는 특징이 있다(Third Pass).

 

효율성

이를 실제 코드로 구현하려면 중첩루프를 돌아야 한다. 앞서 배운 알고리즘의 효율을 생각해보자. n개의 값이 주어졌을 때 루프가 각 n-1번, n-2번 반복되므로 (n−1)∗(n−2)=n​ ^2​^^^66^^^​−3n+2번의 비교 및 교환이 필요하다.

 

표기법으로 나타내면 시간복잡도의 상한은 O(n^2)이다(n이 매우 크다고 가정). 그렇다면 하한은 어떨까. 버블 정렬에서는 정렬 여부에 관계없이 루프를 돌며 전체 값을 비교하기 때문에 하한도 여전히 Ω(n^2)이다. 주어진 배열 안에서 교환을 통해 정렬하기 때문에 공간복잡도는 O(n)이다.

 

생각해보기

버블정렬이 효율적인 경우는 어떤 경우일까?

 

버블 정렬은 비교와 교환의 과정을 거치는 알고리즘이다. 그중에서도 특히 교환에서 오랜 시간이 소요된다. 배열이 이미 정렬되어 있을 경우 비교만 일어나기 때문에 상대적으로 효율적이다. 하지만 무작위로 정렬돼있는 경우 교환 연산이 많이 일어나기 때문에 상대적으로 비효율적이다.

(생각해보기의 답변은 네이버 CS50 코칭 스터디 2기 Jisu 코치님의 도움을 받았습니다. )

 

 

 

참고 자료

Bubble sort - Wikipedia

정렬 알고리즘 6개 정리

---

 

이 글은 네이버 부스트 코스 David J. Malan(데이비드 J. 말란) 교수님의 모두를 위한 컴퓨터 과학(CS50 2019) 강의를 수강하고 작성한 글입니다. 본 강좌 내 실습에서는 CS50 Sandbox를 사용합니다.

 

모두를 위한 컴퓨터 과학 (CS50 2019)