Newsgroup: it.comp.lang.c++
Titolo: Quick Sort

Carissimi... mi rivolgo a voi per un quesito...
C'è qualcuno in grado di spiegarmi come funziona il quick sort? magari
spedendomi anche la codifica... GRAZIE

 spedendomi anche la codifica... GRAZIE
Se hai un compilatore C, o C++, che comprenda i sorgenti
della libreria, non ti serve "la codifica", poiche` ne disponi
gia`; qsort e std::sort sono proprio (tipicamente eccellenti)
implementationi di quickersort (variante migliorata del
Quicksort) e non si potrebbe fare di meglio.
Se non hai di questi sorgenti, dal sito cygnus scarica
quelli di libgcc.
CAPIRE quicksort richiede qualcosa di piu` che non
l'esame dei sorgenti per la sua codifica.
Il concetto-base e` questo: se prendo un "punto di
divisione" nell'array che sto sortando, piu` o meno a
caso, e posso rapidamente eseguire una partizione
dell'array in modo che tutti gli elementi PRIMA di
quello al punto di divisione siano MINORI-EGUALI di
esso, tutti quelli DOPO siano MAGGIORI-EGUALI;
allora, ho diviso il mio array in due porzioni piu`
piccole (mediamente, si puo` sperare, la meta`
ciascuna); applicando, magari recursivamente, la
stessa procedura a ciascuna meta`, posso alla fine
trovarmi ad un array sortato dopo un numero
LOGARITMICO di queste applicazioni.
Se ciascuna applicazione richiede un tempo
LINEARE (O(n) rispetto al numero di elementi),
allora il tempo complessivo di ordinamento
dovrebbe essere O(n Log(n)), cioe` compatibile
con il miglior tempo possibile (come si puo`
dimostrare) per algoritmi d'ordinamento basati
solo su confronto minore/maggiore e scambio.
Resta solo da approfondire il primo passo --
come partizionare l'array come detto?  Ma
aspetto una tua conferma di comprensione di
quanto ho espresso sinora prima di eventuale
proseguimento su questo punto, importante ma
in secondo ordine.
Alex

 l'esame dei sorgenti per la sua codifica.
[snip]
Se vuole passare l'esame, o il compito di informatica,
è meglio che se lo studi...

in secondo ordine.
Io ho capito, potresti continuare?
Oppure consigliarmi dei testi on-line di algoritmistica?
-- 
"Non e` bello cio` che e` bello ma e` bello cio` che piace ... a ME!"
Massimo Lauria a.k.a. Gargamella on Usenet
mailto: 
garga...@mclink.it
Proud member of: NonSense Delivering Service

 è meglio che se lo studi...
Appunto a questo scopo, offrivo le mie osservazioni sulla
"struttura" dell'algoritmo stesso.
Alex

Ecco la mia conferma: Fino a questo punto ho capito... volevo xò solo dire a
Massimo Pironato di non preoccuparsi... non è x un compito e/o esame..
quello che mi hai spiegato non è simile alla ricerca dicotomica (credo si
scriva così) nella quale si divide l'array esattamente a metà e si cerca
l'elemento prima o dopo a seconda che la metà sia + grande o -?


 > in secondo ordine.
Il punto e`: come possiamo _efficacemente_ ordinare
l'array in modo che tutti gli elementi con indice MINORE
di quello scelto (quest'ultimo detto "pivot") siano minori
o eguali del pivot, e tutti quelli successivi, maggiori o
eguali del pivot.  E` fondamentale che questa operazione
sia O(N), cioe` lineare nel numero di elementi dell'array.
Come si puo` ottenerla con una semplice scansione
lineare dell'array, dunque?
Nella spiegazione, per semplicita`, ignoriamo le varie
possibilita` di eguaglianza (che non complicano molto
le cose, ma, tanto per chiarezza).
Facile, tutto sommato: procediamo assieme con due
indici, uno dall'alto e uno dal basso; sinche` i vari
elementi indiciati dall'"indice dal basso" sono minori
del pivot, essi soddisfano gia` la proprieta`, quindi
incrementiamo tranquillamente l'indice dal basso; e
allo stesso modo, sinche` gli elementi indiciati
dall'"indice dall'alto" sono maggiori del pivot, vanno
gia` bene li`, quindi decrementiamo l'indice dall'alto.
Quando l'indice dal basso indica un elemento
maggiore del pivot, e quello dall'alto uno minore
del pivot, basta SCAMBIARE questi due elementi
fra loro, e abbiamo di nuovo stabilito la proprieta`
che ci interessa.  E quando i due indici si incontrano,
abbiamo finito; se il pivot a questo punto e`, ad es,
all'inizio dell'array, basta scambiarlo con l'elemento
ora indicato dall'"indice dal basso" per poi procedere
al cruciale passo recursivo in cui ciascuna delle due
"meta`" cosi` ottenute viene sottoposta allo stesso
trattamento.
A questo punto, l'implementazione e` solo questione
di cura nell'evitare piccoli errori (off-by-one e simili!).
A questo scopo, conviene seguire il consiglio di
codifica di Koenig ("C traps and pitfalls") di usare
sempre intervalli semiaperti che includono il limite
inferiore ma escludono il superiore (come d'altronde
fanno sempre le librerie standard C++, nota bene!).
Le linee-guida in pseudocodice sono dunque:
# semantica di Koenig, intervallo semiaperto:
# interessano, cioe`, gli elementi fra:
#     larray[primoindice] COMPRESO, e
#     larray[ultimoindice] ESCLUSO
def quicksort(larray,primoindice,ultimoindice):
    if ultimoindice<=primoindice+1:
        return    # solo 0-1 elementi, non c'e` lavoro da fare
    # se abbiamo 2 o piu` elementi, c'e` da lavorare...:
    puntocentrale = partiziona(larray,primoindice,ultimoindice)
    # il puntocentrale e` gia` a posto, e quindi:
    quicksort(larray,primoindice,puntocentrale)
    quicksort(larray,puntocentrale+1,ultimoindice)
def partiziona(larray,primoindice,ultimoindice):
    pivot=larray[primoindice]
    basso=primoindice
    alto=ultimoindice
    # invariante I: tutti gli elementi sino a
    # larray[basso] compreso sono <= pivot
    # e tutti quelli da larray[alto] (compreso SE
    # esiste) sono >= pivot; quindi "ancora da
    # esaminare" sono gli indici da basso+1
    # compreso ad alto-1 compreso
    while basso+1<alto-1:
        while basso+1<alto and larray[basso+1]<=pivot:
            basso=basso+1
        while alto-1>basso and larray[alto-1]>=pivot:
            alto=alto-1
        # l'invariante I e` ancora valida ma non varrebbe
        # piu` se incrementassimo basso o decrementassimo
        # alto; pero`...:
        if alto-1>basso+1:
            scambiaelementi(larray,basso+1,alto-1)
            basso=basso+1
            alto=alto-1
            # adesso vale l'invariante I!
    # ora basta sistemare il pivot:
    if basso>primoindice:
        scambiaelementi(larray,primoindice,basso)
    return basso
# e naturalmente, se occorre, definiamo anche:
def scambiaelementi(larray,a,b):
    temp=larray[a]
    larray[a]=larray[b]
    larray[b]=temp
Quest'ultima primitiva non occorre se predefinita, ad
esempio la std::swap delle librerie del C++.
Naturalmente, questo "pseudocodice" e` valido
linguaggio Python, quindi lo si puo` anche eseguire
sotto il relativo interprete, magari aggiungendo gli
opportuni "print" per capire bene cosa succede ai
vari indici ed elementi nei vari casi -- operazione
spesso molto istruttiva.
Alex