버블정렬을 시작하기 전에 얼마나 다양한 정렬 방법과 각 정렬방법의 장단점을 알고 싶으면 아래 사이트를 확인해보자. 시각적으로 표현되어 흐름을 이해하기 쉽다.
https://www.toptal.com/developers/sorting-algorithms
버블 정렬(bubbleSort)
버블정렬은 사용도가 좋은 방법은 아니지만 다른 정렬이 얼마나 효율적인지 알기 위해 정리해본다.
버블정렬은 간단히 얘기해서 배열에서 두개씩 값을 비교하여 가장 큰 값을 제일 오른쪽에 보내는 방법이라 보면 된다.
한 번 반복문을 돌면 이렇게 배열에 마지막에 가장 큰 값이 오게 된다.
그럼 5를 제외하고 다시 반복문으로 비교를 진행하고 나머지 중에 가장 큰 값인 4가 5에 앞으로 오게 된다.
이렇게 반복하면,
[3, 4, 1, 2, 5]
[3, 1, 2, 4, 5]
[1, 2, 3, 4, 5]
세번의 반복문으로 오름차순 정렬이 된다.
아래는 실제 코드를 작성한 부분이다.
function bubbleSort(arr){
for(let i = arr.length; i > 0; i--){ // 마지막에 최대값이 있기 때문에 반복문에서 제외시킨다.
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;
}
}
}
return arr;
}첫번째 반복문은 비교할 전체 길이를 줄여주는 구문이라 보면 된다.
배열의 맨 마지막 값에 최대값이 오기 때문에 내부에 비교 반복문이 끝날 때마다 배열의 길이를 줄여준다.
위 내용을 조금 더 모던하게 바꾸면 아래처럼 된다.
function bubbleSort(arr) {
const swap = (arr, idx1, idx2) => { // 구조분해할당을 통해 swap 함수를 만들었다.
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};
for (let i = arr.length; i > 0; i--) {
for (let j = 0; j < i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1); // 함수 실행.
}
}
}
return arr;
}
여기서 더 나아가면 특별한 경우를 생각해 볼 수 있다.
만약, 거의 다 정렬이 된 배열이라면?
[8, 1, 2, 3, 4, 5, 6, 7]
만약 위 같은 배열이라면 1번만 실행하면 정렬이 완료된다.
그러나 프로그램을 알지 못한다. 결론적으로 바꿀 순서가 없는데도 전부 다 비교하기 때문에
길이가 긴 배열이라면 문제가 된다.
이걸 보완해서 만약 비교할 대상이 없을 경우에는 비교 반복문을 중지시키면 된다.
그 방법은 마지막으로 반복문이 실행됐을 때 교환을 했는지 확인하면 된다.
만약 직전에 반복문에서 교환을 하지 않았다면 정렬이 완료됐다는 뜻이기 때문이다.
아래코드를 보자.
function bubbleSort(arr){
let noSwaps; // 확인할 변수 선언
const swap = (arr, idx1, idx2) => {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
noSwaps = false; // 교환 후 noSwaps을 false로 만든다.
};
for(let i = arr.length; i > 0; i--){
noSwaps = true;
for(let j = 0; j < i - 1; j++){
if(arr[j] > arr[j+1]){
swap(arr, j, j+1)
}
}
if(noSwaps) break; // noSwaps가 true면 모든 반복문을 정지한다.
}
return arr;
}
bubbleSort([8,1,2,3,4,5,6,7]);만약 직전 비교 반복문에서 교환을 한번도 하지 않았다면 noSwaps가 true로 유지되면서
break 하게 된다.
여기서 버블정렬의 시간복잡도는 n²이다. 모든 항목에 대해 이중 반복문을 실시하기 때문이다.
따라서 가능한 최고 경우는 이미 정렬된 배열은 O(n)이고 최악은 O(n²)이다.
빅오복잡도는 항상 worst를 생각하기 때문에 버블정렬의 시간복잡도는 n²
여기까지 버블정렬에 대해서 알아보았다.
정렬방법이 아직 많기때문에 일단 가장 기본인 버블부터 확실히 기억하자.
한번 정렬 방법을 익히면 응용해서 만들수 있다.
정렬방법을 하나씩 정리하면서 정렬방법을 마스터 해보자..!!
