[C] Algoritmo ordinamento

[Gio Games]

Salve a tutti ragazzi.

Devo leggere da file una serie di campi e ordinarli in base ad una chiave scelta dall'utente.

La prima cosa che mi è venuta in mente è stato caricare i dati da file, creare un array e ordinarlo tramite mergesort dato che ho la necessità di non modificare l'ordine relativo delle chiavi (mergesort infatti è stabile).
Questo avverrebbe con una complessità asintotica pseudolineare ovvero n*log n.

Ora però mi sorge il dubbio che esista una tecnica migliore per implementare il tutto.

Qualsiasi spunto è ben accetto.

Grazie in anticipo

[wizard1993]

non c'è sistema migliore, in quanto non mi ricordo per quale teorema un ordinamento basato su confronti non può scendere sotto n log n di complessità
eventualmente puoi vedere se il bucket sort fa al caso tuo in quanto in alcuni casi particolari può risolvere in n passaggi l'ordinamento
comunque se i campi da ordinare sono di grandi dimensioni conviene usare il quicksort in quanto è in place e richiede uno stack aggiuntivo minore del mergesort
altra scelta è quella di utilizzare un hashtable

[sirus]

Che un ordinamento per confronti non può scendere sotto n*log(n) è effettivamente dimostrabile.
Per quanto riguarda la scelta dell'algoritmo io non direi che il mergesort è sempre una buona soluzione se consideri che anche lui è implementabile in-place al pari del quicksort, quindi, se dovessi scegliere, io non avrei dubbi.

[Gio Games]

Grazie ragazzi ad entrambi per le risposte.

Non vorrei sbagliarmi ma il quicksort non dovrebbe essere stabile a differenza del mergesort.

Quindi in base alle vostre risposte sarei sempre più propenso a svolgere il lavoro come pensato all'inizio.
Costruire dinamicamente una lista con i record contenuti all'interno del file (dato che non ne conosco a priori il numero), creare così il mio array di record ed utilizzare infine mergesort per ordinarlo in base alla chiave scelta dall'utente.

Avrei un peggioramento della complessità dato che avrei in più gli n elementi da aggiungere alla lista e poi copiare sull'array, ma asintoticamente rimarrei sempre su n*log(n) se non sbaglio giusto?

Grazie mille a tutti coloro che risponderanno

[wizard1993]

alla fine quello è l'unico sistema, il merge lo fai in place o no?

[Gio Games]

alla fine quello è l'unico sistema, il merge lo fai in place o no?

No in quanto il mergesort non lavora sul posto se non sbaglio

[sirus]

No in quanto il mergesort non lavora sul posto se non sbaglio
Puoi implementarlo anche in-place ;) lo svantaggio è che non è stabile implementato così. :(

[Gio Games]

Puoi implementarlo anche in-place ;) lo svantaggio è che non è stabile implementato così. :(

Capisco, "purtroppo" mi serve un algoritmo stabile quindi non posso implementarlo in place.

Grazie mille a tutti per gli spunti, se avete ancora idee non esitate :)

[wizard1993]

Capisco, "purtroppo" mi serve un algoritmo stabile quindi non posso implementarlo in place.

Grazie mille a tutti per gli spunti, se avete ancora idee non esitate :)

perchè ti serve necessariamente stabile?
ho fatto svariati test con un implementazione del quicksort che ho fatto io e su 1 milione (scritto appositiamente un programma, non misono certamente messo a farlo a mano :p ) di array di lunghezza variabile fra 10 e 10000 elementi e mai siamo scesi sotto 3/2 nlog n passagi.
in marge sort in place non l'ho mai fatto quindi non so come vada.
tutto sta che ho avuto anche io da affrontare un problema simile che richiedeva di ordinare oggetti in vari modi, e alla fine confrontando il tempo fra quicksort in place e merge sort non in place ho notato che la velocità alla fine pendeva per il quicksort in quanto a meno che non si faccia un array di riferimenti, lo scrivere e lo spostare oggetti di grosse dimensioni dall'array di swap a quello buono, richiedeva più tempo che fare alcuni scambi in più

[Gio Games]

Mi serve stabile in quanto ho la necessità di non cambiare l'ordine relativo prodotto da altre chiavi. Altrimenti sarei stato anche io più propenso al quick sort

[wizard1993]

Mi serve stabile in quanto ho la necessità di non cambiare l'ordine relativo prodotto da altre chiavi. Altrimenti sarei stato anche io più propenso al quick sort

allora da quel poco che so io non si dice stabile :D
per stabile io indentendo un algoritmo in cui caso migliore caso peggiore e caso medio coincidano come nel mergesort, magari sbaglio io

[Gio Games]

http://it.wikipedia.org/wiki/Algoritmo_di_ordinamento

Leggendo la sezione "Stabilità di un algoritmo" credo che si intenda quello che dico io, altrimenti non avrei capito niente di "Algoritmi e strutture dati" :D

[wizard1993]

http://it.wikipedia.org/wiki/Algoritmo_di_ordinamento

Leggendo la sezione "Stabilità di un algoritmo" credo che si intenda quello che dico io, altrimenti non avrei capito niente di "Algoritmi e strutture dati" :D

mi sa che quello che sbaglia sono io, sai autodidatta su libri o in inglese e quindi magari sbaglio io a fare una traduzione con un sinonimo o su libri in italiano non tradotti benissimo, alla fine qualche errore ci scappa

[Gio Games]

Figurati, ti capisco. Sbagliare da autodidatta è facilissimo. Io l'ho fatto fino a quest'anno e mi sono accorto di taaaante cose apprese non proprio per come erano in realtà :D

Però è una soddisfazione unica essere autodidatta.