Sortowanie bąbelkowe

Question

Znalazłem taki kod do sortowania bąbelkowego:

public static void bubblesort2(int[] tablica) {
for(int i = 1; i < tablica.length; i++) {
for(int j = 0; j < tablica.length - i; j++) {
if(tablica[j] > tablica[j + 1]) {
swap(tablica, j, j + 1);
}
}
}
}

Wewnętrzna pętla zmniejsza się o 1, ponieważ

* za każdym jej przebiegiem największy element jest na swojej pozycji.

* Nie trzeba z nim zatem porównywać innych liczb.

* @param tablica tablica liczb do posortowania

 

Rzeczywiście działa ale jak sobie to analizuje to mi nie wychodzi na kartce papieru...

Jeżeli mam tablicę 6 elementową i użyję takiej pętli

for(int j = 0; j < tablica.length - i; j++)

To w sytuacji kiedy i będzie równe 3, a tablica ma 6 elementów to "tablica.length - i"  da mi 3 przy jednocześnie tej samej wartości dla zmiennej j - więc wykona się tylko 3 razy, zabraknie 3 kolejnych cykli.

Gdzie robię błąd?

 

Kod zaczerpnięty ze strony algorytm

Answer 1

Bo to co masz jest pewna optymalizacja klasycznego sortowania babelkowego. Algorytm ten dziala tak ze z kazda glowna iteracja najwiekszy element przenoszony jest na koniec. Skoro tak to mozna zoptymalizowac to do takiej postaci jak przedstawiasz, a zatem z kazda glowna iteracja mozna pomijac kolejne elementy z konca ciagu, poniewaz one na bank sa posortowane:

Jakis ciag nieposortowany 4, 9, 5, 3, 8,  2, 7

po pierwszej glownej iteracji bedize tak: 4, 5, 3, 8, 2, 7, 9   9 - jest najwiekszym elementem 

po 2 iteracji: 4, 3, 5, 2, 7, 8, 9  - pogrubione elementy sa juz posortowane i nie trzeba ich sprawdzac tak jak jest to w normalnym sortowaniu babelkowym.

I z kazda kolejna iteracja ten ciag pogrubionych wartosci bedzie wiekszy.

 

Klasyczny algorytm babelkowy masz pod tym linkiem co podales w pierwszej metodzie bubblesort1.

Comments

To w jaki sposób podana przez Ciebie tablica posortuje się do końca? Tablica siedmioelementowa dan w konsekwencji 4, 3, 2, 5, 7, 8, 9. W czwartej iteracji się już nie wykona, bo "j" będzie wynosić 4 a "tablica.length - i" da nam 7 - 4 = 3. Czyli nie będzie spełniony warunek

for(int j = 0; j < tablica.length - i; j++)

 

bo 4 < 3. Gdzie robię błąd?

---

Iteracja nr: 1
4 9 5 3 8 2 7 
4 5 9 3 8 2 7 
4 5 3 9 8 2 7 
4 5 3 8 9 2 7 
4 5 3 8 2 9 7 
4 5 3 8 2 7 9 

Iteracja nr: 2
4 5 3 8 2 7 9 
4 3 5 8 2 7 9 
4 3 5 8 2 7 9 
4 3 5 2 8 7 9 
4 3 5 2 7 8 9 

Iteracja nr: 3
3 4 5 2 7 8 9 
3 4 5 2 7 8 9 
3 4 2 5 7 8 9 
3 4 2 5 7 8 9 

Iteracja nr: 4
3 4 2 5 7 8 9 
3 2 4 5 7 8 9 
3 2 4 5 7 8 9 

Iteracja nr: 5
2 3 4 5 7 8 9 
2 3 4 5 7 8 9 

Iteracja nr: 6
2 3 4 5 7 8 9 

 Posortowane:
2 3 4 5 7 8 9 

Tak bedzie to wygladalo.

---

Dzięki, źle patrzyłem na kod.

---

Chodzi po prostu o to ze z kazda iteracja jest o 1 mniej liczb do posortowania.

---

mbabane ma rację, możesz to jeszcze zobaczyć na animacji tutaj