Olimpo Informatico

ZapoTeX

Ciao a tutti,

sono sempre io, sto programma mi sta tirando scemo Sad

.

Ho 5 array di circa 200,000 righe. Devo ordinarli (tutti) a seconda del valore di uno di essi. Intendo che l'ordine degli array 2, 3, 4 e 5 deve essere basato sul valore dell'array 1. Come fare in Excel sort data by column A, ma ordinare anche le colonne B, C, D, E.

Ho provato con gli ingenui "insertion sort" e "bubble sort", ma sono troppo lenti, ho bisogno di un fast sort di tipo NlogN.

Ci sono svariate implementazioni in c scaricabili da internet (heap sort è popolarissimo), purtroppo però restituiscono solo l'array ordinato... Io avrei bisogno che mi restituissero anche una MAPPA con i cambiamenti fatti (del tipo un array map[200,000], dove map[i]=la posizione originaria dell'elemento che ora sta in posizione i.

In questo modo, mando alla procedura l'array che contiene i numeri per l'ordine e, con la mappa, mi ordino gli altri 4 array.

Sapete di qualche cosa che funzioni così?

Grazie mille e a presto!

SverX · Inviato: 21 Feb 2011 16:35 Oggetto:

banalmente mi verrebbe da suggerirti di cambiare i 5 array da 200mila elementi ognuno in un array solo, ma composto di strutture dove hai un membro per ognuno degli array iniziali (cioè 5).
Così potrai ordinare l'array di strutture secondo il membro che ti conviene mantenendo insieme i dati.

ZapoTeX · Inviato: 21 Feb 2011 16:55 Oggetto:

Ottima idea! Interessante... Sai cosa però? Se ogni volta che due numeri si scambiano lu deve smazzarsi lo scambio dell'intera struttura, non perdo velocità rispetto ad ordinarmi un solo array di interi e poi usare la mappa sugli altri, che è un'operazione O(N)?

Guarderò comunque a come fare la tua soluzione. Grazie mille!

SverX · Inviato: 21 Feb 2011 18:49 Oggetto:

freemind · Inviato: 21 Feb 2011 18:58 Oggetto:

Come algoritmo io penso ad un bel quicksort (magari senza ricorsione appoggiandoti ad un albero) e come dice SverX usare le strutture.
Però invece di usare degli array e basta penserei ai puntatori così ti ritrovi addirittura a scambiare gli indirizzi delle strutture così gli scambi sono su numeri interi.
In pratica usi un array di puntatori ognuno dei quali punta a una struttura (che contiene anche l'indice originale).
Gli elementi da scambiare sono i pointer.
Però hai veramente tanti elementi, io ribadisco che sarebbe ipotizzabile riformulare il problema e passare all'uso di altre strutture

ZapoTeX · Inviato: 21 Feb 2011 21:36 Oggetto:

Grazie mille!!!

Buona giornata!