삽입정렬 자바스크립트

삽입정렬이란?

여러 개의 섞인 숫자가 작은 순서부터 큰 순서로 정렬하는 것이다.

삽입정렬은 첫번째 숫자는 놔두고 두번째 숫자부터 선택해서 첫번째 보다 크면 오른쪽에 작으면 왼쪽에 넣는다.

ex)

위의 사진을 예시로 들면

a. 7부터 시작해서  7이 3보다 크기때문에 제자리에 둔다

b. 2부터 시작해서 7보다 작기때문에 왼쪽으로 이동하고 7은 오른쪽으로 이동한다. 2가 3보다도 작기 때문에 2를 맨 왼  쪽에 두고 2, 3, 7로 둔다.

c. 5부터 시작해서 위의 정렬된 순서대로 3보다 크고 7보다 작기 때문에 사이에 둔다.

f.이와 같은 방법으로 정렬하다보면 맨 왼쪽은 작은 수 오른쪽은 가장 큰 수로 정렬된다.

 

자바스크립트코드

var insertionSort = function(array){
  var i = 1;// 선택할 숫자의 위치
  var k,temp;//뽑은 숫자를 알맞은 위치에 넣을 때 사용할 변수, 뽑은 숫자 값을 저장할 변수
  for(i;i<array.length;i++){
    temp = array[i];//새로운 숫자를 선택해서 temp에 넣는다.
    for(k = i-1; k>=0 && temp< array[k]; k --) { //현재 정렬된 배열은 i-1까지이므로 i-1번째부터 역순으로 조사한다, k값은 음수가 아니여야하고, temp 값보다 정렬된 배열에 있는 값이 크면 k번재를 k+1번째로 이동한다.
      array[k + 1] = array[k];//한칸씩 오른쪽으로 이동한다
    }
    array[k+1] = temp;//마자막 빈 칸에 선택한 숫자를 넣는다.
  }
retrun array;
};
insertionSort([5,1,2,4,3]);

 

장점

 -안정한 정렬 방법.

 -대부분의 수가 정렬되어 있을경우 효율적일 수 있다.

 -적은 수 일 경우 다른 복잡한 정렬방법 보다 효율적일 수 있다.

 

단점

 -레코드들의 많은 이동이 필요하다.

 -레코드 수가 많고 레크드 크키가 클경우 적합하지 않다.