Bubblesort1

Iz MaFiRaWiki

Gre za izboljšan algoritem urejanja z mehurčki, kjer se postopek urejanja konča takoj, ko v nekem prehodu algoritem ne opravi nobene zamenjave.

Metodi dodamo novo spremenljivko k tipa boolean, ki pove ali je v nekem prehodu prišlo do zamenjave. Spremenljivko

  • na začetku vsakega prehoda jo postavimo na false
  • ob vsaki zamenjavi dobi vrednost true

Zunanjo zanko realiziramo s stavkom while in ne vemo kolikokrat se bo izvršila, v najslabšem primeru za eno manj, kot je podatkov v tabeli.

  1. public static void BubbleSort1(int[] tab){
  2. int i,j;
  3. int x;
  4. boolean k = true;
  5. j = 0;
  6. while (j < tab.length && k = true){ // ponavljamo, dokler ni urejena vsa tabela, oziroma dokler metoda opravi zamenjavo
  7. k = false;
  8. for(i=tab.length-1; i>j; i--) // pomikamo se od zadnjega elementa proti prvemu-do tistega dela tabele, ki je že urejen
  9. if (tab[i] < tab[i-1]){ // če je element manjši od predhodnika, ju zamenjamo
  10. x = tab[i];
  11. a[i] = a[i-1];
  12. a[i-1] = x;
  13. k = true;
  14. }
  15. j = j+1; // urejeni del tabele se poveča za ena
  16. }
  17. }
Osebna orodja