Ordinamento non basato su confronti
Salve,
vorrei levarmi una curiosità.
Conosco parecchi algoritmi di ordinamento, che vengono definiti come "basati su confronti", dove implica una limitazione inferiore sempre di $Omega(nlogn)$.
Ora vorrei sapere quali sono quelli "non basati su confronti"? ne avete qualche esempio? Forse li conosco, ma non trovo qualche informazione che li suddivida su questa proprietà...
Questa tipologia per intuizione, direi che utilizza particolari confronti non sull'elemento da ordinare, ma su qualche funzione o proprietà particolare (shell-sort?).
è da parecchio che mi gira in testa sta domanda.
Ringrazio
vorrei levarmi una curiosità.
Conosco parecchi algoritmi di ordinamento, che vengono definiti come "basati su confronti", dove implica una limitazione inferiore sempre di $Omega(nlogn)$.
Ora vorrei sapere quali sono quelli "non basati su confronti"? ne avete qualche esempio? Forse li conosco, ma non trovo qualche informazione che li suddivida su questa proprietà...
Questa tipologia per intuizione, direi che utilizza particolari confronti non sull'elemento da ordinare, ma su qualche funzione o proprietà particolare (shell-sort?).
è da parecchio che mi gira in testa sta domanda.
Ringrazio
Risposte
Lo shell sort si basa sul confronto.
Gli algoritmi non basati sul confronto sfruttano spesso particolari caratteristiche dei dati da ordinare, ad es. famosi sono quelli per l'ordinamento di interi come il bucket sort, il counting sort e il radix sort.
Tuttavia questi algoritmi si rivelano efficienti solo quando i dati in input sono distribuiti in un modo particolare, come ad es. un vettore di interi t.c. la distanza tra il minimo e il massimo elemento è inferiore alla lunghezza del vettore stesso.
Gli algoritmi non basati sul confronto sfruttano spesso particolari caratteristiche dei dati da ordinare, ad es. famosi sono quelli per l'ordinamento di interi come il bucket sort, il counting sort e il radix sort.
Tuttavia questi algoritmi si rivelano efficienti solo quando i dati in input sono distribuiti in un modo particolare, come ad es. un vettore di interi t.c. la distanza tra il minimo e il massimo elemento è inferiore alla lunghezza del vettore stesso.
Sono confuso. Il confronto è parte fondamentale di un ordinamento in quanto lo definisce. Cioè quello che noi chiamiamo confrontare è il mettere in ordine due elementi.
Da un punto di vista un po' più astratto, counting sort, radix sort e bucket sort... sono tutti più o meno basati sull'esistenza di una "mappa" (non necessariamente iniettiva) tra gli elementi da ordinare e un sottointervallo di interi o numeri reali. L'idea di base è la seguente.
Supponi di avere la tua successione \( a_1, \dots, a_n \) in cui ogni elemento ha un valore in un qualche insieme \(T\) e di avere una mappa \( f : T \to [s, e) \). Consideriamo quindi di prendere una successione \( r_0, r_1, \dots, r_k \) di numeri reali tali che \( s = r_0 < r_1 < \dots < r_{k-1} < r_{k} = e \). Se a questo punto definiamo \( H_j = \{ a_i \; : \; 1 \le i \le n \, \wedge \, a_i \in [r_{j-1}, r_{j})\} \) e \( S_j = \sum_{i=1}^{j} |H_i| \) scopriamo che mettendo tutti gli elementi (in ordine di comparsa) in \( H_j \) nell'intervallo di indici \( S_{j-1} < i \le S_j \) (\(S_0 = 0\) per definizione) si ottiene una specie di ordinamento, con tutti gli elementi di \(H_j\) che seguono quelli di \(H_l\) per ogni \(l < j\).
Nel caso del counting sort, si richiede un ordinamento completo degli elementi e quindi una biezione tra \(T\) e un intervallo dei naturali del tipo \( 0, 1, \dots, k \). Gli intervalli in questo caso sono semplicemente intervalli contenenti un singolo numero naturale. Tutti gli elementi in un qualche \( H_j \) sono quindi da considerare come uguali.
Il problema del radix sort è che quando il numero di valori in \( T \) è molto grande, il metodo diventa impraticabile. Il radix sort itera più volte il procedimento base ordinando di volta in volta usando mappe diverse. Supponi di avere cioè la biezione descritta prima nel caso del counting sort e di ordinare ogni volta in base ad una cifra decimale diversa partendo da quella meno significativa a quella più significativa. Al primo passaggio tutti gli elementi saranno ordinati in base alla cifra meno significativa, al secondo saranno ordinati in base alle due meno significative (gli elementi vengono inseriti in ordine per cui non viene distrutto l'ordinamento precedente) e così via. Non è l'unica mappa possibile per questo metodo. Si possono usare basi diverse o anche mappe come la seguente. Supponi di voler ordinare delle date. Puoi allora prima ordinare in base al giorno del mese, poi ai mesi (e i giorni compariranno ordinati) e quindi l'anno.
Il bucket sort considera invece una mappa verso i numeri reali nell'intervallo [0, 1) assumendo che questi numeri siano uniformemente distribuiti. L'idea è quindi quella di separare i numeri reali in diversi sotto-intervalli come descritto precedentemente e poi ordinare separatamente ogni singolo bucket (così vengono chiamati gli \(H_j\) usando tendenzialmente l'insertion sort. E' più difficile vedere come mai questo ha complessità media uguale a O(n + k) ma si usa il fatto che i numeri siano uniformemente distribuiti. Non è infatti molto efficiente nel caso in cui non lo siano.
Supponi di avere la tua successione \( a_1, \dots, a_n \) in cui ogni elemento ha un valore in un qualche insieme \(T\) e di avere una mappa \( f : T \to [s, e) \). Consideriamo quindi di prendere una successione \( r_0, r_1, \dots, r_k \) di numeri reali tali che \( s = r_0 < r_1 < \dots < r_{k-1} < r_{k} = e \). Se a questo punto definiamo \( H_j = \{ a_i \; : \; 1 \le i \le n \, \wedge \, a_i \in [r_{j-1}, r_{j})\} \) e \( S_j = \sum_{i=1}^{j} |H_i| \) scopriamo che mettendo tutti gli elementi (in ordine di comparsa) in \( H_j \) nell'intervallo di indici \( S_{j-1} < i \le S_j \) (\(S_0 = 0\) per definizione) si ottiene una specie di ordinamento, con tutti gli elementi di \(H_j\) che seguono quelli di \(H_l\) per ogni \(l < j\).
Nel caso del counting sort, si richiede un ordinamento completo degli elementi e quindi una biezione tra \(T\) e un intervallo dei naturali del tipo \( 0, 1, \dots, k \). Gli intervalli in questo caso sono semplicemente intervalli contenenti un singolo numero naturale. Tutti gli elementi in un qualche \( H_j \) sono quindi da considerare come uguali.
Il problema del radix sort è che quando il numero di valori in \( T \) è molto grande, il metodo diventa impraticabile. Il radix sort itera più volte il procedimento base ordinando di volta in volta usando mappe diverse. Supponi di avere cioè la biezione descritta prima nel caso del counting sort e di ordinare ogni volta in base ad una cifra decimale diversa partendo da quella meno significativa a quella più significativa. Al primo passaggio tutti gli elementi saranno ordinati in base alla cifra meno significativa, al secondo saranno ordinati in base alle due meno significative (gli elementi vengono inseriti in ordine per cui non viene distrutto l'ordinamento precedente) e così via. Non è l'unica mappa possibile per questo metodo. Si possono usare basi diverse o anche mappe come la seguente. Supponi di voler ordinare delle date. Puoi allora prima ordinare in base al giorno del mese, poi ai mesi (e i giorni compariranno ordinati) e quindi l'anno.
Il bucket sort considera invece una mappa verso i numeri reali nell'intervallo [0, 1) assumendo che questi numeri siano uniformemente distribuiti. L'idea è quindi quella di separare i numeri reali in diversi sotto-intervalli come descritto precedentemente e poi ordinare separatamente ogni singolo bucket (così vengono chiamati gli \(H_j\) usando tendenzialmente l'insertion sort. E' più difficile vedere come mai questo ha complessità media uguale a O(n + k) ma si usa il fatto che i numeri siano uniformemente distribuiti. Non è infatti molto efficiente nel caso in cui non lo siano.
"vict85":
Sono confuso. Il confronto è parte fondamentale di un ordinamento in quanto lo definisce. Cioè quello che noi chiamiamo confrontare è il mettere in ordine due elementi.
Sì, ma come ha spiegato apatriarca non è detto che tu debba usare confronti "espliciti" tra questi elementi ( o per lo meno l'rodinamento non è totalmente determinato dalla sequenza di confronti). In questo modo il lower bound ricavato con gli alberi di decisione cessa di valere*, ma comunque, negli algoritmi conosciuti, la complessità lineare si raggiunge solo per determinate distribuzioni degli elementi.
*non so se esista un altro lower bound, ho provato a cercare, ma senza successo, ma credo che per una sequenza di $n$ reali qualsiasi non si riesca ad abbattere il muro di $O(n log n)$ passi nella real-RAM.
La complessità lineare nel counting sort e nel radix sort si ha anche nel caso peggiore. La complessità dell'algoritmo non dipende infatti dagli elementi. Nota che puoi usare il radix sort anche per ordinare i numeri floating point sfruttando le proprietà della loro rappresentazione binaria.
Sì, ma per es. il counting sort è lineare nel numero degli elementi e nel valore del massimo elemento, che però può essere esponenziale rispetto alla dimensione dell'input. Quindi non è lineare nella dimensione dell'input, a meno che gli elementi non siano distribuiti in un certo modo.
Non so di cosa tu stia parlando. La complessità del counting sort è lineare sia nel range degli elementi sia nella dimensione dell'input e lo stesso vale anche per il radix sort, ma non per il bucket sort.
La complessità del counting sort è $O(n + k)$ (vedi qui) dove $n$ è il numero di elementi in input, $k$ il valore dell'elemento più grande (o altrimenti la differenza tra l'elemento più grande e quello più piccolo), ma $k$ può essere un numero molto grande, addirittura esponenziale rispetto alla dimensione dell'input (ciò è un po' impreciso, per essere precisi bisognerebbe fissare un modello di calcolo ben definito, ma direi di sorvolare).
Sì, lo so qual'è la complessità. Ma il counting sort non ha senso usarlo in casi in cui gli elementi possono assumere valori troppo grandi. Il radix sort d'altra parte non ha quella complessità. Si possono infatti ordinare numeri a 64 bit facendo 9 passaggi sull'array, uno per ogni byte più un passaggio per creare le tabelle, e uno sulle 8 tabelle. Per cui la complessità diventa \(O(9N + 8 \cdot 256)\).
Sono d'accordo con te. Probabilmente non mi sono spiegato bene: volevo semplicemente dire che non esiste un algoritmo in grado di ordinare $n$ reali in tempo lineare nella dimensione dell'input se non si applicano restrizioni sulla "natura" di questi reali, come ad es. il fatto che siano limitati. Gli algoritmi non basati sul confronto funzionano meglio (per lo meno asintoticamente) quando invece l'input ha caratteristiche particolari (anche se ragionevoli).
davvero molto interessante, vi ringrazio tutti, sapevo mi davate una bella risposta approfondita
un'ultima cosa, riguardo questa affermazione di Deckard:
intendi $Omega(nlogn)$? se non non mi torna.
Comunque direi che può valere o anche no, dipende dai dati e dalla "mappa" di ordinamento o no?
un'ultima cosa, riguardo questa affermazione di Deckard:
*non so se esista un altro lower bound, ho provato a cercare, ma senza successo, ma credo che per una sequenza di n reali qualsiasi non si riesca ad abbattere il muro di $O(nlogn)$ passi nella real-RAM.
intendi $Omega(nlogn)$? se non non mi torna.
Comunque direi che può valere o anche no, dipende dai dati e dalla "mappa" di ordinamento o no?
"hamming_burst":*non so se esista un altro lower bound, ho provato a cercare, ma senza successo, ma credo che per una sequenza di n reali qualsiasi non si riesca ad abbattere il muro di $O(nlogn)$ passi nella real-RAM.
intendi $Omega(nlogn)$? se non non mi torna.
Sì sì ovvio, ho sbagliato a scrivere
Comunque direi che può valere o anche no, dipende dai dati e dalla "mappa" di ordinamento o no?
Dipende dal modello di calcolo utilizzato: esistono diversi lower bound per diversi modelli di calcolo per il problema dell'ordinamento (oltre a quello classico valido per gli albero di decisione e quindi solo per gli algoritmi basati sul confronto); il difficile è trovarne uno che valga in un modello sufficientemente generale (come la real-RAM ad es.) per escludere la possibilità di costruire un algoritmo che sfrutti qualche proprietà particolare e riesca quindi ad abbattere il lower bound.
Nel caso dell'ordinamento di numeri reali, è comunque ancora possibile utilizzare il radix sort. Tutte le rappresentazione in virgola mobile o fissa sono in biezione con gli interi con lo stesso numero di bit e possono quindi essere ordinati, con qualche piccola variazione, come interi. Ovviamente questo discorso non vale sempre, per esempio quando i numeri siano rappresentati da frazioni, o quando il numero di bit sia variabile e non fisso. Due interessanti articoli sull'argomento sono Radix Sort Revisited e Radix Tricks. Quest'ultimo articolo A question of sorts confronta poi diversi algoritmi di ordinamento sulla PS3 discutendo poi di un algoritmo di ordinamento parallelo basato sul merge sort.
"Deckard":
Dipende dal modello di calcolo utilizzato: esistono diversi lower bound per diversi modelli di calcolo per il problema dell'ordinamento
fantastico ti ringrazio molto della precisazione
@apatriarca:
interessanti articoli, grazie
Be se tu prendi un insieme di numeri (un array) e gli scambi casualmente hai effettuato un ordinamento(o un disordinamento O_O) casuale (nel senso che l'ordine cambia). E per fare ciò non hai bisogno di confronti tra gli elementi. Che poi questo tipo di ordinamento abbia qualche utilità pratica è ancora da vedersi.. (be se per un gioco dobbiamo mischiare un mazzo di carte allora il gioco è fatto se ogni carta è un numero dell'array).
Era questa la tua domandao?
Era questa la tua domandao?
Ma hai letto il resto del post? Quello di cui parli non è comunque un ordinamento, ma solo una permutazione. C'è differenza tra i due termini. Gli algoritmi a cui faceva riferimento era decisamente altri e ne abbiamo già discusso.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo