Tri rapide pour les listes liées Assistance requise

Tri rapide pour les listes liées Assistance requise - C - Programmation

Marsh Posté le 21-07-2023 à 17:49:18    

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!

Reply

Marsh Posté le 21-07-2023 à 17:49:18   

Reply

Marsh Posté le 21-07-2023 à 18:37:11    

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


---------------
Réalisation amplis classe D / T      Topic .Net - C# @ Prog
Reply

Marsh Posté le 21-07-2023 à 23:11:46    

Reply

Marsh Posté le 22-07-2023 à 16:38:53    

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?)?


---------------
Si vous ouvrez un sujet merci de ne pas le "laisser mourir" subitement et de le marquer comme "résolu" le cas échéant!
Reply

Marsh Posté le 22-07-2023 à 16:42:17    

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

---------------
Réalisation amplis classe D / T      Topic .Net - C# @ Prog
Reply

Marsh Posté le 22-07-2023 à 16:49:21    

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


---------------
Si vous ouvrez un sujet merci de ne pas le "laisser mourir" subitement et de le marquer comme "résolu" le cas échéant!
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed