Le tri par insertion binaire est un algorithme de tri similaire au tri par insertion , mais au lieu d'utiliser la recherche linéaire pour trouver l'emplacement où un élément doit être inséré, nous utilisons recherche binaire . Ainsi, nous réduisons la valeur comparative de l'insertion d'un seul élément de O (N) à O (log N).
Il s'agit d'un algorithme flexible, ce qui signifie qu'il fonctionne plus rapidement lorsque les mêmes membres donnés sont déjà fortement triés, c'est-à-dire que l'emplacement actuel de l'entité est plus proche de son emplacement réel dans la liste triée.
Il s'agit d'un algorithme de filtrage stable – les éléments avec les mêmes valeurs apparaissent dans le même ordre dans le dernier ordre comme dans la première liste.
Applications du tri par insertion binaire :
- Le tri par insertion binaire fonctionne mieux lorsque le tableau contient un nombre d'éléments inférieur.
- Lors d'un tri rapide ou d'un tri par fusion, lorsque la taille du sous-tableau devient plus petite (disons <= 25 éléments), il est préférable d'utiliser un tri par insertion binaire.
- Cet algorithme fonctionne également lorsque le coût des comparaisons entre clés est suffisamment élevé. Par exemple, si nous souhaitons filtrer plusieurs chaînes, les performances de comparaison de deux chaînes seront plus élevées.
Comment fonctionne le tri par insertion binaire ?
- Dans le mode de tri par insertion binaire, nous divisons les mêmes membres en deux sous-tableaux – filtrés et non filtrés. Le premier élément des mêmes membres se trouve dans le sous-tableau organisé et tous les autres éléments ne sont pas planifiés.
- Ensuite, nous itérons du deuxième élément au dernier. Dans la répétition du i-ème, nous faisons de l’objet actuel notre clé. Cette clé est une fonctionnalité que nous devrions ajouter à notre liste existante ci-dessous.
- Pour ce faire, nous utilisons d'abord une recherche binaire sur le sous-tableau trié ci-dessous pour trouver l'emplacement d'un élément plus grand que notre clé. Appelons cette position pos. Nous décalons ensuite vers la droite tous les éléments de pos à 1 et créons Array[pos] = key.
- Nous pouvons noter qu'à chaque i-ème multiplication, la partie gauche du tableau jusqu'à (i – 1) est déjà triée.
Approche pour implémenter le tri par insertion binaire :
- Parcourez le tableau du deuxième élément au dernier élément.
- Stockez l’élément actuel A[i] dans une clé variable.
- Recherchez la position de l'élément juste supérieure à A[i] dans le sous-tableau de A[0] à A[i-1] à l'aide de la recherche binaire. Supposons que cet élément soit à l'index pos.
- Déplacez tous les éléments de l'index pos vers i-1 vers la droite.
- A[pos] = clé.
Vous trouverez ci-dessous la mise en œuvre de l'approche ci-dessus :
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[faible]) ?> >(low + 1) : low;> >int> mid = (low + high) / 2;> >if> (item == a[mid])> >return> mid + 1;> >if> (item>un[milieu])> >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]; j--; } a[j + 1] = sélectionné ; } } // Code du pilote int main() { int a[] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = taillede(a) / taillede(a[0]), je; insertionSort(a, n); cout<<'Sorted array:
'; for (i = 0; i cout <<' '<< a[i]; return 0; } // this code is contribution by shivanisinghss2110> |
>
>
C
// 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>un[faible]) ?> >(low + 1) : low;> >int> mid = (low + high) / 2;> >if> (item == a[mid])> >return> mid + 1;> >if> (item>un[milieu])> >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]; j--; } a[j + 1] = sélectionné ; } } // Code du pilote int main() { int a[] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = taillede(a) / taillede(a[0]), je; insertionSort(a, n); printf('Tableau trié :
'); pour (i = 0; i printf('%d ', a[i]); return 0; }> |
>
>
Java
liste de tableaux Java
apprentissage automatique supervisé
// 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> |
>
>
Python3
# 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]>val:> >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>fin :> >return> start> >mid>=> (start>+>end)>/>/>2> >if> arr[mid] return binary_search(arr, val, mid+1, end) elif arr[mid]>val : return binaire_search(arr, val, start, mid-1) else : return mid def insertion_sort(arr) : pour i dans range(1, len(arr)) : val = arr[i] j = binaire_search(arr, val, 0, i-1) arr = arr[:j] + [val] + arr[j:i] + arr[i+1:] return arr print('Tableau trié :') print(insertion_sort( [37, 23, 0, 31, 22, 17, 12, 72, 31, 46, 100, 88, 54])) # Code contribué par Mohit Gupta_OMG> |
>
>
C#
// 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[$faible]) ? ($faible + 1) : $faible; $mid = (int)(($low + $high) / 2); if($item == $a[$mid]) return $mid + 1; if($item> $a[$mid]) return binaireSearch($a, $item, $mid + 1, $high); return binaireSearch($a, $item, $low, $mid - 1); } // Fonction pour trier un tableau a de taille 'n' function insertionSort(&$a, $n) { $i; $loc; $j; k$ ; $sélectionné ; pour ($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] = $sélectionné ; } } // Code du pilote $a = array(37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54); $n = taillede($a); insertionSort($a, $n); echo 'Tableau trié :
'; pour ($i = 0; $i<$n; $i++) echo '$a[$i] '; // This code is contributed by // Adesh Singh ?>> |
>
>
Javascript
> // Javascript Program implementing> // binary insertion sort> function> binarySearch(a, item, low, high)> {> > >if> (high <= low)> >return> (item>a[faible]) ?> >(low + 1) : low;> > >mid = Math.floor((low + high) / 2);> > >if>(item == a[mid])> >return> mid + 1;> > >if>(item>un[milieu])> >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) { tableau[j + 1] = tableau[j]; j--; } // Placer l'élément à son // emplacement correct array[j+1] = x; } } // Code du pilote let arr=[ 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54]; trier(arr); for (let i = 0; i document.write(arr[i] + ' '); // Ce code est fourni par unknown2108 // Programme C pour l'implémentation du // tri par insertion binaire #include // Une recherche binaire fonction basée // pour trouver la position // où l'élément doit être inséré // dans a[low..high] int binaireSearch(int a[], int item, int low, int high) { if (high<= low) return (item>un[faible]) ? (faible + 1) : faible ; int mid = (bas + haut) / 2 ; if (item == a[mid]) renvoie mid + 1 ; if (item> a[mid]) return binaireSearch(a, item, mid + 1, high); return binaireSearch(a, item, low, mid - 1); } // Fonction pour trier un tableau a[] de taille 'n' void insertionSort(int a[], int n) { int i, loc, j, k, selected; for (i = 1; i { j = i - 1; selected = a[i]; // trouver l'emplacement où la sélection doit être insérée loc = binaireSearch(a, selected, 0, j); // déplacer tous les éléments après l'emplacement pour créer de l'espace while (j>= loc) { a[j + 1] = a[j]; j--; } a[j + 1] = selected } } // Driver Code int main() { int a [] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = taille de (a) / taille de (a [0]), je; ); printf('Tableau trié :
'); for (i = 0; i printf('%d ', a[i]); r// Programme C pour l'implémentation du // tri par insertion binaire #include // Une fonction basée sur la recherche binaire // pour trouver la position // où l'élément doit être inséré // dans a[low..high] int binaireSearch(int a[], int item, int low, int high) { si (élevé<= low) return (item>un[faible]) ? (faible + 1) : faible ; int mid = (bas + haut) / 2 ; if (item == a[mid]) renvoie mid + 1 ; if (item> a[mid]) return binaireSearch(a, item, mid + 1, high); return binaireSearch(a, item, low, mid - 1); } // Fonction pour trier un tableau a[] de taille 'n' void insertionSort(int a[], int n) { int i, loc, j, k, selected; for (i = 1; i { j = i - 1; selected = a[i]; // recherche l'emplacement où la sélection doit être insérée loc = binaireSearch(a, selected, 0, j); // déplace tous les éléments après l'emplacement pour créer de l'espace while (j>= loc) { a[j + 1] = a[j]; j--; } a[j + 1] = selected } } // Driver Code int main() { int a [] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = taille de (a) / taille de (a [0]), je; ); printf('Tableau trié :
'); for (i = 0; i printf('%d ', a[i]); // Programme C pour l'implémentation du // tri par insertion binaire # include // Une fonction basée sur la recherche binaire // pour trouver la position // où l'élément doit être inséré // dans a[low..high] int binaireSearch(int a[], int item, int low, int high) { if (haut<= low) return (item>un[faible]) ? (faible + 1) : faible ; int mid = (bas + haut) / 2 ; if (item == a[mid]) renvoie mid + 1 ; if (item> a[mid]) return binaireSearch(a, item, mid + 1, high); return binaireSearch(a, item, low, mid - 1); } // Fonction pour trier un tableau a[] de taille 'n' void insertionSort(int a[], int n) { int i, loc, j, k, selected; for (i = 1; i { j = i - 1; selected = a[i]; // recherche l'emplacement où la sélection doit être insérée loc = binaireSearch(a, selected, 0, j); // déplace tous les éléments après l'emplacement pour créer de l'espace while (j>= loc) { a[j + 1] = a[j]; j--; } a[j + 1] = selected } } // Driver Code int main() { int a [] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = taille de (a) / taille de (a [0]), je; ); printf('Tableau trié :
'); for (i = 0; i printf('%d ', a[i]); // Programme C pour l'implémentation du // tri par insertion binaire # include // Une fonction basée sur la recherche binaire // pour trouver la position // où l'élément doit être inséré // dans a[low..high] int binaireSearch(int a[], int item, int low, int high) { if (haut<= low) return (item>un[faible]) ? (faible + 1) : faible ; int mid = (bas + haut) / 2 ; if (item == a[mid]) renvoie mid + 1 ; if (item> a[mid]) return binaireSearch(a, item, mid + 1, high); return binaireSearch(a, item, low, mid - 1); } // Fonction pour trier un tableau a[] de taille 'n' void insertionSort(int a[], int n) { int i, loc, j, k, selected; for (i = 1; i { j = i - 1; selected = a[i]; // trouver l'emplacement où la sélection doit être insérée loc = binaireSearch(a, selected, 0, j); // déplacer tous les éléments après l'emplacement pour créer de l'espace while (j>= loc) { a[j + 1] = a[j]; j--; } a[j + 1] = selected } } // Driver Code int main() { int a [] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = taille de (a) / taille de (a [0]), je; ); printf('Tableau trié :
'); for (i = 0; i printf('%d ', a[i]); // Programme C pour l'implémentation du // tri par insertion binaire # include // Une fonction basée sur la recherche binaire // pour trouver la position // où l'élément doit être inséré // dans a[low..high] int binaireSearch(int a[], int item, int low, int high) { if (haut<= low) return (item>un[faible]) ? (faible + 1) : faible ; int mid = (bas + haut) / 2 ; if (item == a[mid]) renvoie mid + 1 ; if (item> a[mid]) return binaireSearch(a, item, mid + 1, high); return binaireSearch(a, item, low, mid - 1); } // Fonction pour trier un tableau a[] de taille 'n' void insertionSort(int a[], int n) { int i, loc, j, k, selected; for (i = 1; i { j = i - 1; selected = a[i]; // recherche l'emplacement où la sélection doit être insérée loc = binaireSearch(a, selected, 0, j); // déplace tous les éléments après l'emplacement pour créer de l'espace while (j>= loc) { a[j + 1] = a[j]; j--; } a[j + 1] = selected } } // Driver Code int main() { int a [] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = taille de (a) / taille de (a [0]), je; ); printf('Tableau trié :
'); for (i = 0; i printf('%d ', a[i]);// Programme C pour l'implémentation du // tri par insertion binaire # include // Une fonction basée sur la recherche binaire // pour trouver la position // où l'élément doit être inséré // dans a[low..high] int binaireSearch(int a[], int item, int low, int high) { if (haut<= low) return (item>un[faible]) ? (faible + 1) : faible ; int mid = (bas + haut) / 2 ; if (item == a[mid]) return mid + 1 ; if (item> a[mid]) return binaireSearch(a, item, mid + 1, high); return binaireSearch(a, item, low, mid - 1); } // Fonction pour trier un tableau a[] de taille 'n' void insertionSort(int a[], int n) { int i, loc, j, k, selected; for (i = 1; i { j = i - 1; selected = a[i]; // recherche l'emplacement où la sélection doit être insérée loc = binaireSearch(a, selected, 0, j); // déplace tous les éléments après l'emplacement pour créer de l'espace while (j>= loc) { a[j + 1] = a[j]; j--; } a[j + 1] = selected } } // Driver Code int main() { int a [] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = taille de (a) / taille de (a [0]), je; ); printf('Tableau trié :
'); pour (i = 0; i printf('%d ', a[i])> |
>
>Sortir
mot-clé statique en Java
Sorted array: 0 12 17 23 31 37 46 54 72 88 100>
Complexité temporelle : L’algorithme dans son ensemble a toujours un temps d’exécution dans le pire des cas de O(n2) en raison de la série d'échanges requis pour chaque insertion.
Une autre approche : Voici une implémentation itérative du code récursif ci-dessus
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>un[milieu])> >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]; j--; } a[j + 1] = sélectionné ; } } // Code du pilote int main() { int a[] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = taillede(a) / taillede(a[0]), je; insertionSort(a, n); cout<<'Sorted array:
'; for (i = 0; i cout <<' '<< a[i]; return 0; } // This code is contributed by shivanisinghss2110.> |
>
>
C
#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>un[milieu])> >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]; j--; } a[j + 1] = sélectionné ; } } // Code du pilote int main() { int a[] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = taillede(a) / taillede(a[0]), je; insertionSort(a, n); printf('Tableau trié :
'); for (i = 0; i printf('%d ', a[i]); return 0; } // contribué par tmeid> |
>
ouvrir un fichier avec java
>
Java
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>un[milieu])> >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]; j--; } a[j + 1] = sélectionné ; } } // Code du pilote public static void main (String[] args) { int a[] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = a.longueur, je; insertionSort(a, n); System.out.println('Tableau trié :'); for (i = 0; i System.out.print(a[i] +' '); } } // Ce code est fourni par shivanisinghss2110.> |
>
>
Python3
# 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[milieu]):> >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> |
>
>
C#
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>un[milieu])> >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]; j--; } a[j + 1] = sélectionné ; } } // Code du pilote public static void Main (String[] args) { int []a = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = a.Longueur, i; insertionSort(a, n); Console.WriteLine('Tableau trié :'); for (i = 0; i Console.Write(a[i] +' '); } } // Ce code est contribué par shivanisinghss2110> |
mylivecriclet
>
>
Javascript
> // 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>un[milieu])> >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]; j--; } a[j + 1] = sélectionné ; } } // Code du pilote var a = [ 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 ]; var n = a.longueur, je; insertionSort(a, n); document.write('Tableau trié :' + ' '); for (i = 0; i document.write(a[i] +' '); // Ce code est fourni par shivanisinghss2110> |
>
>Sortir
Sorted array: 0 12 17 23 31 37 46 54 72 88 100>