Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1253 connectés 

  FORUM HardWare.fr
  Programmation
  C

  Tri rapide pour les listes liées Assistance requise

 
 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Tri rapide pour les listes liées Assistance requise

n°2451614
joun17
be cool
Posté le 21-07-2023 à 17:49:18  profilanswer
 

Bonjour à tous,
 
J'essaie de créer l'algorithme de tri rapide pour des listes liées similaires à cet exemple, mais j'ai quelques problèmes. Je me rends compte que les listes chaînées ont des structures de mémoire différentes de celles des tableaux et qu'il peut être difficile de les diviser efficacement.
 
Voici ce que j'ai en Python jusqu'à présent

Code :
  1. class ListNode:
  2.     def __init__(self, val=0, next=None):
  3.         self.val = val
  4.         self.next = next
  6. def quick_sort_linked_list(head):
  7.     if not head or not head.next:
  8.         return head
  10.     pivot = head
  11.     smaller_head = smaller_tail = None
  12.     equal_head = equal_tail = None
  13.     larger_head = larger_tail = None
  15.     current = head.next
  16.     while current:
  17.         if current.val < pivot.val:
  18.             if not smaller_head:
  19.                 smaller_head = smaller_tail = current
  20.             else:
  21.                 smaller_tail.next = current
  22.                 smaller_tail = current
  23.         elif current.val == pivot.val:
  24.             if not equal_head:
  25.                 equal_head = equal_tail = current
  26.             else:
  27.                 equal_tail.next = current
  28.                 equal_tail = current
  29.         else:
  30.             if not larger_head:
  31.                 larger_head = larger_tail = current
  32.             else:
  33.                 larger_tail.next = current
  34.                 larger_tail = current
  36.         current = current.next
  38.     # Recursively sort the smaller and larger partitions
  39.     smaller_sorted = quick_sort_linked_list(smaller_head)
  40.     larger_sorted = quick_sort_linked_list(larger_head)
  42.     # Combine the partitions in the correct order
  43.     result_head = result_tail = ListNode(None)
  44.     if smaller_sorted:
  45.         result_tail.next = smaller_sorted
  46.         result_tail = smaller_tail
  47.     if equal_head:
  48.         result_tail.next = equal_head
  49.         result_tail = equal_tail
  50.     if larger_sorted:
  51.         result_tail.next = larger_sorted
  53.     return result_head.next
  55. # Example usage
  56. head = ListNode(38)
  57. head.next = ListNode(27)
  58. head.next.next = ListNode(43)
  59. head.next.next.next = ListNode(3)
  60. head.next.next.next.next = ListNode(9)
  61. head.next.next.next.next.next = ListNode(82)
  62. head.next.next.next.next.next.next = ListNode(10)
  64. sorted_head = quick_sort_linked_list(head)


 
Quelqu'un pourrait-il expliquer les différentes procédures de sélection de pivot dans Quick Sort, telles que choisir le premier, le dernier, la médiane de trois ou un élément aléatoire ? De plus, comment puis-je m'assurer que mon choix de pivot réduit le risque de complexité temporelle dans le pire des cas ?
 
Tout exemple ou visualisation du processus de sélection de pivot serait grandement apprécié. Merci pour votre aide!

mood
Publicité
Posté le 21-07-2023 à 17:49:18  profilanswer
 

n°2451624
TotalRecal​l
Posté le 21-07-2023 à 18:37:11  profilanswer
 

Mais du coup ça doit être en C ou en Python à la fin ?


---------------
Topic .Net - C# @ Prog
n°2451660
rufo
Pas me confondre avec Lycos!
Posté le 21-07-2023 à 23:11:46  profilanswer
 
n°2451675
rat de com​bat
attention rongeur méchant!
Posté le 22-07-2023 à 16:38:53  profilanswer
 

C'est un exo scolaire ou un truc pour la prod? Dans ce dernier cas il doit y avoir un truc tout fait déjà, en Python ou - en tant que lib externe - en C (tu veux quoi?)?


---------------
matos à vendre
n°2451676
TotalRecal​l
Posté le 22-07-2023 à 16:42:17  profilanswer
 

Tu m'étonnes, sauf besoin ultra spécifique personne ne s'amuse à coder lui-même ce genre de trucs aujourd'hui dans un langage haut niveau, donc ça doit être scolaire.
Maintenant va falloir réussir à concilier ça avec le "Developer senior" et les 25 ans du posteur, perso j'ai pas encore réussi [:caloub]

Message cité 1 fois

---------------
Topic .Net - C# @ Prog
n°2451677
rat de com​bat
attention rongeur méchant!
Posté le 22-07-2023 à 16:49:21  profilanswer
 

TotalRecall a écrit :

Maintenant va falloir réussir à concilier ça avec le "Developer senior" et les 25 ans du posteur, perso j'ai pas encore réussi [:caloub]

Ah oui, bien vu... C'était pas ce Monsieur qui postait en anglais tout le temps aussi? Bon, attendons. :o


---------------
matos à vendre

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C

  Tri rapide pour les listes liées Assistance requise

 

Sujets relatifs
Question de noob sur les listesCréer une page auteur avec Tri Alphabétique
Récupérer automatiquement des listes de produits de Amazon.frTri d'evénénement sous Microsoft edge
(HELP ! ) Tri par ordre Alphabétique AJAX (Help ! )Listes chainee
[JAVA EE] Liste Déroulantes Liées ServletPetite question rapide
créer des listes python en boucle list(n)[PYTH] .PY ou .EXE plus rapide ?
Plus de sujets relatifs à : Tri rapide pour les listes liées Assistance requise

Forum MesDiscussions.Net, Version 2010.2
(c) 2000-2011 Doctissimo
Page générée en 0.066 secondes

Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR