버블 정렬, 선택 정렬, 삽입 정렬

 

 

버블 정렬 (Bubble sort)

 

 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않으면 자리를 교환하며 정렬하는 알고리즘.

오름차순의 경우 가장 큰 값을 가장 뒤로 보내며 정렬하고, 내림차순의 경우 가장 작은 값을 가장 뒤로 보내며 정렬한다. 

 

버블 정렬이라는 이름은 원소의 이동이 가벼운 거품이 수면 위로 올라오는 모습과 닮아 붙여진 것이다. 

 

 

버블 정렬 시각화 예시

 

 

// 구현하기

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


// 최적화 (배열 벗어나는 부분은 비교 X, 
// 교환이 이루어지지 않는 경우 이후의 무의미한 과정 제거)

function bubbleSort2(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;
}

 

 

→ 일반적인 시간복잡도가 O(n^2)이므로 잘 사용하지는 않는다. 

 

 

---

 

 

 

선택 정렬 (Selection Sort)

 

 

 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식. 

 

예시 : [5, 3, 4, 1, 2]

(1) [5, 3, 4, 1, 2] 중 최솟값 1을 찾아 제일 앞에 위치한 5와 교환.

(2) [1, 3, 4, 5, 2] 중 최솟값 2를 찾아 제일 앞에 위치한 3과 교환.

(3) [1, 2, 4, 5, 3] 중 최솟값 3을 찾아 제일 앞에 위치한 4와 교환.

(4) [1, 2, 3, 5, 4] 중 최솟값 4를 찾아 제일 앞에 위치한 5와 교환.

=> 결과 : [1, 2, 3, 4, 5]

 

 

선택 정렬 시각화 예시

 

 

// 구현하기

function selectionSort(arr){
    for(let i = 0; i < arr.length; i++){
        let lowest = i;
        for(let j = i + 1; j < arr.length; j++){
            if(arr[j] < arr[lowest]){
                lowest = j;
            }
        }
        if(i !== lowest){
            let temp = arr[i];
            arr[i] = arr[lowest];
            arr[lowest] = temp;
        }
    }
    return arr;
}

 

→ 교환 횟수가 비교적 적다는 점에서 버블 정렬보다 나을 순 있지만, 선택 정렬 또한 일반적인 시간복잡도가 O(n^2)이므로 잘 사용하지는 않는다. 

 

 

---

 

 

 

삽입 정렬 (Insertion Sort)

 

 

 이미 정렬되어 있는 앞 부분과 비교하여 자신의 위치를 찾아 삽입하는 방식. 

 

예시 : [5, 3, 4, 1, 2]

(1) [5, 3, 4, 1, 2] 3을 앞의 배열 5에 넣어 정렬.

(2) [3, 5, 4, 1, 2] 4를 앞의 배열 3, 5에 넣어 정렬.

(3) [3, 4, 5, 1, 2] 1을 앞의 배열 3, 4, 5에 넣어 정렬.

(4) [1, 3, 4, 5, 2] 2를 앞의 배열 1, 3, 4, 5에 넣어 정렬

=> 결과 : [1, 2, 3, 4, 5]

 

 

삽입 정렬 시각화 예시

 

 

// 구현하기

function insertionSort(arr){
    for(let i = 1; i < arr.length; i++){
        let currentVal = arr[i];
        for(let j = i - 1; j >= 0 && arr[j] > currentVal; j--){
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = currentVal;
    }
    return arr;
}

//        <----------
// 예시 :[2, 1, 9, 76, 4]
// (1) currentVal === 1, [2, 2, 9, 76, 4] -> [1, 2, 9, 76, 4]
// (2) currentVal === 9
//     currentVal === 76
//     currentVal === 4, [1, 2, 9, 76, 76] -> [1, 2, 4, 9, 76]

 

→ 버블 정렬, 선택 정렬과 마찬가지로 일반적인 시간복잡도가 O(n^2)이지만, 주어진 데이터가 어느 정도 정렬되어 있는 경우 좀 더 효율적이다. 

 

 

 

---

 

버블, 선택, 삽입 정렬 비교

 

-> 이 세 가지 알고리즘은 배열의 길이가 짧은 경우 더 유리할 수 있다.

 

 

 

 

 

[ 참고 자료 ]

 

- JavaScript 알고리즘 & 자료구조 마스터 클래스

https://www.udemy.com/course/best-javascript-data-structures/

 

- https://visualgo.net/en/sorting

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo