Implementazioni di algoritmi/Radix sort: differenze tra le versioni

Naviga nella cronologia in modo interattivo

← Differenza precedente Differenza successiva →

Contenuto cancellato Contenuto aggiunto

VisualeWikitesto

In linea

Versione delle 20:22, 4 mar 2008

Algoritmi

Copertina

Tutti i moduli · Sviluppo

Copertina Algoritmi/Copertina

Modifica il sommario

Il Radix Sort è un algoritmo di ordinamento per valori numerici interi con complessità computazionale O( $n*logk$ ), dove $n$ è la lunghezza dell'array e $k$ è la media del numero di cifre degli $n$ numeri.

Radixsort utilizza un procedimento controintuitivo per l'uomo, ma più facilmente implementabile. Esegue gli ordinamenti per posizione della cifra ma partendo dalla cifra meno significativa. Questo affinché l'algoritmo non si trovi a dovere operare ricorsivamente su sottoproblemi di dimensione non valutabili a priori.

Implementazione in Java

 public class radixSort {
        public static void radixSort(int[] arr){ 
        if(arr.length == 0)
            return;
        int[][] np = new int[arr.length][2]; //matrice
        int[] q = new int[256];
        int i,j,k,l,f = 0;
        for(k=0;k<4;k++){
            for(i=0;i<(np.length-1);i++)
                np[i][1] = i+1;
            np[i][1] = -1;
            for(i=0;i<q.length;i++)
                q[i] = -1;
            for(f=i=0;i<arr.length;i++){
                j = ((255<<(k<<3))&arr[i])>>(k<<3);
                if(q[j] == -1)
                    l = q[j] = f;
                else{
                    l = q[j];
                    while(np[l][1] != -1)
                        l = np[l][1];
                    np[l][1] = f;
                    l = np[l][1];
                }
                f = np[f][1];
                np[l][0] = arr[i];
                np[l][1] = -1;
            }
            for(l=q[i=j=0];i<256;i++)
                for(l=q[i];l!=-1;l=np[l][1])
                        arr[j++] = np[l][0];
   }
  }
 }}

Altri progetti

Wikipedia contiene una voce su questo algoritmo

@@ Riga 1: / Riga 1: @@
+{{algoritmi}}
-Il '''Radix Sort''' è un [[algoritmo]] di ordinamento per valori numerici interi con [[complessità computazionale]] [[o-grande|O]](<math>n * logk</math>), dove <math>n</math> è la lunghezza dell'array e <math>k</math> è la media del numero di cifre degli <math>n</math> numeri.
-[[Immagine:Radix.JPG||thumb|right|450px|]]
+Il '''Radix Sort''' è un [[w:algoritmo|algoritmo]] di ordinamento per valori numerici interi con [[w:complessità computazionale|complessità computazionale]] [[w:o-grande|O]](<math>n * logk</math>), dove <math>n</math> è la lunghezza dell'array e <math>k</math> è la media del numero di cifre degli <math>n</math> numeri.
 Radixsort utilizza un procedimento controintuitivo per l'uomo, ma più facilmente implementabile. Esegue gli ordinamenti per posizione della cifra ma partendo dalla cifra meno significativa. Questo affinché l'algoritmo non si trovi a dovere operare ricorsivamente su sottoproblemi di dimensione non valutabili a priori.
-==Considerazioni sull'algoritmo==
-L'algoritmo Radix sort ha complessità computazionale variabile in base al valore k. Se k risulta essere minore di n, non si ha guadagno rispetto a [[Integer sort]] che opera in tempo lineare.
-Se k è invece maggiore di n, l'algoritmo può risultare peggiore anche dei più classici algoritmi di ordinamento per confronto a tempo quasi lineare, come [[Quicksort]] o [[Mergesort]].
-Usando come base dell'algoritmo un valore B = Θ(n) il tempo di ordinamento diviene <math>\mathcal{O}(n (1 + {log (k) \over log (n)  } ))</math>
-La precedente definizione è dimostrabile ricordando che ci sono <math>log_n (k) = \mathcal{O}(log_n (k))</math> passate di [[Integer sort]] e ciascuna richiede tempo <math>\mathcal{O}(n)</math>.
-Usando le regole per il cambiamento di base dei [[logaritmo|logaritmi]], il tempo totale è dato da <math>\mathcal{O}(n log_n (k)) = \mathcal{O}(n {log (k) \over log (n)})</math>.
-A questa quantità va aggiunto <math>\mathcal{O}(n)</math> per contemplare il caso in cui k < n, dato che la sequenza, va almeno letta.
 ==Implementazione in Java==
-{{Trasferimento|wb|Implementazioni}}
 <source lang="java">
@@ Riga 58: / Riga 44: @@
 </source>
+== Altri progetti ==
+{{interprogetto|w=Radix sort|w_etichetta=questo algoritmo}}
-[[Categoria:Algoritmi di ordinamento]]
+[[Categoria:Algoritmi| ]]
+{{Avanzamento|100%|4 marzo 2008}}
-[[cs:Radix sort]]
-[[de:Radixsort]]
-[[en:Radix sort]]
-[[es:Ordenamiento Radix]]
-[[fi:Kantalukulajittelu]]
-[[fr:Tri par base]]
-[[he:מיון בסיס]]
-[[ja:基数ソート]]
-[[ko:기수 정렬]]
-[[lt:Skaitmeninis rikiavimo algoritmas]]
-[[nl:Radix sort]]
-[[no:Radikssortering]]
-[[pl:Sortowanie pozycyjne]]
-[[pt:Radix sort]]
-[[ru:Поразрядная сортировка]]
-[[uk:Сортування за розрядами]]
-[[vi:Sắp xếp theo cơ số]]
-[[zh:基数排序]]