In questo articolo, discuteremo importanti proprietà di diverse tecniche di ordinamento tra cui la loro complessità, stabilità e vincoli di memoria. Prima di capire questo articolo, dovresti capire le basi delle diverse tecniche di ordinamento (Vedi: Tecniche di ordinamento).
Analisi della complessità temporale –
Abbiamo discusso la complessità migliore, media e peggiore delle diverse tecniche di ordinamento con possibili scenari.
Ordinamento basato sul confronto –
Nell’ordinamento basato sul confronto, gli elementi di una matrice sono confrontati tra loro per trovare la matrice ordinata.
- Bolla e Insertion sort –
Complessità temporale media e peggiore: n^2
Complessità temporale migliore: n quando la matrice è già ordinata.
Caso peggiore: quando la matrice è ordinata al contrario. - Selection sort –
Complessità temporale del caso migliore, medio e peggiore: n^2 che è indipendente dalla distribuzione dei dati. - Merge sort –
Migliore, media e peggiore complessità di tempo: nlogn che è indipendente dalla distribuzione dei dati. - Heap sort –
Migliore, media e peggiore complessità di tempo: nlogn che è indipendente dalla distribuzione dei dati. - Quick sort –
È un approccio divide et impera con relazione di ricorrenza:T(n) = T(k) + T(n-k-1) + cn
Caso peggiore: quando la matrice è ordinata o ordinata al contrario, l’algoritmo di partizione divide la matrice in due subarray con 0 e n-1 elementi. Quindi,
T(n) = T(0) + T(n-1) + cnSolving this we get, T(n) = O(n^2)
Caso migliore e caso medio: In media, l’algoritmo di partizione divide l’array in due subarray di uguale dimensione. Pertanto,
T(n) = 2T(n/2) + cnSolving this we get, T(n) = O(nlogn)
Ordinamento non basato sul confronto –
Nell’ordinamento non basato sul confronto, gli elementi della matrice non vengono confrontati tra loro per trovare la matrice ordinata.
- Radix sort –
Complessità di tempo migliore, media e peggiore: nk dove k è il numero massimo di cifre negli elementi dell’array. - Count sort –
Complessità di tempo migliore, media e peggiore: n+k dove k è la dimensione del count array. - Ordinamento a secchielli –
Complessità temporale migliore e media: n+k dove k è il numero di secchielli.
Complessità temporale del caso peggiore: n^2 se tutti gli elementi appartengono allo stesso secchio.
Tecnica In-place/Outplace –
Una tecnica di ordinamento è inplace se non usa alcuna memoria extra per ordinare l’array.
Tra le tecniche basate sul confronto discusse, solo il merge sort è una tecnica outplaced in quanto richiede un array extra per unire i subarray ordinati.
Tra le tecniche non basate sul confronto discusse, tutte sono tecniche outplaced. Il counting sort usa un array di conteggio e il bucket sort usa una tabella hash per ordinare l’array.
Tecnica online/offline –
Una tecnica di ordinamento è considerata online se può accettare nuovi dati mentre la procedura è in corso, cioè non sono necessari dati completi per iniziare l’operazione di ordinamento.
Tra le tecniche basate sul confronto discusse, solo Insertion Sort si qualifica per questo a causa dell’algoritmo sottostante che usa, cioè elabora l’array (non solo gli elementi) da sinistra a destra e se vengono aggiunti nuovi elementi a destra, non ha impatto sull’operazione in corso.
Tecnica stabile/instabile –
Una tecnica di ordinamento è stabile se non cambia l’ordine degli elementi con lo stesso valore.
Tra le tecniche basate sul confronto, bubble sort, insertion sort e merge sort sono tecniche stabili. L’ordinamento a selezione è instabile perché può cambiare l’ordine degli elementi con lo stesso valore. Per esempio, consideriamo la matrice 4, 4, 1, 3.
Nella prima iterazione, l’elemento minimo trovato è 1 e viene scambiato con 4 in 0a posizione. Pertanto, l’ordine di 4 rispetto a 4 in 1a posizione cambierà. Allo stesso modo, quick sort e heap sort sono anche instabili.
Tra le tecniche non basate sul confronto, Counting sort e Bucket sort sono tecniche di ordinamento stabili, mentre la stabilità di radix sort dipende dall’algoritmo sottostante utilizzato per l’ordinamento.
Analisi delle tecniche di ordinamento:
- Quando la matrice è quasi ordinata, l’ordinamento a inserimento può essere preferito.
- Quando l’ordine di ingresso non è noto, l’ordinamento a fusione è preferito in quanto ha una complessità temporale nel caso peggiore di nlogn ed è anche stabile.
- Quando la matrice è ordinata, l’ordinamento a inserimento e a bolle dà una complessità di n ma l’ordinamento rapido dà una complessità di n^2.
Que – 1. Quale algoritmo di ordinamento richiede meno tempo quando tutti gli elementi della matrice di input sono identici? Considera le implementazioni tipiche degli algoritmi di ordinamento.
(A) Insertion Sort
(B) Heap Sort
(C) Merge Sort
(D) Selection Sort
Soluzione: Come discusso, l’insertion sort avrà la complessità di n quando l’array di input è già ordinato.
Que – 2. Consideriamo l’algoritmo Quicksort. Supponiamo che ci sia una procedura per trovare un elemento pivot che divide la lista in due sottoelenchi, ognuno dei quali contiene almeno un quinto degli elementi. Sia T(n) il numero di confronti necessari per ordinare n elementi. Allora, (GATE-CS-2012)
(A) T(n) <= 2T(n/5) + n
(B) T(n) <= T(n/5) + T(4n/5) + n
(C) T(n) <= 2T(4n/5) + n
(D) T(n) <= 2T(n/2) + n
Soluzione: La complessità dell’ordinamento rapido può essere scritta come:
T(n) = T(k) + T(n-k-1) + cn
Come indicato nella domanda, una lista contiene 1/5 degli elementi totali. Pertanto, un’altra lista avrà 4/5 degli elementi totali. Mettendo i valori, otteniamo:
T(n) = T(n/5) + T(4n/5) + cn, che corrisponde all’opzione (B).
Tabella di confronto della complessità temporale e spaziale :
| Algoritmo di ordinamento | Complessità temporale | Complessità spaziale | ||
|---|---|---|---|---|
| Best Case | Media Case | Worst Case | Worst Case | |
| Bubble Sort | Ω(N) | Θ(N2) | O(N2) | O(1) |
| Selezione | Ω(N2) | Θ(N2) | O(N2) | O(1) |
| Insertion Sort | Ω(N) | Θ(N2) | O(N2) | O(1) |
| Merge Sort | Ω(N log N) | Θ(N log N) | O(N log N) | O(N) |
| Heap Sort | Ω(N log N) | Θ(N log N) | O(N log N) | O(1) |
| Sistema rapido | Ω(N log N) | Θ(N log N) | O(N2) | O(N log N) |
| Radix Sort | Ω(N k) | Θ(N k) | O(N k) | O(N + k) |
| Count Sort | Ω(N + k) | Θ(N + k) | O(N + k) | O(k) |
| Bucket Sort | Ω(N + k) | Θ(N + k) | O(N2) | O(N) |
