Méthode d'insertion de liste Knuth en C

Question

J'ai lu les algorithmes de tri et de recherche du volume 3 de l'art de la programmation informatique de Donald Knuth, deuxième édition. Je suis tombé sur un algorithme que Knuth appelle "insertion de liste" (Une modification sur le tri d'insertion traditionnel) à la page 95.

Sur cette page, Knuth conclut que la "bonne structure de données pour l'insertion directe est un sens unique, lié liste linéaire. », et que« l'allocation liée (section 2.2.3) est parfaitement adaptée à l'insertion, car seuls quelques liens doivent être modifiés ». Toutefois, le programme MIXAL (Programme L) à la page 97 ne semble pas utiliser une structure de liste linéaire liée traditionnelle (une série de nœuds liés par des adresses). Au lieu de cela, il semble que la clé et le lien sont stockés ensemble dans une structure semblable à une structure et ces structures sont stockées dans un tableau appelé INPUT.

J'ai décidé d'essayer de mettre en œuvre cet algorithme en C. J'ai fourni la description de Knuth de l'algorithme, et son implémentation dans le langage d'assemblage MIXAL comme référence. J'ai décidé de laisser les clés être les éléments, eux-mêmes, dans le tableau data, et j'ai mis les liens dans un tableau semblable à un parallèle appelé links. Je dis «tableau de type parallèle» car la taille du tableau links est supérieure à la taille du tableau data. Je l'ai fait pour que je puisse facilement déterminer l'index du plus petit élément du tableau data en le stockant comme le premier élément du tableau links. En raison de cet index supplémentaire dans links, les indices 0 - (n - 1) du tableau data correspondent aux indices 1 - n du tableau links. Chaque élément du tableau links correspond à l'index du tableau data de l'élément suivant de la liste triée.

Ma question est, est-ce comment cet algorithme est censé être mis en œuvre en fonction de sa description, ou est-ce que je manque quelque chose?

int *listInsertion(int data[], int n) { 

    if (n > 1) { 
     int i, j, entry; 
     int *links = (int *) calloc(n + 1, sizeof *links); 
     links[n] = -1; 
     links[n - 1] = n - 1; 

     for (i = n - 2; i >= 0; i--) { 
      entry = data[i]; 
      for (j = i + 1; links[j] >= 0 && entry > data[links[j]]; 
        j = links[j] + 1) 
       continue; 

      if (j == i + 1) { 
       links[i] = i; 
      } else { 
       links[i] = links[i + 1]; 
       links[i + 1] = links[j]; 
       links[j] = i; 
      } 
     } 
     return links; 
    } 
    return NULL; 
} 

Answer 1

Je vous suggère de mettre en œuvre l'algorithme avec le symbole mentionné par Knuth premier.
Cela vous aidera à trouver la première version rapidement.

void insertSort(const int *K, int *L, int n) { 
    if (n == 1) return; 

    L[n] = n-1; 
    L[n-1] = n; 

    for (int j = n-2; j >= 0; j--) { 
    int entry = K[j]; 
    int p = L[n]; 
    int q = n; 

    while(entry > K[p]) { 
     q = p; 
     p = L[q]; 
     if (p == n) { 
     break; 
     } 
    } 

    L[q] = j; 
    L[j] = p; 
    } 
} 

Ensuite, vous pouvez refactoriser votre première version pour l'améliorer ou la rendre plus courte.