이진 삽입 정렬은 다음과 유사한 정렬 알고리즘입니다. 삽입 정렬 , 그러나 요소를 삽입해야 하는 위치를 찾기 위해 선형 검색을 사용하는 대신 다음을 사용합니다. 이진 검색 . 따라서 단일 요소를 삽입하는 비교 값을 O(N)에서 O(log N)로 줄입니다.

이는 유연한 알고리즘입니다. 즉, 동일한 특정 멤버가 이미 심하게 정렬되어 있는 경우, 즉 기능의 현재 위치가 정렬된 목록의 실제 위치에 더 가까운 경우 더 빠르게 작동한다는 의미입니다.

이는 안정적인 필터링 알고리즘입니다. 동일한 값을 가진 요소는 첫 번째 목록에 있었던 것과 동일한 마지막 순서로 동일한 순서로 나타납니다.

이진 삽입 정렬의 응용:

• 이진 삽입 정렬은 배열의 항목 수가 적을 때 가장 잘 작동합니다.
• 빠른 정렬이나 병합 정렬을 수행할 때 하위 배열 크기가 작아지면(예: <= 25개 요소) 이진 삽입 정렬을 사용하는 것이 가장 좋습니다.
• 이 알고리즘은 키 간 비교 비용이 충분히 높을 때도 작동합니다. 예를 들어 여러 문자열을 필터링하려는 경우 두 문자열의 비교 성능이 더 높아집니다.

이진 삽입 정렬은 어떻게 작동하나요?

• 이진 삽입 정렬 모드에서는 동일한 멤버를 필터링된 하위 배열과 필터링되지 않은 하위 배열로 나눕니다. 동일한 멤버의 첫 번째 요소는 구성된 하위 배열에 있고 다른 모든 요소는 계획되지 않았습니다.
• 그런 다음 두 번째 요소부터 마지막 ​​요소까지 반복합니다. i번째를 반복하면서 현재 객체를 키로 만듭니다. 이 키는 아래의 기존 목록에 추가해야 하는 기능입니다.
• 이를 위해 먼저 아래 정렬된 하위 배열에 대해 이진 검색을 사용하여 키보다 큰 요소의 위치를 ​​찾습니다. 이 위치를 pos라고 부르자. 그런 다음 모든 요소를 ​​pos에서 1로 오른쪽으로 이동하고 Array[pos] = key를 생성했습니다.
• 모든 i번째 곱셈에서 (i – 1)까지 배열의 왼쪽 부분이 이미 정렬되어 있음을 알 수 있습니다.

이진 삽입 정렬을 구현하는 방법:

• 두 번째 요소부터 마지막 ​​요소까지 배열을 반복합니다.
• 현재 요소 A[i]를 변수 키에 저장합니다.
• 이진 검색을 사용하여 A[0]부터 A[i-1]까지 하위 배열에서 A[i]보다 조금 더 큰 요소의 위치를 ​​찾습니다. 이 요소가 인덱스 위치에 있다고 가정해 보겠습니다.
• 인덱스 pos에서 i-1까지의 모든 요소를 ​​오른쪽으로 이동합니다.
• A[pos] = 열쇠.

다음은 위의 접근 방식을 구현한 것입니다.

C++

// C program for implementation of> // binary insertion sort> #include> using> namespace> std;> // A binary search based function> // to find the position> // where item should be inserted> // in a[low..high]> int> binarySearch(> int> a[],> int> item,> > int> low,> int> high)> {> > if> (high <= low)> > return> (item>a[낮음]) ?> > (low + 1) : low;> > int> mid = (low + high) / 2;> > if> (item == a[mid])> > return> mid + 1;> > if> (item>a[중간])> > return> binarySearch(a, item,> > mid + 1, high);> > return> binarySearch(a, item, low,> > mid - 1);> }> // Function to sort an array a[] of size 'n'> void> insertionSort(> int> a[],> int> n)> {> > int> i, loc, j, k, selected;> > for> (i = 1; i { j = i - 1; selected = a[i]; // find location where selected should be inserted loc = binarySearch(a, selected, 0, j); // Move all elements after location to create space while (j>= loc) { a[j + 1] = a[j]; 제이--; } a[j + 1] = 선택됨; } } // 드라이버 코드 int main() { int a[] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = sizeof(a) / sizeof(a[0]), i; 삽입정렬(a, n); 시합 < <'Sorted array: '; for (i = 0; i cout < <' ' < < a[i]; return 0; } // this code is contribution by shivanisinghss2110>

씨

// C program for implementation of> // binary insertion sort> #include> // A binary search based function> // to find the position> // where item should be inserted> // in a[low..high]> int> binarySearch(> int> a[],> int> item,> > int> low,> int> high)> {> > if> (high <= low)> > return> (item>a[낮음]) ?> > (low + 1) : low;> > int> mid = (low + high) / 2;> > if> (item == a[mid])> > return> mid + 1;> > if> (item>a[중간])> > return> binarySearch(a, item,> > mid + 1, high);> > return> binarySearch(a, item, low,> > mid - 1);> }> // Function to sort an array a[] of size 'n'> void> insertionSort(> int> a[],> int> n)> {> > int> i, loc, j, k, selected;> > for> (i = 1; i { j = i - 1; selected = a[i]; // find location where selected should be inserted loc = binarySearch(a, selected, 0, j); // Move all elements after location to create space while (j>= loc) { a[j + 1] = a[j]; 제이--; } a[j + 1] = 선택됨; } } // 드라이버 코드 int main() { int a[] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = sizeof(a) / sizeof(a[0]), i; 삽입정렬(a, n); printf('정렬된 배열: '); for (i = 0; i printf('%d ', a[i]); return 0; }>

자바

// Java Program implementing> // binary insertion sort> import> java.util.Arrays;> class> GFG> {> > > public> static> void> main(String[] args)> > {> > final> int> [] arr = {> 37> ,> 23> ,> 0> ,> 17> ,> 12> ,> 72> ,> > 31> ,> 46> ,> 100> ,> 88> ,> 54> };> > new> GFG().sort(arr);> > for> (> int> i => 0> ; i System.out.print(arr[i] + ' '); } // Driver Code public void sort(int array[]) { for (int i = 1; i { int x = array[i]; // Find location to insert // using binary search int j = Math.abs( Arrays.binarySearch(array, 0, i, x) + 1); // Shifting array to one // location right System.arraycopy(array, j, array, j + 1, i - j); // Placing element at its // correct location array[j] = x; } } } // Code contributed by Mohit Gupta_OMG>

파이썬3

# Python Program implementation> # of binary insertion sort> def> binary_search(arr, val, start, end):> > > # we need to distinguish whether we> > # should insert before or after the> > # left boundary. imagine [0] is the last> > # step of the binary search and we need> > # to decide where to insert -1> > if> start> => => end:> > if> arr[start]>값:> > return> start> > else> :> > return> start> +> 1> > # this occurs if we are moving> > # beyond left's boundary meaning> > # the left boundary is the least> > # position to find a number greater than val> > if> start>끝:> > return> start> > mid> => (start> +> end)> /> /> 2> > if> arr[mid] return binary_search(arr, val, mid+1, end) elif arr[mid]>val: return binary_search(arr, val, start, mid-1) else: return mid def insert_sort(arr): for i in range(1, len(arr)): val = arr[i] j = binary_search(arr, val, 0, i-1) arr = arr[:j] + [val] + arr[j:i] + arr[i+1:] return arr print('정렬된 배열:') print(insertion_sort( [37, 23, 0, 31, 22, 17, 12, 72, 31, 46, 100, 88, 54])) # 코드 제공: Mohit Gupta_OMG>

씨#

// C# Program implementing> // binary insertion sort> using> System;> class> GFG {> > public> static> void> Main()> > {> > int> [] arr = { 37, 23, 0, 17, 12, 72,> > 31, 46, 100, 88, 54 };> > sort(arr);> > for> (> int> i = 0; i Console.Write(arr[i] + ' '); } // Driver Code public static void sort(int[] array) { for (int i = 1; i { int x = array[i]; // Find location to insert using // binary search int j = Math.Abs( Array.BinarySearch(array, 0, i, x) + 1); // Shifting array to one location right System.Array.Copy(array, j, array, j + 1, i - j); // Placing element at its correct // location array[j] = x; } } } // This code is contributed by nitin mittal.>

PHP

// PHP program for implementation of // binary insertion sort // A binary search based function to find // the position where item should be // inserted in a[low..high] function binarySearch($a, $item, $low, $high) { if ($high <= $low) return ($item>$a[$low]) ? ($낮음 + 1) : $낮음; $mid = (int)(($low + $high) / 2); if($item == $a[$mid]) return $mid + 1; if($item> $a[$mid]) return BinarySearch($a, $item, $mid + 1, $high); return BinarySearch($a, $item, $low, $mid - 1); } // 'n' 크기의 배열 a를 정렬하는 함수 function insertSort(&$a, $n) { $i; $loc; $j; $k; $선택됨; for ($i = 1; $i <$n; ++$i) { $j = $i - 1; $selected = $a[$i]; // find location where selected // item should be inserted $loc = binarySearch($a, $selected, 0, $j); // Move all elements after location // to create space while ($j>= $loc) { $a[$j + 1] = $a[$j]; $j--; } $a[$j + 1] = $선택됨; } } // 드라이버 코드 $a = array(37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54); $n = 크기($a); 삽입정렬($a, $n); echo '정렬된 배열: '; ($i = 0; $i <$n; $i++) echo '$a[$i] '; // This code is contributed by // Adesh Singh ?>>

자바스크립트

> // Javascript Program implementing> // binary insertion sort> function> binarySearch(a, item, low, high)> {> > > if> (high <= low)> > return> (item>a[낮음]) ?> > (low + 1) : low;> > > mid = Math.floor((low + high) / 2);> > > if> (item == a[mid])> > return> mid + 1;> > > if> (item>a[중간])> > return> binarySearch(a, item,> > mid + 1, high);> > > return> binarySearch(a, item, low,> > mid - 1);> }> function> sort(array)> {> > for> (let i = 1; i { let j = i - 1; let x = array[i]; // Find location to insert // using binary search let loc = Math.abs( binarySearch(array, x, 0, j)); // Shifting array to one // location right while (j>= loc) { 배열[j + 1] = 배열[j]; 제이--; } // 요소를 // 올바른 위치에 배치 array[j+1] = x; } } // 드라이버 코드 let arr=[ 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54]; 정렬(arr); for (let i = 0; i document.write(arr[i] + ' '); // 이 코드는known2108에 의해 제공되었습니다. // 이진 삽입 정렬 #include 구현을 위한 C 프로그램 // 이진 검색 // 기반 함수 // 항목을 삽입해야 하는 위치를 찾기 위한 // // in a[low..high] int BinarySearch(int a[], int item, int low, int high) { if (high) <= low) return (item>a[낮음]) ? (낮음 + 1) : 낮음; int mid = (낮음 + 높음) / 2; if (item == a[mid]) return mid + 1; if (item> a[mid]) return binarySearch(a, item, mid + 1, high); return BinarySearch(a, 항목, 낮음, 중간 - 1); } // 'n' 크기의 배열 a[]를 정렬하는 함수 void insertSort(int a[], int n) { int i, loc, j, k, selected; for (i = 1; i { j = i - 1; selected = a[i]; // selected를 삽입해야 할 위치를 찾습니다. loc = binarySearch(a, selected, 0, j); // 위치 뒤의 모든 요소를 ​​이동합니다. 공간을 생성하려면 while (j>= loc) { a[j + 1] = a[j]; j-- } a[j + 1] = selected } } // 드라이버 코드 int main() { int a [] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 } int n = sizeof(a) / sizeof(a[0]), i; ); printf('정렬된 배열: '); for (i = 0; i printf('%d ', a[i]); r// 이진 삽입 정렬을 구현하기 위한 C 프로그램 #include // 이진 검색 기반 함수 // 항목을 삽입해야 하는 // 위치를 찾는 // in a[low..high] int BinarySearch(int a[], int item, int low, int high) { 만약 (높다면 <= low) return (item>a[낮음]) ? (낮음 + 1) : 낮음; int mid = (낮음 + 높음) / 2; if (item == a[mid]) return mid + 1; if (item> a[mid]) return binarySearch(a, item, mid + 1, high); return BinarySearch(a, 항목, 낮음, 중간 - 1); } // 'n' 크기의 배열 a[]를 정렬하는 함수 void insertSort(int a[], int n) { int i, loc, j, k, selected; for (i = 1; i { j = i - 1; selected = a[i]; // selected를 삽입해야 하는 위치를 찾습니다. loc = binarySearch(a, selected, 0, j); // 위치 뒤의 모든 요소를 ​​이동합니다. 공간을 생성하려면 while (j>= loc) { a[j + 1] = a[j]; j-- } a[j + 1] = selected } } // 드라이버 코드 int main() { int a [] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 } int n = sizeof(a) / sizeof(a[0]), i; ); printf('정렬된 배열: '); for (i = 0; i printf('%d ', a[i]); // 바이너리 삽입 정렬 구현을 위한 C 프로그램 # include // 이진 검색 기반 함수 // 항목을 삽입해야 하는 // 위치를 찾기 위한 // in a[low..high] int BinarySearch(int a[], int item, int low, int high) { if (높은 <= low) return (item>a[낮음]) ? (낮음 + 1) : 낮음; int mid = (낮음 + 높음) / 2; if (item == a[mid]) return mid + 1; if (item> a[mid]) return binarySearch(a, item, mid + 1, high); return BinarySearch(a, 항목, 낮음, 중간 - 1); } // 'n' 크기의 배열 a[]를 정렬하는 함수 void insertSort(int a[], int n) { int i, loc, j, k, selected; for (i = 1; i { j = i - 1; selected = a[i]; // selected를 삽입해야 하는 위치를 찾습니다. loc = binarySearch(a, selected, 0, j); // 위치 뒤의 모든 요소를 ​​이동합니다. 공간을 생성하려면 while (j>= loc) { a[j + 1] = a[j]; j-- } a[j + 1] = selected } } // 드라이버 코드 int main() { int a [] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 } int n = sizeof(a) / sizeof(a[0]), i; ); printf('정렬된 배열: '); for (i = 0; i printf('%d ', a[i]); // 바이너리 삽입 정렬 구현을 위한 C 프로그램 # include // 이진 검색 기반 함수 // 항목을 삽입해야 하는 // 위치를 찾기 위한 // in a[low..high] int BinarySearch(int a[], int item, int low, int high) { if (높은 <= low) return (item>a[낮음]) ? (낮음 + 1) : 낮음; int mid = (낮음 + 높음) / 2; if (item == a[mid]) return mid + 1; if (item> a[mid]) return binarySearch(a, item, mid + 1, high); return BinarySearch(a, 항목, 낮음, 중간 - 1); } // 'n' 크기의 배열 a[]를 정렬하는 함수 void insertSort(int a[], int n) { int i, loc, j, k, selected; for (i = 1; i { j = i - 1; selected = a[i]; // selected를 삽입해야 할 위치를 찾습니다. loc = binarySearch(a, selected, 0, j); // 위치 뒤의 모든 요소를 ​​이동합니다. 공간을 생성하려면 while (j>= loc) { a[j + 1] = a[j]; j-- } a[j + 1] = selected } } // 드라이버 코드 int main() { int a [] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 } int n = sizeof(a) / sizeof(a[0]), i; ); printf('정렬된 배열: '); for (i = 0; i printf('%d ', a[i]); // 바이너리 삽입 정렬 구현을 위한 C 프로그램 # include // 이진 검색 기반 함수 // 항목을 삽입해야 하는 // 위치를 찾기 위한 // in a[low..high] int BinarySearch(int a[], int item, int low, int high) { if (높은 <= low) return (item>a[낮음]) ? (낮음 + 1) : 낮음; int mid = (낮음 + 높음) / 2; if (item == a[mid]) return mid + 1; if (item> a[mid]) return binarySearch(a, item, mid + 1, high); return BinarySearch(a, 항목, 낮음, 중간 - 1); } // 'n' 크기의 배열 a[]를 정렬하는 함수 void insertSort(int a[], int n) { int i, loc, j, k, selected; for (i = 1; i { j = i - 1; selected = a[i]; // selected를 삽입해야 하는 위치를 찾습니다. loc = binarySearch(a, selected, 0, j); // 위치 뒤의 모든 요소를 ​​이동합니다. 공간을 생성하려면 while (j>= loc) { a[j + 1] = a[j]; j-- } a[j + 1] = selected } } // 드라이버 코드 int main() { int a [] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 } int n = sizeof(a) / sizeof(a[0]), i; ); printf('정렬된 배열: '); for (i = 0; i printf('%d ', a[i]);// 바이너리 삽입 정렬 구현을 위한 C 프로그램 # include // 이진 검색 기반 함수 // 항목을 삽입해야 하는 // 위치를 찾기 위한 // in a[low..high] int BinarySearch(int a[], int item, int low, int high) { if (높은 <= low) return (item>a[낮음]) ? (낮음 + 1) : 낮음; int mid = (낮음 + 높음) / 2; if (item == a[mid]) return mid + 1; if (item> a[mid]) return binarySearch(a, item, mid + 1, high); return BinarySearch(a, 항목, 낮음, 중간 - 1); } // 'n' 크기의 배열 a[]를 정렬하는 함수 void insertSort(int a[], int n) { int i, loc, j, k, selected; for (i = 1; i { j = i - 1; selected = a[i]; // selected를 삽입해야 하는 위치를 찾습니다. loc = binarySearch(a, selected, 0, j); // 위치 뒤의 모든 요소를 ​​이동합니다. 공간을 생성하려면 while (j>= loc) { a[j + 1] = a[j]; j-- } a[j + 1] = selected } } // 드라이버 코드 int main() { int a [] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 } int n = sizeof(a) / sizeof(a[0]), i; ); printf('정렬된 배열: '); for (i = 0; i printf('%d ', a[i])>

산출

Sorted array: 0 12 17 23 31 37 46 54 72 88 100 

시간 복잡도: 알고리즘 전체는 여전히 O(n)의 최악의 실행 시간을 갖습니다. ² ) 각 삽입에 필요한 일련의 교체로 인해.

또 다른 접근법: 다음은 위의 재귀 코드를 반복적으로 구현한 것입니다.

C++

#include> using> namespace> std;> // iterative implementation> int> binarySearch(> int> a[],> int> item,> int> low,> int> high)> {> > while> (low <= high) {> > int> mid = low + (high - low) / 2;> > if> (item == a[mid])> > return> mid + 1;> > else> if> (item>a[중간])> > low = mid + 1;> > else> > high = mid - 1;> > }> > return> low;> }> // Function to sort an array a[] of size 'n'> void> insertionSort(> int> a[],> int> n)> {> > int> i, loc, j, k, selected;> > for> (i = 1; i j = i - 1; selected = a[i]; // find location where selected should be inserted loc = binarySearch(a, selected, 0, j); // Move all elements after location to create space while (j>= loc) { a[j + 1] = a[j]; 제이--; } a[j + 1] = 선택됨; } } // 드라이버 코드 int main() { int a[] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = sizeof(a) / sizeof(a[0]), i; 삽입정렬(a, n); 시합 < <'Sorted array: '; for (i = 0; i cout < <' ' < < a[i]; return 0; } // This code is contributed by shivanisinghss2110.>

씨

#include> // iterative implementation> int> binarySearch(> int> a[],> int> item,> int> low,> int> high)> {> > while> (low <= high) {> > int> mid = low + (high - low) / 2;> > if> (item == a[mid])> > return> mid + 1;> > else> if> (item>a[중간])> > low = mid + 1;> > else> > high = mid - 1;> > }> > return> low;> }> // Function to sort an array a[] of size 'n'> void> insertionSort(> int> a[],> int> n)> {> > int> i, loc, j, k, selected;> > for> (i = 1; i j = i - 1; selected = a[i]; // find location where selected should be inserted loc = binarySearch(a, selected, 0, j); // Move all elements after location to create space while (j>= loc) { a[j + 1] = a[j]; 제이--; } a[j + 1] = 선택됨; } } // 드라이버 코드 int main() { int a[] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = sizeof(a) / sizeof(a[0]), i; 삽입정렬(a, n); printf('정렬된 배열: '); for (i = 0; i printf('%d ', a[i]); return 0; } // tmeid에서 기여>

자바

import> java.io.*;> class> GFG {> // iterative implementation> static> int> binarySearch(> int> a[],> int> item,> int> low,> int> high)> {> > while> (low <= high) {> > int> mid = low + (high - low) /> 2> ;> > if> (item == a[mid])> > return> mid +> 1> ;> > else> if> (item>a[중간])> > low = mid +> 1> ;> > else> > high = mid -> 1> ;> > }> > return> low;> }> // Function to sort an array a[] of size 'n'> static> void> insertionSort(> int> a[],> int> n)> {> > int> i, loc, j, k, selected;> > for> (i => 1> ; i j = i - 1; selected = a[i]; // find location where selected should be inserted loc = binarySearch(a, selected, 0, j); // Move all elements after location to create space while (j>= loc) { a[j + 1] = a[j]; 제이--; } a[j + 1] = 선택됨; } } // 드라이버 코드 public static void main (String[] args) { int a[] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = a.길이, i; 삽입정렬(a, n); System.out.println('정렬된 배열:'); for (i = 0; i System.out.print(a[i] +' '); } } // 이 코드는 shivanisinghss2110이 제공한 것입니다.>

파이썬3

# iterative implementation> def> binarySearch(a, item, low, high):> > while> (low <> => high):> > mid> => low> +> (high> -> low)> /> /> 2> > if> (item> => => a[mid]):> > return> mid> +> 1> > elif> (item>a[중간]):> > low> => mid> +> 1> > else> :> > high> => mid> -> 1> > return> low> > # Function to sort an array a[] of size 'n'> def> insertionSort(a, n):> > for> i> in> range> (n):> > j> => i> -> 1> > selected> => a[i]> > > # find location where selected should be inserted> > loc> => binarySearch(a, selected,> 0> , j)> > > # Move all elements after location to create space> > while> (j>> => loc):> > a[j> +> 1> ]> => a[j]> > j> -> => 1> > a[j> +> 1> ]> => selected> # Driver Code> a> => [> 37> ,> 23> ,> 0> ,> 17> ,> 12> ,> 72> ,> 31> ,> 46> ,> 100> ,> 88> ,> 54> ]> n> => len> (a)> insertionSort(a, n)> print> (> 'Sorted array: '> )> for> i> in> range> (n):> > print> (a[i], end> => ' '> )> # This code is contributed by shivanisinghss2110>

씨#

using> System;> class> GFG {> // iterative implementation> static> int> binarySearch(> int> []a,> int> item,> int> low,> int> high)> {> > while> (low <= high) {> > int> mid = low + (high - low) / 2;> > if> (item == a[mid])> > return> mid + 1;> > else> if> (item>a[중간])> > low = mid + 1;> > else> > high = mid - 1;> > }> > return> low;> }> // Function to sort an array a[] of size 'n'> static> void> insertionSort(> int> []a,> int> n)> {> > int> i, loc, j, selected;> > for> (i = 1; i j = i - 1; selected = a[i]; // find location where selected should be inserted loc = binarySearch(a, selected, 0, j); // Move all elements after location to create space while (j>= loc) { a[j + 1] = a[j]; 제이--; } a[j + 1] = 선택됨; } } // 드라이버 코드 public static void Main (String[] args) { int []a = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = a.길이, i; 삽입정렬(a, n); Console.WriteLine('정렬된 배열:'); for (i = 0; i Console.Write(a[i] +' '); } } // 이 코드는 shivanisinghss2110에 의해 제공되었습니다.>

자바스크립트

> // iterative implementation> function> binarySearch( a, item, low, high)> {> > while> (low <= high) {> > var> mid = low + (high - low) / 2;> > if> (item == a[mid])> > return> mid + 1;> > else> if> (item>a[중간])> > low = mid + 1;> > else> > high = mid - 1;> > }> > return> low;> }> // Function to sort an array a[] of size 'n'> function> insertionSort(a, n)> {> > var> i, loc, j, k, selected;> > for> (i = 1; i j = i - 1; selected = a[i]; // find location where selected should be inserted loc = binarySearch(a, selected, 0, j); // Move all elements after location to create space while (j>= loc) { a[j + 1] = a[j]; 제이--; } a[j + 1] = 선택됨; } } // 드라이버 코드 var a = [ 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 ]; var n = a.길이, i; 삽입정렬(a, n); document.write('정렬된 배열:' + ' '); for (i = 0; i document.write(a[i] +' '); // 이 코드는 shivanisinghss2110이 기여했습니다.>

산출

Sorted array: 0 12 17 23 31 37 46 54 72 88 100