Tri sur grosses volumétries

**crashtib** · 19/05/2009, 15h22

Hello,

je voulais savoir, parmi tous les algorithmes de tri élaborés à ce jour, lequel serait le plus adapté pour une grosse volumétrie (>10 millions d'entrées). Ces entrées sont sur un fichier, et le langage est le C. La sortie doit être en fichier aussi.

**pseudocode** · 19/05/2009, 15h30

Vu la taille, je commencerais par splitter le fichier et trier chaque partie (en mémoire, avec un quicksort), puis ensuite construire le fichier final trié.

**crashtib** · 19/05/2009, 15h36

d'accord.

mais comment trier ensuite entre elles les sous parties?

et comment splitter un gros fichier? (sous unix)

**pseudocode** · 19/05/2009, 17h37

Envoyé par crashtib

mais comment trier ensuite entre elles les sous parties?

Par exemple, si chaque partie triée est stockée dans un fichier différent (part-xxxx), tu lis la premiere entrée de chaque fichier. La plus petite entrée est insérée dans le fichier final et tu avances d'un cran de la fichier part-xxxx dont est issue l'entrée

part-A = 2,3,5,6
part-B = 1,5,7,9
part-C = 4,6,8,9
final = (vide)

etape 1 : entreeA = 2, entreeB = 1, entreeC = 4
=> minimum : entréeB = 1
=> ajouter dans final : "1"
=> on avance dans le fichier part-B

etape 2 : entreeA = 2, entreeB = 5, entreeC = 4
=> minimum : entréeA = 2
=> ajouter dans final : "2"
=> on avance dans le fichier part-A

etc.

et comment splitter un gros fichier? (sous unix)

Bonne question. faut aller voir sur le forum adequat.