logo

TechCodeview

이진 삽입 정렬

이진 삽입 정렬은 다음과 유사한 정렬 알고리즘입니다. 삽입 정렬 , 그러나 요소를 삽입해야 하는 위치를 찾기 위해 선형 검색을 사용하는 대신 다음을 사용합니다. 이진 검색 . 따라서 단일 요소를 삽입하는 비교 값을 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)의 최악의 실행 시간을 갖습니다.2) 각 삽입에 필요한 일련의 교체로 인해.

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

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에 의해 제공되었습니다.> 

>

>

문자열 json객체

자바스크립트




> // 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>