서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않으면 자리를 교환하면서 정렬하는 알고리즘이다.
Sorting Algorithm Animations // 정렬되지않은 데이터를 Animation으로 다양하게 볼 수 있다.
1회전에 첫 번째 원소와 두 번째 원소를 비교하고 첫 번째 > 두 번째라면 서로 교환한다. 첫 번째 원소가 두 번째 원소와 같거나 작다면 교환하지 않고 진행한다. 다시 두 번째 원소와 세 번째 원소, 세 번째 원소와 네 번째 원소, ... 같은 방법으로 length - 1 번째 원소까지 비교하여 조건에 맞으면 교환한다.
1회전을 수행하고 나면 제일 큰 원소는 마지막으로 이동하고 정렬에서 제외된다. 이때 첫 번째 원소부터 다시 시작한다. 2회전을 수행하고 나면 끝에서 두 번째 원소까지 정렬에서 제외되고 이 과정을 반복하여 모든 데이터를 정렬한다.
function bubble(arr) {
for(let i = 0; i < arr.length; i++) {
for(let j = 0; j < arr.length; j++) {
if( arr[j] > arr[j+1] ) {
let temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
설명과 GIF를 보면 정렬된 원소는 제외하고 남은 원소들로만 다시 정렬을 해야한다.
위와 같이 구현하면 문제점이 발생한다. 1회전 수행 후 이미 정렬된 원소를 계속하여 비교하는 점, length의 범위를 넘어가 마지막 원소와 undefined를 비교하는 점이다.
또 한가지가 더 있는데, [5, 1, 2, 3, 4]와 같이 거의 정렬된 데이터에서 1회전 수행 후 정렬이 끝나지만 다시 여러번 비교하며 교환없이 수행된다.
function bubble( arr ) {
let noSwaps;
for ( let i = arr.length; i > 0; i-- ){
noSwaps = true;
for ( let j = 0; j < i-1; j++ ){
if ( arr[j] > arr[j+1] ) {
let temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
noSwaps = false;
}
}
if ( noSwaps ) break;
}
return arr;
}