3.삽입 정렬

크기가 n인 배열을 오름차순으로 정렬하려면:

1: 배열에 대해 arr[1]에서 arr[n]까지 반복합니다.

2: 현재 요소(키)를 이전 요소와 비교합니다.

3: 키 요소가 이전 요소보다 작으면 이전 요소와 비교합니다. 더 큰 요소를 한 위치 위로 이동하여 교체된 요소를 위한 공간을 만듭니다.

다른 예:

12, 11, 13, 5, 6

i = 1(배열의 두 번째 요소)에서 4(배열의 마지막 요소) i = 1에 대해 루프를 실행합니다

. 11은 12보다 작으므로 12를 이동하고 삽입합니다. 11 이전 12

11, 12, 13, 5, 6

i = 2. 13은 A[0..I-1]의 모든 요소가 13보다 작기 때문에 해당 위치에 유지됩니다.

11, 12, 13, 5, 6

i = 3. 5는 처음으로 이동하고 11에서 13까지의 다른 모든 요소는 현재 위치보다 한 위치 앞으로 이동합니다.

5, 11, 12, 13, 6

i = 4. 6은 5 이후의 위치로 이동하고 11에서 13까지의 요소는 현재 위치보다 한 위치 앞으로 이동합니다.

5, 6, 11, 12, 13


// Javascript program for insertion sort 
   
// Function to sort an array using insertion sort
function insertionSort(arr, n) 
{ 
    let i, key, j; 
    for (i = 1; i < n; i++)
    { 
        key = arr[i]; 
        j = i - 1; 
   
        /* Move elements of arr[0..i-1], that are 
        greater than key, to one position ahead 
        of their current position */
        while (j >= 0 && arr[j] > key)
        { 
            arr[j + 1] = arr[j]; 
            j = j - 1; 
        } 
        arr[j + 1] = key; 
    } 
} 
   
// A utility function to print an array of size n 
function printArray(arr, n) 
{ 
    let i; 
    for (i = 0; i < n; i++) 
        document.write(arr[i] + " "); 
    document.write("<br>");
} 
   
// Driver code
    let arr = [12, 11, 13, 5, 6 ]; 
    let n = arr.length; 
   
    insertionSort(arr, n); 
    printArray(arr, n);

분할