버블정렬(bubble sort) - 정렬 알고리즘을 배울때 보통 먼저 배우는 정렬 알고리즘 입니다.
버블정렬은 간단하기 때문에, 직관적으로 쉽게 이해할 수 있습니다.
마치 거품이 수면으로 올라오는 것 같아서 버블정렬이라고 한다네요.
버블정렬을 설명하기에 앞서 주요 정렬 알고리즘에 관한 시각적 자료를 링크하겠습니다.
정렬들간에 비교와 정렬의 특성을 파악할 수 있습니다.
버블정렬은 사람의 입장에서는 그렇게 자연스럽지 않습니다. 위 영상처럼 두 개씩 대소관계를 비교하며 위치를 바꾸어 나가는 데 컴퓨터 가 살아있다면 컴퓨터 입장에서 이러한 단순함이 오히려 쉽다고 느껴질꺼라 생각합니다.
버블 소트의 문제해결 방법은 다음과 같습니다.
1. 배열의 첫번째 요소와 두번째 요소의 대소관계를 비교한다
2. 대소관계에 따른 위치를 바꾼다.
3. 비교하는 배열의 첨자(요소의 번호,위치)를 하나씩 증가하여 1,2번을 되풀이한다.
4. 배열의 끝 요소까지 비교했으면 처음부터 위 작업을 반복하되 바로 앞에서 비교했던 요소 중 제일 마지막 첨자는 제외한다.
이런식으로 비교하면 배열의 맨 뒤에서부터 큰수가 차례대로 채워지게 됩니다.
위 방법은 (배열 요소의 개수 -1)번의 루프안에 (1부터 (배열요소의 개수-1)까지의 합)의 루프가 돌아갑니다.
다음은 크기순서 관계없이 무작위로 나열된 크기 5인 배열을 버블정렬(bubble sort)을 이용해 정렬하는 그림입니다.
붉은 부분은 문제해결 방법의 순서 1에 해당됩니다. 만약 대소를 비교하여 바꿀 필요가 없다면 2번은 수행되지 않습니다. 이렇게 배열을 끝까지 비교를 마치면 배열의 끝에는 비교한 수 중 가장 큰 수가 있게 됩니다.
위에 44의 수는 더이상 비교할 필요가 없습니다. 제외를 하고 문제해결방법의 1,2번을 배열의 첫째 요소부터 반복합니다.
이런 식으로 나머지 세계의 수에 대해서도 마무리하면 모든 루프가 끝나고 배열은 크기 순서대로 정렬이 되게 됩니다.
다음은 위 배열에대한 버블정렬을 하는 코드입니다.
코드는 매우 간단합니다. 배열에 대한 이해와 각 루프간에 상관관계를 파악한다면 쉽게 분석할 수 있습니다.
위 코드는 버블정렬의 기본적인 생각이 반영되어 있지만, 세련되지는 못합니다. 이유는 다음과 같습니다.
2,4,23에 대해서 문제해결방법 1,2를 시행하지만 쓸모없는 시행이 되어버립니다. 이렇게 정렬이 다 된 경우에도 나머지 수행을 하는 것은 매우 낭비적인 일이고, 배열의 크기가 클 수록 자원낭비가 커지게 됩니다.
해결 방법은 일종의 플래그를 설정하여, 앞의 시행에서 문제해결방법 2번의 시행이 한 차례도 일어나지 않는 다면 정렬이 다 된 것으로 간주해도 좋습니다.
만약 flag가 변화하지 않는다면 문제해결 2번이 한 차례도 실행되지 않은 것이므로 break로 루프를 빠져나갑니다.
http://www.sorting-algorithms.com/
위에 링크된 주소로 가면 각 정렬들간 비교를 할 수 있습니다. 버블 정렬은 단순한 만큼 속도면에서 매우 비효율적인 정렬입니다. 앞으로 여러 정렬들을 포스팅하며 효율적인 정렬방법과 여러 상황에 맞는 정렬 방법을 정리해 가도록 하겠습니다.