[알고리즘] 정렬 알고리즘(1) by javascript - Bubble(버블), Selection(선택), Insertion(삽입)

알고리즘을 배우게 되면 머리에 가장 오래 남아있던 그 정렬 알고리즘에 대해 알아보자.

사실 javascript에서는 Array.prototype.sort()라는 배열 메서드가 존재해서 굳이 정렬 알고리즘을 알아야 되나 싶기도 한데, 알아둬서 나쁠 건 없다고 생각된다.

 

정렬의 동작 원리는 아래 사이트를 통해 보면 이해하기 쉽다.

(싱가폴 대학(?)에서 만든 학습용 사이트라는데 시각적으로 표현되어 있어서 보기 좋다.)

https://visualgo.net/en/sorting

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

---

1. 버블 정렬 (Bubble Sort)

버블 정렬 (Bubble Sort)은 매번 연속된 두 개 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방법이다.

성능이 매우 안좋은 정렬이기 때문에 잘 사용되지는 않는다.

 

▷ 버블 정렬(Bubble Sort) 알고리즘 구현

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

bubbleSort([3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]);
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

단순히 이중 반복문을 돌려 스왑 해주며 정렬해주는 코드이다.

---

2. 선택 정렬 (Selection Sort)

선택 정렬 (Selection Sort)은 가장 작은 값을 탐색한다음 그 값을 정렬이 안된 배열의 맨 앞에 위치한 값과 교체하는 알고리즘이다.

 

▷ 선택 정렬(Selection Sort) 알고리즘 구현

const selectionSort = (arr) => {
    for(let i = 0 ; i < arr.length; i++){
        let min = i;
        for(let j = i + 1 ; j < arr.length; j++){
            if(arr[j] < arr[min]) min = j;
        }
        [arr[i], arr[min]] = [arr[min], arr[i]];
    }
    return arr;
}

selectionSort([2, 4, 33, 17, 8, 45, 1, 7, 10, 37]);
// [1, 2, 4, 7, 8, 10, 17, 33, 37, 45]

i라는 시작점을 두고 j반복문을 돌려 최솟값을 찾아 시작점과 교체해주는 반복을 거쳐서 정렬해주는 방식이다.

---

3. 삽입 정렬 (Insertion Sort)

삽입 정렬 (Insertion Sort)은 아직 정렬되지 않은 임의의 데이터를 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

 

▷ 삽입 정렬(Insertion  Sort) 알고리즘 구현

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

insertionSort([10, 34, 45, 50, 8, 48, 14, 41, 43, 1, 46, 9, 7, 25, 36])
// [1, 7, 8, 9, 10, 14, 25, 34, 36, 41, 43, 45, 46, 48, 50]

삽입 정렬은 본문 초반에 알려준 visualgo.net을 꼭 들어가서 동작 원리를 살펴보길 바란다.

i의 방향은 오른쪽 j의 방향은 왼쪽으로 서로 반대방향을 가리킨다.

 

i의 기준이 되는 배열 값을 하나 담아두고

기준의 왼쪽 방향 즉, j 방향으로 하나씩 당겨주면서 정렬을 실시한다.

 

그러다가 i의 기준이 되는 배열 값의 적절한 위치에 도착하면 그 위치에 값을 넣어주는 형식이다.

---

참고 : 위키백과 - 거품 정렬

거품 정렬 - 위키백과, 우리 모두의 백과사전

참고 : 위키백과 - 선택 정렬

선택 정렬 - 위키백과, 우리 모두의 백과사전

참고 : 위키백과 - 삽입 정렬

삽입 정렬 - 위키백과, 우리 모두의 백과사전