[정렬] 버블 정렬

가장 간단한 정렬 알고리즘 중 버블정렬에 대해 알아보도록 하자

데이터의 인접 요소끼리 비교하고, 스왑 연산을 수행하며 정렬하는 방식

• 최상의 경우 : O(n)
• 최악의 경우 : O(n^2)

출처 :  [JS/Sorting] 버블 정렬, 삽입 정렬, 선택 정렬 자바스크립트로 구현하기 (Bubble Sort, Insertion Sort, Selection Sort in JavaScript) :: Code Playground (tistory.com)

Bubble Sort

데이터가 이미 정렬되어 있는 경우에는 한번의 순회로 정렬이 가능하나, 그렇지 않다면 각 자리를 찾기 위해 n번 동안 n번 값을 찾아야한다.

function bubbleSort(arr) {
        for (let i = 0; i < arr.length; i++) {
            let swap;
            for (let j = i + 1; j < arr.length; j++) {
                if(arr[i] > arr[j]) {
                    swap = arr[i];
                    arr[i] = arr[j];
                    arr[j] = swap;
                }
            }
        }
        return arr;
    }