삽입 정렬
배열을 정렬하는 매우 간단한 비교 정렬입니다. 비교 정렬 정렬하려는 현재 값을 배열의 다른 값과 비교합니다. 한 번에 하나의 항목으로 작동하며 필요한 정렬된 배열을 얻기 위해 각 항목을 올바른 위치에 반복적으로 배치합니다.
실제로 삽입 정렬은 힙 정렬과 같은 일부 고급 알고리즘만큼 효율적이지 않습니다. 또는 병합 정렬 . 큰 프로그램을 다룰 때는 최선의 선택이 아닙니다. 숨겨진 상수 값이 낮기 때문에 , 삽입 정렬은 작은 배열을 처리하는 동안 힙 또는 빠른 정렬과 같은 일부 고급 알고리즘보다 성능이 뛰어납니다. .
삽입 정렬 배열 위에서 왼쪽에서 오른쪽으로 이동하여 작동합니다. 현재 항목을 사용합니다. '키'로 키가 실제로 있어야 하는 위치를 찾기 위해 해당 키의 왼쪽에 있는 값을 검색합니다.
알고리즘
다음 예에서 주어진 배열은 0,-3,5,8,2,7,6입니다.
- 반복 0 - 첫 번째 반복에서는 0,-3,5,8,2,7,6인 실제 정렬되지 않은 배열만 있습니다.
- 반복 1 - 이 반복에서 키는 -3인 인덱스 1의 값입니다. 삽입 정렬은 키를 해당 키의 왼쪽에 있는 값과 비교하고 프로세스를 진행합니다. -3은 0보다 작기 때문에 배열을 -3,0,5,8,2,7,6으로 지정하여 0의 왼쪽으로 이동합니다.
- 반복 2 - 여기서 키는 5(인덱스 2의 값)입니다. 왼쪽의 -3 및 0 값과 비교되어 정렬된 값에 배치됩니다. 따라서 반복 2 이후의 배열은 -3,0,5,8,2,7,6입니다.
- 반복 3 - 이 반복에서 키 값 8은 왼쪽에 있는 요소와 비교되고 최종 배열은 -3,0,5,8,2,7,6이 됩니다.
- 반복 4 - 이 반복에서 키 값 2는 왼쪽에 있는 값과 비교되고 정렬된 위치에 배치됩니다. 따라서 반복 4 이후의 최종 배열은 -3,0,2,5,8,7,6입니다.
같은 방식으로 최종 반복이 끝나면 정렬된 배열은 -3,0,2,5,6,7,8이 됩니다.
예
<html>
<head>
<script>
function iSort(array) {
for (var p = 1; p < array.length; p++) {
if (array[p] < array[0]){
array.unshift(array.splice(p,1)[0]);
}
else if (array[p] > array[p-1]){
continue;
}
else {
for (var q = 1; q < p; q++) {
if (array[p] > array[q-1] && array[p] < array[q]){
array.splice(q,0,array.splice(p,1)[0]);
}
}
}
}
return array;
}
document.write(iSort([0,-3,5,8,2,7,6]));
</script>
</body>
</html> 출력
-3,0,2,5,6,7,8