Aspecte teoretice:
Sortarea după ranguri (sau sortarea digitală ) este o metodă care utilizează reprezentarea binară a cheilor. Este mai eficientă decât orice altă metodă de sortare internă realizată pe asemenea calculatoare cu condiția ca N (numãrul elementelor) să nu fie prea mic si cheile să nu fie prea mici. Algoritmul Radixsort tratează cheile ca numere reprezentate într-o bază M, pentru diferite valori ai lui M (radixul) și lucrează cu cifrele individuale ale numerelor.(De ex: caracterele pot fi reprezentate în bază 128) Astfel 10 grămezi corespunzând celor 10 cifre zecimale când M=10. Fiecare coloană este sortată începând cu rangul cel mai puțin semnificativ (prima din dreapta) al cheilor, mutând înregistrările din aria de intrare într-o arie auxiliară. Apoi se sortează după următorul rang semnificativ, până când pasul final stabilește toate înregistrările în ordinea dorită. Această metodă de sortare mecanică care se folosea la sortarea cartelelor perforate se poate implementa pe calculator.
Fiecare pachet poate fi reprezentat ca o coadă înlănțuită FIFO. La sfârșitul fiecărui pas aceste cozi pot fi combinate ușor în ordine potrivită. Dacă numărul maxim de biți într-o cheie este M, atunci sunt necesare M pași de la bitul cel mai puțin semnificativ la bitul cel mai semnificativ pentru a sorta cheile. Tabela inițială este aranjată ca o simplă listă înlănțuită. Prima dată sortăm elementele după biții mai puțin semnificativi, îmbinăm grămezile apoi sortăm după biții mai semnificativi iarăși îmbinăm grămezile (pockets) etc.
Analiza complexității:
Trebuie să folosim structuri de date potrivite ca să fie eficient Radix sortul. Este preferabil ca elementele de sortat să fie într-o listă înlănțuită în loc de o tabelă simplă. Dacă folosim listă înlănțuită nu trebuie să copiem înregistrarea ci doar să mutăm înregistrarea dintr-o listă în alta. Ca combinarea să fie rapidă avem nevoie de pointeri la sfârșitul fiecărei liste.
Timpul de execuție al Radix sortului este liniar ( de O(N) ) dacă cheile de sortat sunt de tip întregi sau șir de caractere cu lungime fixă. Dacă avem N elemente cu M biți atunci algoritmul este de O(M+N). Dacă cheile sunt privite ca șiruri binare de lungime logN atunci Radixsort va fi de O(logN). Algoritmul nu necesită foarte multă memorie.
Exemplu Pas cu Pas:
Implementare:
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace RadixSortCS { class Program { static void RadixSort(int [] a, int n) { int i,m=0,exp=1; int [] b = new int[100]; for(i=0;i<n;i++) { if(a[i]>m) m=a[i]; } while(m/exp>0) { int [] bucket = new int[10] {0,0,0,0,0,0,0,0,0,0}; for(i=0;i<n;i++) bucket[a[i]/exp%10]++; for(i=1;i<10;i++) bucket[i]+=bucket[i-1]; for(i=n-1;i>=0;i--) b[--bucket[a[i]/exp%10]]=a[i]; for(i=0;i<n;i++) a[i]=b[i]; exp*=10; } } static void Main(string[] args) { int [] v = new int[100]; int i; int len; Console.Write("Dati numarul de elemente din vector: "); len = Convert.ToInt32(Console.ReadLine()); for (i = 0; i < len; i++) { Console.Write("v[" + i + "]="); v[i] = Convert.ToInt32(Console.ReadLine()); } RadixSort(v, len); for (i = 0; i < len; i++) Console.Write(v[i] + " "); Console.ReadLine(); } } }
// RadixSortCPP.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; int v[20]; void RadixSort(int *a,int n) { int i,b[100],m=0,exp=1; for(i=0;i<n;i++) { if(a[i]>m) m=a[i]; } while(m/exp>0) { int bucket[10]={0}; for(i=0;i<n;i++) bucket[a[i]/exp%10]++; for(i=1;i<10;i++) bucket[i]+=bucket[i-1]; for(i=n-1;i>=0;i--) b[--bucket[a[i]/exp%10]]=a[i]; for(i=0;i<n;i++) a[i]=b[i]; exp*=10; } } int main(void) { int i; int len; cout<<"Dati numarul de elemente din vector: "; cin>>len; for (i=0; i<len; i++) { cout<<"v["<<i<<"]="; cin>>v[i]; } RadixSort(v, len); for (i=0; i<len; i++) cout<<v[i]<<" "; system("pause"); }
Module Module1 Private Sub RadixSort(a As Integer(), n As Integer) Dim i As Integer, m As Integer = 0, exp As Integer = 1 Dim b As Integer() = New Integer(99) {} For i = 0 To n - 1 If a(i) > m Then m = a(i) End If Next While m \ exp > 0 Dim bucket As Integer() = New Integer(9) {0, 0, 0, 0, 0, 0, _ 0, 0, 0, 0} For i = 0 To n - 1 bucket(a(i) / exp Mod 10) += 1 Next For i = 1 To 9 bucket(i) += bucket(i - 1) Next For i = n - 1 To 0 Step -1 b(System.Threading.Interlocked.Decrement(bucket(a(i) / exp Mod 10))) = a(i) Next For i = 0 To n - 1 a(i) = b(i) Next exp *= 10 End While End Sub Sub Main(args As String()) Dim v As Integer() = New Integer(99) {} Dim i As Integer Dim len As Integer Console.Write("Dati numarul de elemente din vector: ") len = Convert.ToInt32(Console.ReadLine()) For i = 0 To len - 1 Console.Write("v[" & i & "]=") v(i) = Convert.ToInt32(Console.ReadLine()) Next RadixSort(v, len) For i = 0 To len - 1 Console.Write(v(i) & " ") Next Console.ReadLine() End Sub End Module
{ public static void RadixSort(int a[], int n) { int i,m=0,exp=1; int [] b = new int[100]; for(i=0;i<n;i++) { if(a[i]>m) m=a[i]; } while(m/exp>0) { int [] bucket = {0,0,0,0,0,0,0,0,0,0}; for(i=0;i<n;i++) bucket[a[i]/exp%10]++; for(i=1;i<10;i++) bucket[i]+=bucket[i-1]; for(i=n-1;i>=0;i–) b[–bucket[a[i]/exp%10]]=a[i]; for(i=0;i<n;i++) a[i]=b[i]; exp*=10; } } public static void main(String args[]) { int a[]={7,4,5,3,1,8,9,2,6,0}; int i; RadixSort(a,10); |
Rezultat:
InfoCad Blog 