Je travaille à travers le livre Introduction aux algorithmes, 3ème édition. L'une des premières choses expliquées est le tri de l'insertion. À la page 18 Il y a un peu de code pseudo:
a = {5, 2, 4, 6, 1, 3}; p> Il est indiqué que le pseudo code est utilisé de sorte qu'il se traduit facilement vers n'importe quel type de langage (C, C ++, Java, ils ne mentionnent pas, mais je suppose que c # aussi). Depuis que je programme en C #, je l'ai traduits dans Linqpad. P> for (var j = 2; j <= a.Length - 1; j++)
{
var key = a[j];
var i = j - 1;
while(i > 0 && a[i] > key)
{
a[i + 1] = a[i];
i--;
}
a[i + 1] = key;
}
6 Réponses :
Je pense que le professeur utilise une notation de tableau basée sur 1, donc avec tandis que (i> 0 && a [i]> clé) code>, vous manquez l'élément A [0] dans la boucle . Changez votre code initial en cela, alors cela fonctionne: for (var j = 1; j < a.Length; j++)
{
var key = a[j];
var i = j - 1;
while(i >= 0 && a[i] > key) <----------- Try this, or you'd miss the first number
{
a[i + 1] = a[i];
i--;
}
a[i + 1] = key;
}
Oui, i> = 0 fonctionne effectivement. J'ai découvert comment obtenir le tri au travail s'il est un peu différent de votre solution - c'est celui que vous voyez beaucoup dans d'autres manuels. Au lieu d'avoir i> = 0 , vous feriez le deuxième prédicat de la boucle tandis que la boucle A [i-1] et avez la première ligne dans la boucle tandis que A [i + 1] = A [i] comme A [i] = A [I - 1] . Le professeur que j'ai contacté était Corman. Bien qu'il soit assez gentil de répondre, il semblait tout à fait offensé que je pensais qu'il y avait peut-être un bogue dans le code.
"Je pense que le professeur utilise une notation de tableau à 1 fois" - j'ai reçu un email et c'était en effet ce qui se passait. Je ne sais pas pourquoi j'ai reçu du code avec un tableau qui commence par un index de 1. J'ai regardé les tableaux C et j'ai pensé qu'ils ont toujours commencé avec 0.
@Garth: Eh bien, je suppose que Corman est juste en train d'être paresseux :) Et après tout, car il utilise des pointeurs, il pourrait traiter l'entrée comme s'il est basé sur 1, car dans son code, le A [0] n'est jamais utilisé.
Je crois que votre argument sur i> 0 est correct, quel que soit le prof. dit. Dans le pseudo-code, la boucle est pendant que je> 0 et que l'indexation de la matrice commence par 1. Dans C #, l'indexation du tableau commence par 0, vous devez donc avoir pendant que je> = 0 < / code>.
Droite. Et j'ai vérifié comme des tableaux de bienvenus en C, ils commencent également par un index de 0.
Vous ne devriez pas penser à traduire le pseudocode, mais à propos de traduire votre compréhension de l'algorithme.
Le tableau est complètement non formé au début. L'algorithme fonctionne par
prendre des éléments non traités successifs et les insérer dans le
partie déjà triée. La "partie triée" de départ est le premier élément,
qui est trivialement "triée". Donc, le premier élément à insérer est le
seconde. Quel est l'index du deuxième élément? Votre alors, Les erreurs hors-tête sont notoirement difficiles à repérer (et à mélanger
Des notions de tableaux à base de 1 et à base de 0 n'aident sûrement pas), mais ne pas
juste violer jusqu'à ce qu'il semble fonctionner. Essayez de comprendre ce que le
le code fait réellement. j doit
partir de là.
i doit parcourir chacun des indices d'éléments triés,
en arrière, jusqu'à ce qu'il trouve l'endroit pour insérer la valeur actuelle
ou manque d'éléments. Donc, d'où faut-il commencer et où
faut-il finir? Veillez à ce qu'il regarde réellement chaque élément
est doit.
Je suis totalement d'accord - et c'est ce que j'ai fait. Je l'ai mis à part, regarda les pièces mobiles et je l'obtiens. Je reçois comment ça marche, je peux le faire fonctionner. En le retournant, cependant au pseudo code et le code que j'ai obtenu du professeur que je suis confus parce que je ne peux tout simplement pas obtenir la bonne sortie. Le professeur est admis sur le fait que cela fonctionne.
...Et il fonctionne. Le professeur m'a envoyé m'a expliqué que le tableau C commençait avec un indice de 1. Depuis que je pensais que les tableaux C ont commencé avec 0, le code n'a pas eu de sens. Maintenant ça fait!
N'oubliez pas: A.Longueur va de 0 à N, alors la longueur devrait être a.length -1. J'ai fait cet algorithme pour mes étudiants en C ++ en espagnol, en utilisant ce livre. Est simple à traduire en c #.
une traduction pour que vous puissiez mieux comprendre
Je suis également tombé sur votre problème et j'ai trouvé la solution à cela. J'ai codé l'algorithme en Java comme ci-dessous.
int a[] = {5,2,4,3,1};
int key;
int i;
for(int j = 0; j < 5; j++)
{
key = a[j];
i = j - 1;
while(i>=0 && a[i]>key)
{
a[i+1]= a[i];
i--;
}
a[i+1] = key;
for(int k=0; k<a.length;k++)
{
System.out.print(a[k]+" ");
}
}
WOW, merci de revenir à elle (après une si longue période après avoir été posée!)
J'ai vécu le même problème. Vous trouverez ci-dessous le code en C qui implémente correctement le pseudo-code ci-dessus. Je n'utilise pas les pointeurs, comme d'autres solutions.
En effet, la partie délicate à ce sujet était que le pseudo code utilise des notations de matrices à base de 1, contrairement à la plupart des langages de programmation! P>
#include <stdio.h>
int main(void)
{
int A[] = { 50, 20, 10, 40, 60, 30 };
int j, key, len, i;
len = (sizeof(A)) / (sizeof(A[0]));
for (j = 1; j < 6; j++) { <-- Change here
key = A[j];
// Insert key into the sorted sequence A[1 .. j - 1].
i = j - 1;
while (i >= 0 && A[i] > key) { <-- Change here
A[i + 1] = A[i];
i--;
}
A[i + 1] = key;
}
for (int z = 0; z < len; z++) {
printf("%d ", A[z]);
}
printf("\n");
}
Chaque langage de programmation que je connais des index de 0. Je pense que Matlab et R pourraient être des exceptions, mais ce ne sont pas de véritables langues de programmation. :-)