삽입 정렬

삽입정렬이란?

데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘입니다.

뒤섞여있는 트럼프 카드를 순서대로 정리하는 모습과 비슷합니다.

데이터 집합에서 요소를 하나씩 뽑아 적절한 곳에 끼워 넣는 것을 반복하여 정렬된 데이터 집합을 찾아냅니다.

버블정렬은 반드시 모든 반복에 대해서 비교를 거치지만 삽입 정렬은 데이터 집합이 정렬되어 있는 경우에는 한번도 비교를 거치지 않습니다.

var array= [1,9,-1,5,10,23,-2,7,4,5]; for (i = 0; i < array.length; i++) { temp = array[i]; j = i; while((j > 0) && (array[j-1] > temp)) { array[j] = array[j-1]; j--; } array[j] = temp; } console.log(array);

정렬이 된 부분은 다시 비교를 하지 않아 버블 정렬보다 빠르며

비교적 크기가 작은 데이터 집합을 정렬하는 루틴을 작성할 때, 정렬 대신 삽입 정렬을 사용할 것을 권합니다.