Urejanje Shell sort/Implementacija (Java)

Iz MaFiRaWiki

  1. /* Shell sort - algoritem na osnovi navadnega vstavljanja, ki uredi dane elemente tabele tako, da v večih fazah pregleda
  2. tabelo,uredi podatke v skupinah, pri čemer v isto skupino spadajo elementi,ki so določeno število mest narazen.*/
  3. Public static void shellSort(int[] tab)
  4. {
  5. int k=1; // izračun koraka za prvo fazo
  6. while (3*k+1 < tab.length) // določimo največji korak, ki ga lahko izvedemo znotraj tabele (1, 4, 13, 40, 121, ...)
  7. k=3*k+1;
  8. while (k>0) // zanka za faze
  9. {
  10. for(int i = k; i < tab.length; i++)
  11. {
  12. int x = tab[i]; // izberemo zadnji element skupine
  13. int j = i-k;
  14. while (j>=0 && x<(tab[j])) // če je element x v skupini manjši od tistega pred njim
  15. {
  16. tab[j+k] = tab[j]; // ju zamenjamo
  17. j = j-k;
  18. }
  19. tab[j+k] = x; // nov trenutni element
  20. }
  21. k = k/3; // vsi elementi v skupini so urejeni, zmanjšamo korak
  22. }
  23. }
Osebna orodja