안녕하세요. 이번 시간에는 기본적인 정렬 중 하나인 버블 정렬에 대해 알아보겠습니다. 이렇게 이름지어진 이유는 정렬하는 모습이 거품이 꺼지는 모습과 비슷하기 때문입니다. 실제로 흩어져있는 데이터들이 서로 바뀌면서 일렬로 정렬되는데 그 모습이 정말 보기 좋습니다. 링크에 버블 정렬에 대한 움짤이 있습니다.
아쉽게도 위키피디아에는 자바스크립트로 구현된 버블 정렬 코드가 없기 때문에 제가 직접 보여드리겠습니다. (없어서 다행입니다.) 버블 정렬은 O(n^2)이기 때문에 성능이 좋지 않습니다. 거기에 성능이 안 좋은 정렬 중에서도 가장 안 좋은 편에 속하는 정렬이라, 주로 알고리즘 교육용을 제외하고는 사용되지 않습니다. 먼저 간단한 예제를 볼까요?
[5,1,7,4,6,3,2,8] 처음 두 수를 비교해서 순서대로 숫자를 서로 바꿔줍니다.
[1,5,7,4,6,3,2,8] 5와 7은 이미 정렬되어 있으니까 그대로 놔둡니다.
[1,5,7,4,6,3,2,8] 7과 4는 서로 바꿔줍니다.
[1,5,4,7,6,3,2,8]
[1,5,4,6,7,3,2,8]
[1,5,4,6,3,7,2,8]
[1,5,4,6,3,2,7,8] 끝까지 정렬을 했으면 다시 처음부터 비교합니다.
[1,5,4,6,3,2,7,8]
[1,4,5,6,3,2,7,8] 5,6은 넘어가고 6,3 순서를 바꿔줍니다.
[1,4,5,3,6,2,7,8]
[1,4,5,3,2,6,7,8] 다시 처음부터 비교합니다.
[1,4,3,5,2,6,7,8]
[1,4,3,2,5,6,7,8] 다시 처음부터
[1,3,4,2,5,6,7,8]
[1,3,2,4,5,6,7,8] 다시 처음부터
[1,2,3,4,5,6,7,8] 정렬 끝
정렬 과정이 엄청 길죠? 한 과정에 겨우 두 수의 위치를 서로 바꾸는 작업밖에 못합니다. 성능이 좋을 리가 없죠. 하지만 간단한 작업을 하는 만큼, 코드를 짜기는 쉽습니다. 코드로 볼까요?
var bubbleSort = function(array) {
var length = array.length;
var i, j, temp;
for (i = 0; i < length - 1; i++) { // 순차적으로 비교하기 위한 반복문
for (j = 0; j < length - 1 - i; j++) { // 끝까지 돌았을 때 다시 처음부터 비교하기 위한 반복문
if (array[j] > array[j + 1]) { // 두 수를 비교하여 앞 수가 뒷 수보다 크면
temp = array[j]; // 두 수를 서로 바꿔준다
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
return array;
};
bubbleSort([5,1,7,4,6,3,2,8]);코드는 간단하지만 반복문을 두 번 중첩해서 돌기 때문에 성능이 안 좋습니다. 처음 삽입 정렬 시간에도 반복문을 두 번 돌아서 성능이 별로였죠. 다행히 return 값은 array라 메모리를 더 차지하지는 않습니다. 뭐 어차피 앞으로 버블 정렬을 사용하는 일은 없을 겁니다. 다음 시간에는 선택 정렬에 대해 알아보겠습니다!
익명
