[Algorithm] 삽입 정렬(insert sort) Javascript 구현하기

 

삽입정렬(Insert Sort)란?

 

정렬 알고리즘 중 하나다. 데이터들의 위치를 기준으로 좌측에 요소들과 비교를 진행하면서 위치를 찾아나가는 방식이다. 선택 정렬과 다르게 삽입정렬은 좌측 데이터와 비교해야 하기 때문에, 2번째 요소부터 비교하기 시작한다. 만약 좌측 데이터보다 작은 경우 좌측에 데이터를 삽입하고 우측의 데이터들은 우측으로 한칸 밀려난다. 삽입 정렬의 시간복잡도는 O(N^2)이다.

 

예를 들어 아래 배열이 있다고 가정하자.

const arr = [33, 22, 55, 66, 11];

 

먼저 2번째 요소인 22부터 비교를 시작한다. 왼쪽 데이터 33과 비교를 진행한 후 22가 작은 데이터기 때문에 큰 데이터 좌측에 22를 삽입하고 나머지 요소는 index가 1씩 증가한다.

 

다음으로 55를 start 데이터로 잡고 왼쪽 데이터와 비교한다. 큰 값이 존재하지 않기 때문에 skip 된다.

 

마지막으로 11을 start 데이터를 기준으로 왼쪽 데이터들과 비교를 진행한다. 22와 비교했을 때 작은 값이기 때문에 22 데이터 앞에 삽입되고, 우측 데이터들은 1칸씩 뒤로 밀려나게 된다. 오름차순 정렬을 할 때 모든 요소들을 비교하기 때문에 삽입 정렬 알고리즘의 시간복잡도는 O(N^2)이 된다.

 

 

문제

 

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬해서 리턴한다.

 

입출력

입력으로 number 요소를 가지는 1차원 배열과 callback 함수를 입력받는다.

출력값으로 number 타입의 정렬된 배열을 반환한다.

 

 

삽입 정렬 Javascript 구현

 

① 삽입 정렬을 구현하기 위해 2개의 for 반복문을 사용했다.

② 만약 인수로 callback이 제공되면 callback의 결과값으로 비교를 진행한다. 만약 callback이 존재하지 않으면 arr 입력값으로 데이터 비교를 진행한다.

③ 데이터를 특정 위치에 삽입하기 위해서는 Array.prototype.splice() 함수를 사용한다. 특정 index N에 데이터를 삽입하기 위해서는 아래 방식으로 splice() 함수를 사용한다. splice() 함수는 기존 배열을 수정하기 때문에 주의깊게 사용해야 한다.

const arr = [1,2,3,4,5];

// n 번째 위치에 99 데이터 삽입
arr.splice(n, 0, 99);

arr.splice(2, 0, 99); // [1, 2, 99, 3, 4, 5]

 

데이터를 삽입한 후 중복 데이터가 생기기 때문에 기존 비교 데이터를 delete 함수를 사용해 삭제해준다. 

 

const insertionSort = function (arr, cb) {

    // 1. 두번째 위치 부터 좌측 데이터랑 비교함
    for(let i=1; i<arr.length; i++){
      // 4. 더이상 데이터를 찾을 수 없을 때 까지 반복
      for(let j=0; j<i; j++){
        if(cb){
          // 2. 왼쪽에서 큰 값을 찾은 경우 좌측보다 크고 우측보다 작은 위치에 이동
          if(cb(arr[j]) > cb(arr[i])){
            const temp = arr[i]
            // 3. 우측 데이터는 한칸씩 우측으로 이동
            delete arr[i];
            arr.splice(j, 0, temp)
          }
        }else{
          if(arr[j] > arr[i]){

            const temp = arr[i]
            delete arr[i];
            arr.splice(j, 0, temp)
          }
        }
      }
    }
    
    // 5. empty 요소들을 제거해준다.
    const result = [];
    arr.filter((item, idx)=>result.push(arr[idx]));
    return result;
};

 

 

 

 

[Algorithm] treeBFS 알고리즘 Javascript Node.js 구현하기

 

[Algorithm] powerSet 알고리즘,문자열 부분 집합 문제 Javascript, Node.js

[Algorithm] powerSet 알고리즘,문자열 부분 집합 문제 Javascript, Node.js