버블 정렬(Bubble sort)

이번 포스팅은 버블 정렬(bubble sort)에 대해 알아보겠습니다.

버블 정렬(bubble sort)은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면

서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행하는 정렬이다.

이러한 비교-교환 과정을 스캔이라 하며 스캔이 한 번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동된다.

이러한 레코드의 이동 과정이 마치 물속에서 거품(bubble)이 보글보글 떠오르는 것과 유사하여 버블 정렬이라 부른다.

이러한 비교-교환 과정은 전체 레코드가 정렬 될 때까지 계속된다.

버블 정렬의 가장 기본적인 원리는 두 레코드를 비교하여 큰 레코드를 리스트의 우측으로 밀어내는 것이다.

위 그림은 두 레코드를 비교하여 만약 앞의 레코드가 더 크다면 서로 교환을 시킨다.

이후 다시 옆 레코드와 비교하는 방법을 반복한다.

간단하게 설명하자면

1. 이웃 하는 두 레코드를 비교하여 큰 레코드는 우측으로 밀어낸다.

2. 더 이상 이웃 하는 레코드가 없을 때까지 반복한다.

3. 리스트의 가장 우측부터 큰 레코드로 정렬이 된다.

4. 모든 레코드가 정렬이 될 때까지 반복한다. 

버블 정렬을 c로 구현한 소스코드이다.

레코드의 수가 n개라고 할 경우

첫번째 비교 횟수는 n-1번

그 다음은 가장 우측에 정렬 되어 있는 레코드를 제외한 n-2번

이러한 방법으로 가장 좌측에 레코드가 하나만 남아 있을 때까지 반복적으로 진행한다.

버블 정렬의 최악, 평균, 최선의 시간 복잡도는 으로 동일하다.

이유는 기존의 레코드들이 정렬이 되어 있던, 되어 있지 않던 상관 없이

레코드들의 가장 처음부터 끝까지 비교하는 과정이 모두 같기 때문이다.

비교 연산은

(n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 회 일어난다.

이동 횟수는 최악의 경우 각 비교 연산마다 세번 씩 발생하기 때문에

3(n-1) + 3(n-2) + ... + 3(2) + 3(1) = 3n(n-1)/2 회 이동한다.

버블 정렬은 위 소스 코드를 보다시피 구현이 매우 간단하지만,

시간 복잡도 측면에서 효율적이지 못하다는 단점이 있다.

이상으로 버블 정렬에 대해 알아 보았습니다.

제가 첨부한 소스 코드를 보고 따라 하는 코딩하는 것도 충분히 공부가 되겠지만

개념과 정렬의 원리를 파악 한 뒤 혼자 힘으로 먼저 코딩을 해보는 것이 도움이 될 것입니다.

다음은 셸 정렬(Shell sort)에 대해 알아 보도록 하겠습니다.