tri par insertion dans le meilleur cas

Question

En ce qui concerne algorithme - Quatrième édition par Robert et Kevin, j'ai du mal à comprendre la meilleure complexité de cas pour tri par insertion comme ci-dessous le code:

public class Insertion 
{ 
    public static void sort(Comparable[] a) 
    { // Sort a[] into increasing order. 
     int N = a.length; 
     for (int i = 1; i < N; i++) 
      { // Insert a[i] among a[i-1], a[i-2], a[i-3]... .. 
       for (int j = i; j > 0 && less(a[j], a[j-1]); j--) 
        exch(a, j, j-1); 
     } 
    } 
// See page 245 for less(), exch(), isSorted(), and main(). 
} 

Il dit dans le livre que dans le meilleur des cas (tableau trié), le nombre d'échanges est 0 et le nombre de comparés est N-1. Alors que j'ai compris que les échanges étaient à 0, j'ai du mal à savoir comment le nombre de comparés peut-il être N-1 dans le meilleur des cas?

Answer 1

Si le tableau est déjà trié, puis dans la mise en œuvre spécifique d'insertion sorte que vous fournissez, que chaque élément sera comparé à son prédécesseur immédiat. Comme il n'est pas inférieur à ce prédécesseur, le for -loop interne s'interrompt immédiatement, sans nécessiter d'autres comparaisons ou échanges. Notez que les autres implémentations de insertion-tri n'ont pas nécessairement cette propriété.

Answer 2

Le code source pour la mise en œuvre spécifique est:

public class Insertion 
{ 
    public static void sort(Comparable[] a) 
    { // Sort a[] into increasing order. 
     int N = a.length; 
     bool exc = false; 
     for (int i = 1; i < N; i++) 
      { // Insert a[i] among a[i-1], a[i-2], a[i-3]... .. 
       for (int j = i; j > 0 && less(a[j], a[j-1]); j--) { 
        exch(a, j, j-1); 
        exc = true; 
       } 
      if (!exc) 
       break; 
     } 
    } 
// See page 245 for less(), exch(), isSorted(), and main(). 
} 

Answer 3

comment peut nombre de N-être compare 1 dans le meilleur des cas?

Le meilleur cas se produit lorsque vous avez un tableau déjà trié. Le nombre de comparaison est n-1 parce que la comparaison est faite à partir du 2ème élément jusqu'au dernier élément.

Cela peut aussi être observé à partir de votre code donné:

for (int i = 1; i < N; i++) //int i=1 (start comparing from 2nd element)