칸아카데미-삽입정렬 구현 소스

insertion_sort.js

var insert = function(array, rightIndex, value) {
    for(var j = rightIndex;
        j >= 0 && array[j] > value;
        j--) {
        array[j + 1] = array[j];
    }   
    array[j + 1] = value; 
};

var insertionSort = function(array) {
    for(var i=1;i<array.length;i++){
        insert(array,i-1,array[i]);
    }
};
//insert를 호출하여 인덱스 0의 정렬된 하위 배열에 인덱스 1부터 시작하는 요소를 삽입합니다.
//insert를 호출하여 인덱스 0에서 1까지 정렬된 하위 배열에 인덱스 2부터 시작하는 요소를 삽입합니다.
//insert를 호출하여 인덱스 0부터 2까지 정렬된 하위 배열에 인덱스 3부터 시작하는 요소를 삽입합니다.
//…
//마지막으로 insert를 호출하여 인덱스 0에서 n-2 n−2n, minus, 2까지 정렬된 하위 배열에 인덱스 n-1 n−1n, minus, 1부터 시작하는 요소를 삽입합니다.

var array = [22, 11, 99, 88, 9, 7, 42];
insertionSort(array);
println("Array after sorting:  " + array);
Program.assertEqual(array, [7, 9, 11, 22, 42, 88, 99]);

var array = [67,52,99,0,100,1,41,-10,-14,-5];
insertionSort(array);
println("Array after sorting:  " + array);
Program.assertEqual(array, [-14,-10,-5,0,1,41,52,67,99,100]);