Urejanje s štetjem/Implementacija (Java)

Iz MaFiRaWiki

  1.  
  2. public class UrejanjeSstetjem{
  3. public static int[] countSort(int[] zacetna){
  4. int max = 0; //začetna vrednost maximalnega elementa je 0
  5. for (int i = 0; i < zacetna.length; i++){ //v zanki poiščemo maximalen element
  6. if(zacetna[i] > max) max = zacetna[i];
  7. }
  8. int [] dodatna = new int[max + 1]; //dodatna tabela je velikosti največjega elementa začetne tabele + 1
  9. for(int i = 0; i < zacetna.length; i++){
  10. dodatna[zacetna[i]]++;
  11. //element v dodatni tabeli na i-tem mestu nam pove, koliko je elementov elementa i v začetni tabeli
  12. }
  13. for (int i = 1;i < dodatna.length ;i++){//sledi preureditev dodatne tabele
  14. dodatna[i] += dodatna[i-1];//vrednosti dodatne tabele na i-tem mestu prištejemo predhodno vrednost
  15. //element v dodatni tabeli na i-tem mestu nam sedaj pove, koliko je elementov v začetni tabeli, ki so manjši ali enaki i
  16. }
  17. //POZOR!Ker indeksi tabele v Javi tečejo od 0 naprej, pride do rahle "zmede" pri indeksiranju končne tabele!
  18. //Ker mi vstavljamo element j začetne tabele v končno tabelo na mesto s takšnim indeksom,
  19. //kolikršna je vrednost dodatne tabele (na mestu z indeksom števila j), vemo pa, da vrednost dodatne tabele
  20. //na kateremkoli mestu z indeksom j (pri čemer je j katerikoli element začetne tabele) ne bo nikoli enak 0
  21. //(ker če bi bil enak 0, bi to pomenilo, da element j ne nastopa v začetni tabeli, kar pa je v protislovju z
  22. //našo predpostavko). Zato torej ničtega elementa končne tabele ne moremo nikoli zapolniti z vrednostmi začetne
  23. //tabele, zato mu lahko priredimo poljubno vrednost, npr. 0 in ga ob izpisu rezultata ne upoštevamo.
  24. //Vendar moramo zato povečati velikost končne tabele za 1, saj drugače ne bi mogli vstaviti elementa na zadnje mesto.
  25.  
  26. int[] koncna = new int[zacetna.length+1];//končno tabelo moramo zaradi "zmede" povečati za 1
  27. for(int i = zacetna.length-1; i >= 0; i--){//od zadnjega elementa se sprehodimo do prvega
  28. koncna[dodatna[zacetna[i]]] = zacetna[i];//Glejte komentar zgoraj pri POZOR!
  29. dodatna[zacetna[i]]--;//ker smo 1 število na vsakem koraku zanke upoštevali,odštejemo 1 na ustreznem mestu
  30. }
  31. return koncna; //metoda vrača končno urejeno tabelo
  32. }
  33. public static void main(String[] args){ //V metodi main preizkusimo delovanje programa in s tem algoritma
  34. int[] zacetna = {7, 3, 7, 9, 3, 7, 1, 9}; //Zmislimo si poljubno tabelo števil
  35. int[] koncna = countSort(zacetna); //pokličemo zgoraj napisano metodo CountSort, ki pa bo vrnila tabelo
  36. for(int i = 0; i< koncna.length; i++){//zato moramo s for zanko to tabelo tudi izpisati
  37. System.out.print(koncna[i] + " ");
  38. }
  39. }
  40. }

Ko poženemo program, na primer z Drjava, dobimo urejene elemente po velikosti od najmanjšega do največjega:

 
>java UrejanjeSstetjem
 0 1 3 3 7 7 7 9 9 >
Osebna orodja