[JavaScript] 정렬 알고리즘 - 버블 정렬, 선택 정렬, 삽입 정렬

개요

 

JavaScript는 기본적으로 Array.prototype.sort() 메서드가 존재해서 정렬 알고리즘을 사용할 필요가 없지만, 메서드에 의존하기 보다는 컴퓨팅 사고를 통해서 정렬하는 방법을 알아보고자 한다. 해당 정렬을 프로그래머스 Lv0. 중앙값 구하기 문제에 적용하고자 한다.

 

> 중앙값 구하기 문제 풀이 바로가기

GitHub - cham-min/Algorithm: 알고리즘 공부 저장소

 

---

 

1. 버블 정렬 (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]];
              let temp = arr[j];
              arr[j] = arr[j+1];
              arr[j+1] = temp;
            }
        }
    }
    return arr;
}

 

---

 

2. 선택 정렬(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]];
        let temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
    return arr;
}

 

---

 

3. 삽입 정렬(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;
}

 

---

 

Ref

 

• Visualgo

 

---