Tri de 2 listes chaînées de 50000 numéros avec un ensemble d’opérations limité

J’ai donc ce projet pour l’école: j’ai une liste chaînée de 50 000 numéros et une deuxième liste vide. Je n’ai qu’un panel d’instructions très limité. Elles sont :

Je dois implémenter un algorithme de sorting en c et le but est de le faire avec le moins d’instructions possible. J’ai essayé avec un algorithme très simple qui faisait tourner la liste un jusqu’à ce que le maximum soit au-dessus, puis l’a placé à plusieurs resockets dans la liste 2 jusqu’à ce que tout soit dans la liste 2, puis tout repoussé dans la liste 1 plus de 5 000 numéros dans un délai raisonnable

Je pense avoir compris comment faire cela en utilisant un sorting rapide. Voici un pseudocode.

edit: pseudocode mis à jour pour se concentrer sur ce qu’il fait et non sur une syntaxe inutile

 quicksort(int n) if n == 1 return int top_half_len = 0 choose a median //it's up to you to determine the best way to do this for 0 to n { //filter all values above the median into list 2 if (value > median) { push list 1 top to list 2 //list 2 stores the larger half top_half_len++ } rotate list 1 forward } //reverse the list back to original position rotate list 1 backward (n - top_half_len) times //push larger half onto smaller half push list 2 top to list 1 top_half_len times //recursively call this on the larger half quicksort(top_half_len) //rotate smaller half to front rotate list 1 forward top_half_len times //recursively call this on smaller half quicksort(n - top_half_len) //reverse list back to original position rotate list 1 backward top_half_len times 

Fondamentalement, il divise la liste en une partie inférieure ou égale à la médiane (moitié inférieure) et une partie supérieure à la médiane (moitié supérieure). Ensuite, il s’appelle sur ces deux moitiés. Une fois leur longueur 1, l’algorithme est terminé, car une liste de 1 longueur est sortingée. Tri rapide sur Google pour une explication réelle.

Je pense que cela devrait fonctionner, mais j’ai peut-être manqué un cas particulier. Ne suivez pas aveuglément ceci. De plus, si vous utilisiez des tableaux, je vous recommanderais d’arrêter le sorting rapide à une certaine profondeur de récursivité et d’utiliser le sorting en tas (ou quelque chose pour éviter la complexité O (n ^ 2) la plus défavorable), mais je ne suis pas sûr. ce qui serait efficace ici. update: selon Peter Cordes, vous devriez utiliser le sorting par insertion lorsque vous vous trouvez en dessous d’une certaine taille de tableau (IMO, vous devriez également le faire à une certaine profondeur de récursion).

Apparemment, le sorting par fusion est plus rapide sur les listes chaînées. Il ne serait probablement pas trop difficile de modifier cela pour implémenter le sorting par fusion. Le sorting par fusion est assez similaire au sorting rapide. Pourquoi le sorting par fusion est-il préférable au sorting rapide pour le sorting des listes chaînées?

L’instruction problem manque d’une fonction de comparaison. Je définirais donc compare (lista, listb) pour comparer le premier nœud de lista avec le premier nœud de listb et renvoyer -1 pour <, 0 pour =, 1 pour plus ou moins est vraiment nécessaire pour le type de fusion est 0 pour <= et 1 pour>.

Il manque également une valeur de retour pour indiquer qu’une liste est vide lors de l’exécution de pa ou de pb. Je définirais pa ou pb pour renvoyer 1 si la liste source n’est pas vide et 0 si la liste source est vide (aucun noeud à copier).

Il n’est pas clair si l’objective est le plus petit nombre d’instructions fait référence au nombre d’instructions dans le code source ou au nombre d’instructions exécutées lors du sorting.

 - 

Le plus petit nombre d’instructions dans le code ferait pivoter list2 en fonction de compare avec list1 pour insérer des nœuds dans list2 à l’emplacement approprié. Commencez avec un pb et définissez la taille de list2 sur 1. Ensuite, rb ou rrb sont utilisés pour faire pivoter list2 vers l’endroit où le prochain pb doit être effectué. Le code garderait trace de list2 “offset” vers le plus petit nœud afin d’éviter une boucle sans fin dans la rotation de list2. La complexité est O (n ^ 2).

 - 

Je pense que le type le plus rapide et peut-être le moins d’instructions exécutées est un type de fusion ascendante.

Faites un sorting par fusion en faisant pivoter les listes, en les utilisant comme des tampons / listes circulaires. Copiez list1 vers list2 pour générer un nombre de nœuds, en utilisant la séquence | compte = 0 | tandis que (pb) {rb | compte + = 1}.

En utilisant le nombre, déplacez tous les autres nœuds de list2 vers list1 en utilisant {pa, rr}, n / 2 fois. Toujours garder une trace du nombre réel de nœuds sur chaque liste afin de savoir quand la fin logique d’une liste est atteinte. Gardez également la trace d’un compteur d’exécution pour chaque liste afin de savoir quand la fin logique d’une exécution est atteinte. À ce stade, vous avez deux listes où les nœuds pairs sont sur list1 et les nœuds impairs sont sur list2.

La taille de la course commence à 1 et double à chaque passage. Pour le premier passage avec une taille d’exécution de 1, fusionnez les nœuds pairs avec les nœuds impairs, en créant des exécutions sortingées de taille 2, en alternant l’ajout des paires de nœuds sortingés à list1 et list2. Par exemple, si vous ajoutez à noeud list1 et noeud list1 <= noeud list2, utilisez {ra, run1count - = 1}, sinon utilisez {pa, ra, run2count - = 1}. Lorsque la fin d'une analyse est atteinte, ajoutez le reste de l'analyse à la fin de la liste. Au passage suivant, fusionnez les exécutions triées de 2 nœuds des listes, en ajoutant alternativement les exécutions triées de 4 nœuds à chaque liste. Continuez cette opération pour les exécutions de 8, 16, ... jusqu'à ce que tous les nœuds se retrouvent dans une liste.

Il ne rest donc qu’une passe pour compter les nœuds, une passe pour séparer les nœuds pairs et impairs, et ceil (log2 (n)) pour effectuer le sorting par fusion. La surcharge des opérations de la liste chaînée est faible (la rotation supprime et ajoute un nœud), de sorte que la fusion globale devrait être assez rapide.

Le nombre d’instructions sur le nombre de passes peut être réduit avec while (pb) {nombre + = 1}, ce qui permet de copier liste1 à liste2 inversé. Ensuite, cracher liste2 dans liste1 serait également effectué en utilisant rrr pour les inverser.

La complexité est O (n log (n)).