데이터를 정렬할 수 있는 방법은 무수히 많고, 각 알고리즘은 장단점을 갖고 있다.
같은 결과값을 갖더라도 결과를 내기까지의 과정이 제각기 다르다. 특정 상황에 유난히 잘 작동하는 정렬 방법이 존재하고, 이를 잘 활용하게 하기 위함
버블 정렬
자바스크립트 내장 정렬 메서드
array.sort() : num1 - num2 가 양수를 반환하면 num2가 앞에, 음수를 반환하면 num1이 앞에 온다.
숫자 뿐 아니라 문자열으 길이를 음수/양수로 구분하여 정렬할수도 있다.
function numberCompare(num1,num2){
return num1 - num2;
}
[ 6, 4, 16,10 ].sort(numberCompare);
개념
현재 항목과 다음 항목을 한 번씩 비교하여 교환. 제일 끝에서부터 차례대로 쌓이며 정렬이 이루어진다.
교환 (swap)
버블 정렬을 구현하기 전에, 정렬에서 사용되는 배열 원소 간 교환 방식을 이해하고 함수로 만들어, 정렬 시 호출하여 사용해보자.
// ES5
function swap(arr, idx1, idx2) {
var tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
// ES6
const swap = (arr, idx1, idx2) => {
[arr[idx1], arr[idx2]][(arr[idx2], arr[idx1])];
};tmp에 저장해놓고 불러와 쓸 수도 있고, 화살표 함수를 통해 한 줄로 코드를 처리할 수도 있다. 근데 가독성이 그리 좋지 않은 듯.
의사코드
- 숫자로 이루어진 배열을 인자로 받는 bubbleSort 함수 선언
- i라는 변수를 갖고 배열의 맨 끝에서 루프를 시작하여 맨 앞에서 끝남
- 외부 루프 안에는 변수 j가 포함된 내부 루프가 존재 (이중 반복문)
- arr[j]와 arr[j+1]을 비교하여 더 큰 수를 [j+1]로 교환
구현
주어진 의사코드 지침을 따라 구현해보았다.
첫 번째 루프 i에서 마지막(배열의 끝)부터 감소하며 순회하는 이유는 끝에 정렬된 값을 다음 루프에서 포함시키지 않게 하기 위함.
그렇지 않으면 정렬된 끝 값에 상관없이 모든 루프를 돌게 되거나, 끝 값이 undefiend와 비교되는 것을 방지할 수 있다.
function bubbleSort(arr) {
for (var i = arr.length - 1; i >= 0; i--) {
for (var j = 0; j <= arr.length; j++) {
console.log(arr[j], arr[j + 1]);
if (arr[j] > arr[j + 1]) {
let tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
return arr;
}
const arr = [4, 24, 52, 34, 34, 54, 63, 24, 543, 3432, 52];
bubbleSort(arr);
최적화
거의 정렬된 데이터이거나, 정렬이 완료된 데이터는 버블 정렬을 적용할 필요가 없다.
그러나 위 코드처럼 배열의 길이만큼 반복문을 순회하게 해놓으면 손실이 발생하게 된다. 따라서 정렬이 완료된 시점을 파악하여 남은 반복문을 처리하지 않고 결과값을 배열할 수 있을 듯 하다.
가령 초기값이 True인 Boolean 타입인 noSwap 변수가 있다고 해보자.
원소 교환이 이루어질 때마다 False로 변경되고, 내부 반복문을 한 차례 순회한 경우 다시 True로 돌아간다.
내부 반복문에서 값을 순회했지만 원소를 교환하지 않은 경우 정렬이 완료되었음을 의미하며, noSwap 변수 또한 여전히 True이기 때문에 루프를 탈출시켜주는 방법으로 효율적인 버블정렬을 구현할 수 있다.
