Le tri des listes chaînées en C

M'a demandé d'écrire une fonction qui prend 3 non triés listes chaînées et retourne une seule triés liste chaînée qui combine tous les trois listes. Quelle est la meilleure façon que vous pouvez penser?

Je n'ai pas vraiment de restrictions de mémoire, mais que feriez-vous avec/sans les restrictions de mémoire?

Ajouté les devoirs de la balise. Comment avez-vous de tri 'em de toute façon? Par ordre alphabétique, à partir de la plus petite à la plus grande..?
rejoindre le 3 listes ensemble (queue de liste 1 -> à la tête de la liste 2, etc..), alors vous avez seulement 1 liste et se réduit à une simple fonction de tri.
Ce algorithmes de tri savez-vous?
Si le tri doit être lié de tri de la liste, puis un bas jusqu'à la fusion de tri à l'aide d'un petit tableau de pointeurs vers les nœuds est la plus rapide. wiki exemple. Depuis les nœuds sont regroupées dans le tableau interne, un à un, les 3 listes peuvent être traités séparément ou regroupés en un seul de la liste avant de fusionner dans le tableau interne. Le tableau interne est ensuite fusionné pour ne former qu'une seule liste triée.

InformationsquelleAutor Awesomenuts | 2011-08-23

38

Une option serait d'utiliser fusion de tri sur l'ensemble des trois listes liées, puis utilisez une dernière étape de fusion et publipostage pour les fusionner dans un ensemble de la liste triée.

Contrairement à la plupart des O(n log n) algorithmes de tri, fusion de tri peut fonctionner efficacement sur les listes chaînées. À un haut niveau, à l'intuition derrière fusion tri sur une liste chaînée est comme suit:
1. Comme un cas de base, si la liste a zéro ou un des éléments, c'est déjà trié.
2. Autrement:
  1. Diviser la liste en deux listes à peu près égale, la taille, peut-être en déplacement impair d'éléments dans une liste et les éléments de même dans l'autre.
  2. De manière récursive l'utilisation de fusion de tri pour trier les listes.
  3. Appliquer un fusion l'étape de combiner ces listes dans une liste triée.
L'algorithme de fusion sur les listes chaînées est vraiment magnifique. Le pseudo-code fonctionne à peu près comme ceci:
1. Initialiser un vide lié liste de tenir le résultat.
2. Tant que les deux listes ne sont pas vides:
  1. Si le premier élément de la première liste est moins que le premier élément de la deuxième liste, déplacez-le vers l'arrière de la liste des résultats.
  2. Sinon, déplacer le premier élément de la deuxième liste à l'arrière de la liste des résultats.
3. Maintenant que exactement une liste est vide, déplacer tous les éléments de la deuxième liste à l'arrière de la liste des résultats.
Ce qui peut être fait pour s'exécuter en O(n) le temps, de sorte que l'ensemble de la complexité de la fusion de tri en O(n log n).

Une fois que vous avez trié tous les trois listes de manière indépendante, vous pouvez appliquer l'algorithme de fusion de combiner les trois listes en une seule finale de la liste triée. Alternativement, vous pourriez envisager de la concaténation des trois listes liées, puis à l'aide d'un géant de fusion tri passer pour trier toutes les listes en même temps. Il n'y a pas de claire "bonne façon" de faire ça, c'est vraiment à vous.

Au-dessus de l'algorithme s'exécute en Θ(n log n) en temps. Il utilise également à seulement Θ(log n) de la mémoire, car il n'alloue pas de nouvelle liste liée cellules et juste besoin d'espace dans chaque frame de pile pour stocker des pointeurs vers les différentes listes. Depuis la profondeur de récursivité est Θ(log n), l'utilisation de la mémoire est Θ(log n) en tant que bien.

Un autre O(n log n) de sorte que vous pouvez mettre en œuvre sur les listes chaînées est une modification de quicksort. Bien que la liste liée version de quicksort est rapide (toujours en O(n log n) attendus), il n'est pas presque aussi rapide que la version qui fonctionne sur des piles en raison de l'absence d'effets de localité à partir des éléments d'un tableau d'être stockés de manière contiguë. Cependant, c'est un très beau algorithme appliqué aux listes.

L'intuition derrière quicksort est comme suit:
1. Si vous avez un zéro ou un élément de la liste, la liste est triée.
2. Autrement:
  1. Choisir un élément de la liste pour l'utiliser comme un point de pivot.
  2. Scinder la liste en trois groupes: les éléments de moins que le pivot, les éléments égaux au pivot, et des éléments supérieurs au pivot.
  3. De façon récursive de tri le plus petit et le plus d'éléments.
  4. Concaténer les trois listes que les plus petites, alors égal à, puis de plus pour obtenir le retour à l'ensemble de la liste triée.
L'un des aspects positifs de la liste liée version de quicksort est qu'à l'étape de partitionnement est nettement plus facile que dans le tableau de cas. Après que vous avez choisi un pivot (détails un peu plus tard), vous pouvez le faire à l'étape de partitionnement par la création de trois vide listes de pour la moins-que, égal à, et plus que des listes, puis de faire une analyse linéaire par rapport à l'original liste liée. Vous pouvez ensuite ajouter/préfixer chaque liste liée nœud à la liste correspondant à l'original seau.

L'un défi à relever dans l'obtention de ce travail est de choisir un bon pivot de l'élément. Il est bien connu que quicksort peut dégénérer à O(n²) le temps si le choix du pivot est mauvais, mais il est également connu que si vous choisissez un pivot de l'élément au hasard le temps d'exécution est O(n log n) avec une forte probabilité. Dans un tableau, c'est facile (il suffit de choisir un ensemble aléatoire de l'index), mais dans la liste des cas est plus délicat. La façon la plus simple de le faire est de choisir un nombre aléatoire entre 0 et la longueur de la liste, puis choisissez l'élément de la liste en O(n) fois. Sinon, il y a quelques assez cool méthodes pour le prélèvement d'un élément au hasard dans une liste chaînée; un tel algorithme est décrit ici.

Si vous voulez un simple algorithme qui nécessite seulement O(1) de l'espace, vous pouvez également envisager l'utilisation de le tri par insertion pour trier les listes chaînées. Alors que le tri par insertion est plus facile à mettre en œuvre, il s'exécute en O(n²) en temps dans le pire des cas (bien qu'il ait aussi O(n) dans le meilleur des cas de comportement), il est donc probablement pas un bon choix si vous souhaitez éviter de fusion de tri.

L'idée derrière l'insertion algorithme de tri est comme suit:
1. Initialiser un vide lié liste de tenir le résultat.
2. Pour chacune des trois listes:
  1. Alors que cette liste n'est pas vide:
    
    Parcourez la liste des résultats afin de trouver l'endroit où le premier élément de cette liste liée appartient.
    
    Insérer l'élément à l'emplacement.
Un autre O(n²) algorithme de tri qui peut être adapté pour les listes chaînées est tri de la sélection. Cela peut être mis en œuvre très facilement (en supposant que vous avez une liste à double liaison) à l'aide de cet algorithme:
1. Initialiser une liste vide maintenant le résultat.
2. Alors que la liste d'entrée n'est pas vide:
  1. Parcourez la liste liée à la recherche pour le plus petit élément restant.
  2. Supprimer cet élément de la liste chaînée.
  3. Ajouter cet élément à la liste des résultats.
Cela fonctionne aussi en O(n²) le temps et utilise seulement O(1) de l'espace, mais dans la pratique, il est plus lent que le tri par insertion; en particulier, il s'exécute toujours en Θ(n²) temps.

En fonction de la façon dont les listes sont structurés, vous pourriez être en mesure de s'en tirer avec quelques très impressionnant hacks. En particulier, si vous êtes donné doublement-listes liées, alors vous avez de la place pour deux pointeurs dans chacun de vos liée liste de cellules. Étant donné que, vous pouvez réinterpréter le sens de ces pointeurs pour faire quelques assez ridicule de tri astuces.

Comme un exemple simple, nous allons voir comment nous pourrions mettre en œuvre arbre de tri à l'aide de la liste liée cellules. L'idée est la suivante. Lorsque la liste liée cellules sont stockés dans une liste liée, le suivant et précédent, les pointeurs ont leur sens original. Cependant, notre objectif sera de manière itérative tirez sur la liste, les cellules de la liste liée, puis de les réinterpréter comme des nœuds dans un arbre de recherche binaire, où le pointeur signifie "droit de la sous-arborescence" et le pointeur précédent signifie "sous-arbre gauche." Si vous êtes autorisé à le faire, voici une façon vraiment cool de mettre en œuvre arbre de tri:
1. Créer un nouveau pointeur vers une liste liée cellule qui sera le pointeur sur la racine de l'arbre.
2. Pour chaque élément de la liste à double liaison:
  1. Supprimer la cellule à partir de la liste chaînée.
  2. Le traitement de cellule comme un BST nœud, insérer le nœud dans l'arbre de recherche binaire.
3. Faire une commande de marche de la BST. Chaque fois que vous visitez un noeud, le retirer de la BST et réinsérez-le dans la liste à double liaison.
Cela va dans le meilleur des cas O(n log n) au temps et au pire des cas en O(n²). En termes de l'utilisation de la mémoire, les deux premières étapes nécessitent seulement O(1) de la mémoire, puisque nous sommes le recyclage de l'espace de l'ancienne pointeurs. La dernière étape peut se faire en O(1) de l'espace à l'aide de certains particulièrement algorithmes intelligents.

Vous pourriez aussi envisager de mettre en œuvre tas de tri de cette façon, même si c'est un peu délicat.

Espérons que cette aide!
- C'est le genre de ce que je recevais, mais vous l'avez mis beaucoup mieux que j'ai fait! :O)
- Si je ne me trompe, qsort fonctionne bien/ok lorsque les liste doublement chaînée. Pourrait vouloir le signaler.
- Oui, c'est vrai. J'ai surtout de souligner que quicksort ne pas obtenir le gain de performance énorme victoire de la localité qui l'amène à surpasser tous les autres O(n log n) trie lorsque vous traitez avec la matrice de cas.
- pouvez-vous nous expliquer la complexité du temps de l'étape de fusion et publipostage?
- La fusion des deux triés listes liées, comme la fusion de deux tableaux triés, peut se faire en temps O(n), où n est le nombre total d'éléments dans les listes. Vous avez juste besoin de stocker de la queue de pointeurs.
- Article de Wiki pour la fusion de tri liées liste comprend désormais un plus rapide bas jusqu'à la fusion de tri de liste chaînée qui utilise un petit (25 à 32) tableau de pointeurs (ou références) pour les nœuds. C'est environ deux fois plus rapide qu'un haut vers le bas de fusion de tri qui a, à plusieurs reprises, scanner les sous-listes afin de les diviser. Dans ce cas, tous les 3 listes pourraient être regroupées dans le tableau (car cette partie est en fait un nœud à la fois), puis le tableau fusionné pour ne former qu'une seule liste.
InformationsquelleAutor templatetypedef
0

Si les 3 listes ont été tries le problème serait simple, mais comme ils ne sont pas c'est un peu plus délicat.

Je voudrais écrire une fonction qui prend une liste et une liste non triée en tant que paramètres, passe par chaque élément de la liste non triée et l'ajoute dans la bonne position dans la liste triée, à son tour, jusqu'à ce qu'il n'y a pas des éléments à gauche dans la liste non triée.

Ensuite il suffit de créer une suite "vide" de la liste qui, de par la nature même de l'être vide est "triés" et appeler la méthode trois fois avec chacune des listes non triées.

De conversion les listes de tableaux peut rendre les choses un peu plus efficace en termes de pouvoir utiliser plus de tri avancées techniques, mais le coût de la conversion d'un tableau doit être considéré et équilibré par rapport à la taille de l'original listes.

InformationsquelleAutor Richard Baxter
0

Je pensais que vous pouvez appliquer la fonction de tri rapide. C'est presque la même que la fusion de tri, la seule différence est que vous devez d'abord diviser et fusionner les fichiers, où pentecôte quicksort de la première "fusion" et ensuite vous rendre à split. Si vous regardez un peu différent est mergesort quicksort dans le sens opposé à

mergesort:

split -> récursivité -> fusionner

quicksort:

umnerge (en face de la fusion) -> récursivité -> join (en face de split)

InformationsquelleAutor Luka Rahne
-1

La mergesort algorithme décrit dans la populaire post par @templatetypedef ne fonctionne pas en temps O(n lg n). Parce que une liste chaînée n'est pas aléatoire, l'étape 2.1 Split the list into two lists of roughly equal size signifie, en réalité, un ensemble de l'algorithme en O(n^2 log n) pour trier la liste. Juste réfléchir un peu.

Voici un lien qui utilise mergesort pour trier une liste en première lecture les éléments dans un tableau -- http://www.geekviewpoint.com/java/singly_linked_list/sort.
- Comme je l'ai mentionné dans mon commentaire sur votre réponse à une autre question, ce n'est pas vrai. Le linéaire de travail nécessaire pour faire du split, de ne pas augmenter la asymptotique de l'exécution, car il est déjà linéaires du travail se fait dans l'étape de fusion et publipostage. La relation de récurrence est exactement le même. Historiquement, la fusion de tri a été inventé pour travailler sur les lecteurs de bande (qui fonctionnent de manière similaire à des listes liées à de nombreux égards) et l'amélioration de plus de la naïveté O(n^2) sortes, c'est pourquoi il a été utilisé.
InformationsquelleAutor kasavbere
-7

Il n'y a pas efficace algorithmes de tri pour les listes chaînées.
faire un tableau, trier, et de rétablir le lien.
- Euh...mergesort fonctionne très bien. Le seul truc est de savoir comment diviser la liste de manière efficace. Par exemple: chiark.greenend.org.royaume-uni/~sgtatham/algorithms/listsort.html .
- Fusion de tri ne fonctionne que si les listes sont déjà triées, dans ce cas le 3 liste sont à l'origine de l'onu, de tri, de sorte que l'étape 1 serait de trier les listes liées, et puis jointure de fusion-si la mémoire n'est pas un problème, alors la création d'un tableau de pointeurs, le tri des pointeurs et puis créer une nouvelle liste, serait plus efficace.
- Soren: mergesort peut être utilisé sur les listes non triées, puis la fonction de fusion/méthode/de l'outil peut être utilisé pour les combiner.
- -1: - je utiliser mergesort tout le temps dans mes programmes Haskell. Il s'agit sous le couvert Data.List.sort. Il fonctionne efficacement en O(nlogn).
- BTW: Ce serait un bon moment pour obtenir un disciplinée insigne.
- En commençant par des ménagères de listes, de toute sorte sur la base de listes est O(n)
InformationsquelleAutor ddyer

Vous devez vous connecter pour publier un commentaire.