버블 정렬 (bubble sort) 알아보기

반응형

이번 포스팅에서는 정렬 알고리즘 중 가장 기초가 되는 방법 중 한 가지인 버블 정렬에 관한 이야기를 해보려고 합니다. 어떤 순서가 있는 데이터가 있을 때 이것을 정렬하는 상황이 많이 발생합니다. 가장 대표적인 상황으로는 숫자 데이터에 대해 내림차순이나 오름차순으로 정렬할 때가 있습니다. 정렬하는 방법은 굉장히 다양합니다. 따라서 여러 가지 종류의 정렬 알고리즘을 알아두고 상황에 따라 적절한 알고리즘을 적용하는 것이 좋습니다.

 

버블 정렬은 굉장히 간단하므로 이해하기에 쉽습니다. 몇몇 정렬 알고리즘은 우리가 머릿속으로 어떤 자료를 정렬한다고 했을 때 쉽게 떠올릴만한 방법을 정리해놓은 것들인데, 버블 정렬도 그 중 한 가지 입니다. 버블 정렬의 원리는 서로 인접한 두 원소를 검사하면서 정렬하는 방식입니다. 조금 무식한 방법처럼 보이지만 제일 간단한 방법이기도 합니다. 은근히 선택 정렬과 헷갈릴 수 있는데, 선택 정렬은 데이터 전체를 훑으면서 가장 작은/ 가장 큰 값을 찾은 뒤 적절한 위치에 넣어주는 방식이고, 버블 정렬은 인접한 두 데이터끼리 계속 비교해가며 정렬을 하는 방식입니다.

 

조금 더 구체적으로 버블 정렬에 관해 설명해보겠습니다. 우선 숫자 데이터에 대해 오름차순으로 정렬한다고 가정해보겠습니다. 이때 첫 번째 자료와 두 번째 자료를 비교하여 첫 번째 자료가 더 크다면 두 자료의 순서를 바꿉니다. 만약 처음부터 두 번째 자료가 더 큰 값이라면 굳이 바꿀 필요가 없습니다. 다음으로 두 번째 자료와 세 번째 자료도 마찬가지 방식으로 비교합니다. 이렇게 계속해서 인접한 자료와 비교하여 데이터의 순서를 정리해줍니다. 마지막 자료까지 정렬을 완료했다면 데이터 중 가장 큰 값이 마지막 인덱스 위치에 도달해 있을 것입니다. 버블 정렬은 1번 순회를 거치면 1개의 자료가 정렬됩니다. 따라서 모든 자료를 정렬하려면 n-1번 순회를 거쳐야 합니다.

 

버블 정렬 예시

간단한 예시를 통해 버블 정렬에 대해 알아보도록 하겠습니다.

 

데이터: [2, 4, 3, 8, 5]

 

주어진 데이터에 대해 오름차순 정렬을 하려고 합니다. 먼저 [2, 4]를 비교해서 큰 값을 뒤로, 작은 값을 앞으로 옮깁니다. 이 경우 그대로 둘 것이고 만약 정렬이 필요하다면 두 데이터를 swap하면 됩니다. 다음으로는 [4, 3]을 비교합니다. 4가 더 앞에 있기 때문에 두 데이터의 위치를 변경합니다. 이어서 [4, 8]을 비교해서 확인해보면 그대로 둬야 하는 것을 알 수 있고 마지막으로 [8, 5]를 비교하여 데이터를 swap 합니다.

 

1회 순회 결과: [2, 3, 4, 5, 8]

 

이 경우에는 1회 순회만으로 데이터가 오름차순으로 예쁘게 정렬되었습니다. 하지만 일반적으로 버블 정렬에서는 한 번 순회해서 정렬이 보장된 값은 맨 마지막 인덱스의 값일 뿐입니다. 따라서 코드를 작성할 때는 정렬을 하기 위한 순회를 n-1번 하도록 해야 합니다.

 

버블 정렬 특징

위 예시를 통해 알아보았듯 버블 정렬은 굉장히 단순하면서도 직관적입니다. 인접한 두 자료를 계속 비교해가며 정렬을 하므로 구현이 간단하다는 장점이 있습니다. 그러나 단점으로는 비효율적입니다. 선택 정렬과 비교해봐도 매번 인접한 자료를 비교해서 swap 해야 하기 때문에 불필요한 연산 과정이 많이 포함됩니다. 이로 인한 소요 시간도 꽤 걸리는 단점이 있습니다.

 

버블 정렬의 시간 복잡도는 O(N^2)입니다. 평균, 최상, 최악의 경우 모두 평균적으로 O(N^2)이기 때문에 데이터와 관계없이 일정합니다. 최선의 경우에도 N^2 로 비효율적인 시간 복잡도를 갖고 있습니다. N^2 복잡도를 갖고 있으므로 좋은 정렬 방법이라고 볼 수는 없지만 쉽고 간단하게 구현할 방법이기 때문에 데이터의 크기가 크지 않으면 빠르게 적용해서 사용할 수 있는 방법이기도 합니다. 따라서 무조건 빠른 정렬 알고리즘만 사용한다기보다 상황에 맞는 방법을 효율적으로 적용할 줄 아는 것이 좋겠습니다.

 

요약하면 버블 정렬은 데이터의 크기가 큰 경우 사용하기에 적합하지 않은 방법이지만 작은 데이터에 간단하게 적용해볼 경우 사용할 수 있는 알고리즘입니다. 다음 포스팅에서는 버블 정렬과 유사한 다른 N^2 시간 복잡도를 갖는 알고리즘에 대해서도 알아보도록 하겠습니다.