Bubblesort2

Iz MaFiRaWiki

Gre za izboljšan algoritem urejanja z mehurčki, kjer novo primerjanje dveh sosednjih elementov izvajamo samo do mesta zadnje zamenjave. Algoritem izboljšamo tako, da si zapomnimo mesto zadnje zamenjave. Naslednji prehod ustavimo na tem mestu, namesto da bi nadaljevali do fiksno določeno spodnje meje.

Dodana spremenljivka m tipa int vsebuje indeks tistega elementa v tabeli, pri katerem je prišlo do zadnje zamenjave:

  • na zacetku vsakega prehoda začnemo na koncu: m = tab.length-1
  • ob vsaki zamenjavi postane indeks m enak i, tako si zapomnemo mesto menjave
  • na koncu vsakega prehoda se urejeni del postavi na mesto zadnje menjave, povečane za ena: j = m + 1

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