거품 정렬 ( bubble sort )

거품 정렬 ( bubble sort )

거품 정렬이란?

거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

이전 게시물까지는 한글로 정렬 이름을 불렀는데, 거품 정렬은 어감이 뭔가 어색해서 다음부터는 버블 소트라고 해야겠다ㅋㅋ

버블 소트는 다음과 같이 작동한다.

1. 배열의 원소를 두개씩 순서대로 비교하며 앞의 원소가 더 크다면 뒤의 원소와 자리를 바꾼다.
2. 한번 배열을 돌고나면 최소 마지막 한개는 정렬이 완료된다.
3. 배열 전체가 정렬이 될 때까지 반복문을 돌려 리턴.

코드와 설명

const bubbleSort = arr => {
    let temp;
    for ( let i = 0; i < arr.length-1; i++ ) { // 배열의 첫번째 부터 마지막에서 하나 전까지 돌게하는 반복문
        for ( let j = 0; j < arr.length-1-i; j++ ) { // 원소를 두개씩 비교해주는 반복문
            if ( arr[j] > arr[j+1] ) {
                temp = arr[j];  // 세줄로 i번째와 i+1번째 위치를 바꿔줌
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
}

console.log(bubbleSort([3,4,1,2]))

보다시피 코드도 짧고 엄청 쉽지만, 그만큼 성능이 안좋아 실제로는 거의 안쓴다고 보면 된다고 함.

여태 했던 것중에 가장 쉽지만 쓸모없는 정렬 방법