Discussion :

[crashtib]

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]

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]

d'accord.

mais comment trier ensuite entre elles les sous parties?

et comment splitter un gros fichier? (sous unix)

[pseudocode]

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.

[crashtib]

je te remercie de tes réponses éclairées. en plus ça va me faire bosser :youpi: .

bonne fin de journée à toi

[crashtib]

heu, sinon un bon gros sort bien gras sur unix? comme on dit un informaticien c'est fénéant...?

[pseudocode]

heu, sinon un bon gros sort bien gras sur unix? comme on dit un informaticien c'est fénéant...?

C'est aussi une possibilité, mais ca n'a plus de rapport avec l'algorithmique.

[Mac LAK]

Une bonne ressource : http://www.dailly.info/Tri-fusion

Dans mes souvenirs, le problème du tri de très très grands tableaux / fichiers pose le souci de la copie / déplacement des données, voire dans certains cas le problème du déplacement du pointeur de fichier (ce qui coûte un déplacement de tête de lecture, qui n'est pas "gratuit"...).

Le "truc", avec par exemple un très grand fichier, c'est qu'il est "inutile" de séparer le fichier en plusieurs parties et donc de le copier : tu peux t'en sortir en ouvrant N handles de fichier sur le même "gros" fichier initial, et en jouant avec les pointeurs de fichier pour "déplacer" le "début" d'un sous-fichier. Bien sûr, dans ce cas, les tests de type "eof()" sont interdits, c'est à toi de calculer le "EOF" en fonction de la position courante et de la fin théorique du bout de fichier.

Tu effectues ensuite la fusion dans des fichiers temporaires ou, mieux, tu mixes plusieurs algos ensemble :
- Par exemple, tri fusion jusqu'à arriver à une taille "décente" pour un QuickSort (ex : de 5.000 à 10.000 entrées, appelons cette taille limite K).
- Tri rapide d'un bloc de taille relativement importante par QuickSort.
- Remontée dans la récursion du tri fusion et création d'un fichier temporaire contenant un bloc de 2K entrées.
- Fusion successive des blocs de données : on peut décider de conserver les fichiers temporaires existants, ou au contraire de trier "sur place" en écrasant les données originales, tout dépend de tes contraintes. Si tu es certain de travailler déjà sur une copie des données initiales, autant écraser. Sinon, faudra faire des copies impérativement.

J'espère avoir été assez clair.

[crashtib]

je te remercie de toutes ces précieuses informations.

Parc que je ne suis pas en avance, j'ai décidé d'utiliser la commande system("sort fichier.csv"); je suis donc désolé pour tous les soucis que j'ai causé. Néanmoins, si je trouve un peu de temps, je m'y mettrai c'est promi

merci à tous