Newsgroup: it.comp.lang.c++
Titolo: Algoritmo di ordinamento

Devo leggere da un file diverse stringhe e devo ordinarle alfabeticamente.
Mi potete indicare un algoritmo di ordinamento veloce ed elegante? (mi sono
rotto del bubble sort)
Grazie
--
Ciao da Ska Man (Baldo)
akira_sendo[at]
libero.it
Togli "NOSPAM" per risposte via E-Mail
----------
La prima regola di internet:  mai fare i conti senza l'hoster

 Grazie
Il "Quick Sort" è quello che fa per te!

 ha scritto nel messaggio
news:HtYC8.42021$US3.9...@twister1.libero.it...

 dove lo posso trovare?

  dove lo posso trovare?
Buffo, ne ho postato due versioni per due diversi linguaggi su
it.comp.programmare.win32 proprio ieri l'altro.
Ecco una versione piu` concisa (ma appunto per questo
forse un po' meno leggibile):
def qsort(xs):
  return qsort([y for y in xs[1:] if [y] < xs[:1]]
    ) + [xs[:1]] + qsort([y for y in xs[1:] if [y] >= xs[:1]])
In linguaggi piu` a basso livello, come C++, risulta piu`
difficile programmare quicksort in una singola istruzione,
ma per fortuna la libreria standard del C++ te ne offre
uno precotto, std::sort in <algorithm>.  E` MOLTO piu`
efficiente del vecchio qsort del C (che il C++ continua
ad offrire per compatibilita`, v. <cstdlib>) poiche` evita
livelli di indirettezza.  D'altra parte anche in linguaggi a
piu` alto livello, come Python, si usa in pratica sempre
la versione di libreria (xs.sort() per esempio), che ha di
solito altri vantaggi (quella di Python e` un samplesort
ottimizzato da paura...).
Alex

>> y = qsort(x)
Traceback (most recent call last):
  File "<pyshell#2>", line 1, in ?
    y = qsort(x)
  File "<pyshell#0>", line 2, in qsort
    return qsort([y for y in xs[1:] if [y] < xs[:1]]
  File "<pyshell#0>", line 2, in qsort
    return qsort([y for y in xs[1:] if [y] < xs[:1]]
  File "<pyshell#0>", line 2, in qsort
    return qsort([y for y in xs[1:] if [y] < xs[:1]]
  File "<pyshell#0>", line 2, in qsort
    return qsort([y for y in xs[1:] if [y] < xs[:1]]
....
Exception in Tkinter callback
Traceback (most recent call last):
  File "C:\PYTHON22\lib\lib-tk\Tkinter.py", line 1292, in __call__
    return apply(self.func, args)
  File "C:\PYTHON22\Tools\idle\PyShell.py", line 594, in enter_callback
    self.runit()
  File "C:\PYTHON22\Tools\idle\PyShell.py", line 613, in runit
    more = self.interp.runsource(line)
  File "C:\PYTHON22\Tools\idle\PyShell.py", line 191, in runsource
    return InteractiveInterpreter.runsource(self, source, filename)
  File "C:\PYTHON22\lib\code.py", line 87, in runsource
    self.runcode(code)
  File "C:\PYTHON22\Tools\idle\PyShell.py", line 287, in runcode
    self.showtraceback()
  File "C:\PYTHON22\Tools\idle\PyShell.py", line 246, in showtraceback
    InteractiveInterpreter.showtraceback(self)
  File "C:\PYTHON22\lib\code.py", line 167, in showtraceback
    map(self.write, list)
  File "C:\PYTHON22\Tools\idle\PyShell.py", line 296, in write
    self.tkconsole.console.write(s)
  File "C:\PYTHON22\Tools\idle\PyShell.py", line 679, in write
    self.shell.write(s, self.tags)
  File "C:\PYTHON22\Tools\idle\PyShell.py", line 670, in write
    raise KeyboardInterrupt
KeyboardInterrupt
Forse ci vogliono due righe.
Tra le altre cose, mi domando:
anche in Python e` possibile ridefinire gli operatori < e >= in modo
che y >= x sia diverso da !(y < x)?
E` per questo che ripeti due volte la stessa serie di confronti, o e`
solo per farci stare, a tutti i costi, tutto in una riga?
ciao
Massimo

rotto del bubble sort)
Il bubble sort infatti é il più semplice fra gli algoritmi di
ordinamento, ma anche il meno efficiente e va bene soltanto se gli
elementi da ordinare non sono tanti.
La libreria standard comunque mette già da sola a disposizione nel
modulo <algorithm> un algoritmo generico per il sorting sulle
sequenze, la cui efficienza é buona(molto migliore della vecchia qsort
del C, in quanto non ha bisogno di puntatori a funzione), ciò che é
importante però é che esistano dei criteri validi per poter effettuare
il sorting sugli elementi della tua sequenza, ma nel caso che siano
std::string non vi é alcun problema in quanto la classe prevede già
gli opportuni overload degli operatori di confronto.
Ti fornisco un abbozzo di come potrebbe essere realizzato l'algoritmo,
come vedrai é molto semplice.
#include<fstream>
#include<vector>
#include<string>
#include<algorithm>
typedef std::vector<std::string> vtstr;
void readstring(vtstr &v)
{
std::string riga;
std::ifstream f1("filestr.txt");
while(std::getline(f1,riga))
	{
	v.push_back(riga);
	}
f1.close();
}
int main()
	{
	vtstr myv;
	readstring(myv);
	std::sort(myv.begin(),myv.end());
    return 0;
    }
Ti ricordo inoltre che la lib.standard prevede anche l'algoritmo
std::stable_sort , che a differenza di sort mantiene l'ordine relativo
agli elementi uguali e può essere più efficiente in determinati casi.
Il Ghenio
---------
// TODO: Place your ass here

 rotto del bubble sort)
Mettile in uno std::set<std::string> .  Inserzione e ricerca garantite
O(N lnN).  Il default e' l'ordine lessicografico (si dira' cosi' in
italiano?).
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html
Dept. of Physics, Univ. of Padova, Italy          loreti at pd dot infn dot it


ti offendi se ti chiedo di spiegarmi l'istruzione?

 italiano?).
 
pero` non funziona se ci sono due stringhe uguali. Penso che un bel 
std::vector + std::sort possa essere la soluzione migliore.
ciao Anto
-- 
Antonio Cuni, 19 anni, studente
Brainbench C++ Master: 4.73, higher than 99% of all previous test takers.
C Language: 3.79, higher than 92% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it

 O(N lnN).  
sicuro? Non sono garantite in O(lnN)? (con NlnN sarebbero lente in 
effeti...)
BTW: priority_queue se non sbaglio è implementata come heap, quindi 
forse a 'sto punto sarebbe migliore.
Maurizio

 ti offendi se ti chiedo di spiegarmi l'istruzione?
Certamente no!  Questa istruzione def crea una funzione
chiamata qsort che prende un parametro xs e torna il
valore di una espressione che e` la somma di tre valori
(come indicato dai segni + interposti fra di essi):
  qsort([y for y in xs[1:] if [y] < xs[:1]])
  xs[:1]
  qsort([y for y in xs[1:] if [y] >= xs[:1]])
OK sin qua?  OK, il valore di mezzo e` "la fetta di xs sino
all'elemento [1] escluso", cioe`, visto che gli indici iniziano
da 0, la sottolista di xs composta dal suo primo elemento.
Il primo e il terzo valore sono chiamate recursive a qsort
con argomenti due "list comprehensions" che permettono
di costruire liste al volo.  La prima dice: quegli y che sono
in xs[1:] (la sottolista di xs composta da tutti gli elementi
meno il primo) se minori del primo; l'altra, idem ma "se
maggiori o eguali" del primo.
Manca l'istruzione di if per evitare la recursione infinita
quando arriviamo alla lista vuota: c'era nell'altro qsort che
ho postato in questo thread ma ho sbagliato l'editing
preparando questa versione e l'ho erroneamente rimossa!-).
In alternativa all'if, per tenere tutto in una sola istruzione,
potremmo scrivere 
return xs and qsort([y for y in xs[1:] if [y] < xs[:1]]
    ) + xs[:1] + qsort([y for y in xs[1:] if [y] >= xs[:1]])
visto che 'and' "cortocircuita".
Quindi riassumendo quest'unica istruzione dice: per fare
un quicksort, concatena il quicksort di tutti gli elementi
minori del primo, poi il primo, poi il quicksort di tutti gli
altri elementi maggiori o equali al primo (ma se la lista
e` vuota il suo quicksort e` pure una lista vuota).
Quicksort e` un algoritmo fragile: se la lista d'ingresso
e` GIA` sortata, tutti gli elementi sono >= del primo,
quindi la profondita` di recursione diventa O(N), ad
esempio.  Infatti, nella sua forma pura qui espressa,
non e` usabile in produzione.  Bisogna complicarlo per
scegliere bene il 'pivot', l'elemento (che nel quicksort
puro e` sempre il primo) su cui si fa la scelta del minori
e maggiori-eguali.  Procedendo su questa strada si
arriva al samplesort, *decisamente* piu` complicato ma
con prestazioni eccezionali.  Ma appunto per le sue
complicazioni, meglio lasciarlo alle librerie:-).
Alex

scegliere bene il 'pivot', l'elemento (che nel quicksort
...
Oppure prendere molto semplicemente l'elemento di mezzo:
e' possibile costruire artificialmente casi "patologici",
ma almeno il caso abbastanza frequente di array gia'
ordinati o quasi-ordinati (o ordinati al contrario o
quasi) non crea problemi.
Andrea

 quasi) non crea problemi.
Purtroppo i casi problematici non sono pochi, ad esempio
un array di elementi tutti eguali, salvo che non lo trovi con
ulteriori complicazioni.  samplesort e` un'altra cosa... non e`
solo la scelta del pivot, ma becca una serie di casi che,
saranno anche patologici, ma capitano spesso in realta`.
Alex

 solo per farci stare, a tutti i costi, tutto in una riga?
La seconda che hai detto, in sostanza.  Non e` particolarmente
comodo minimizzare il numero di confronti, e neppure cambia molto
in termini di prestazioni.
Alex


Perché non un multiset allora?

 writes:

Esatto.  Un vettore ordinato (seguito da std::binary_search e parenti)
va benissimo se deve essere riempito una volta sola e poi soltanto
utilizzato; visto che dalle frasi dell'OP traspare la necessita' di
aggiornamento del container che deve essere in ogni momento ordinato,
insisto con std::[multi]set .


 insisto con std::[multi]set .
 
alla luce degli ultimi messaggi concordo anche io. Quando avevo mandato 
il post prima non avevo capito che l'OP avesse necessita` di avere il 
contenitore ordinato durante i singoli inserimenti.
ciao Anto
-- 
Antonio Cuni, 20 anni, studente


 contenitore ordinato durante i singoli inserimenti.
Il multiset e' perfetto perche' c'e' gia'. Dal punto di vista
prestazionale dal momento che le stringhe sono lette da file penso che
persino una straight insertion in un vector<string> non sposti le cose
di un granche'.
Ciao,
Nicola