Algorytm Bubble sort

Hej, jestem początkujący, zwracam do was z prośbą o wytłumaczenie tego pseudokodu jest on krótki:

Algorytm Bubble sort:

 
sort(T[1...n])
for i<--2 to n
    do for j<--n downto i
           do if T[j] < T[j-1]
                 then zamien(T[j], T[j-1]) 

Napisałem, jak rozumiem ten pseudokod. Jeśli piszę głupoty, to proszę mnie wyprowadzić z błędu.

2 linijka:

• ta instrukcja wykona się od 2 do n razy
  np. mamy tabelę [3,5,12,6,7] to wykona się 4 razy

• dlaczego zmienna i zaczyna się od drugiego elementu tablicy, a nie od pierwszego?

• w C++ ta linijka będzie wyglądała tak: for(i=2; i<n; i++)?

3 linijka:

• odlicza od n do i z góry w dół - to niestety nie rozumiem, jak to wygląda?
• W C++ ta linijka będzie wyglądała tak: for(j=n; j>=i; i--)?
  **4 i 5 linijki **- rozumiem

Na końcu mam pytania:

Niech będzie dana tabela: [3,5,12,6,7], zilustrujmy to działanie na podstawie powyższego algorytmu

• czy nad 5 jest zmienna i, a nad 7 zmienna j? Pozwolę dodać obraz, gdybyście mnie nie zrozumieli, o co mi chodzi:
  
• co robi zmienna i?
• czy sprawdzenie, czy T[j] < T[j-1] zaczynamy od końca?
  Napisałem przejrzyście, mam nadzieję, że uzyskam odpowiedzi na pytania. Oczywiście przeczytałem na temat pętli for w internecie, ale nadal mam wątpliwości. Przepraszam za tego linka, nie wiem, czemu nie wyświetla, a w poglądzie go widać. Zastosowałem "Wstaw obraz".

Algorytmy rzadko rozkminia się po linijce, bo te linijki są ze soba powiązane!
Algorytm leci od 2 elementu tablicy bo zauważ ze później porównujemy element i-ty oraz i-1 czyli mimo wszystko bierzemy pod uwagę także element pierwszy. Równie dobrze moglibyśmy lecieć pętlą od 1 elementu do n-1 a porównywać i-ty oraz i+1
Algorytm działa tak:

• pętla po 'i' wskazuje na które miejsce w tablicy wskoczy nam liczba która powinna tam być
• pętla po 'j' przeszukuje tablicę od pozycji 'i' do końca (bo wszystko aż do pozycji 'i' powinno już być na swoim miejscu!) i zmienia elementy miejscami tak żeby na miejsce i-te wskoczyła poprawna liczba

Tak,pętle są dobrze napisane, możesz jeszcze ująć to tak for ( int i=0;i<coś_tam;i++) ale wtedy należy pamięć że zmienna 'i' dostępna jest tylko wewnątrz pętli for,po wyjściu z for 'i' nie istnieje.
Tak, T[j] oznacza że sprawdzamy od końca
Działanie Ci kolega wytłumaczył,ja mogę jeszcze podać link : http://edu.i-lo.tarnow.pl/inf/alg/003_sort/0006.php oraz to angielskiej wikipedi http://en.wikipedia.org/wiki/Bubble_sort . Widać tu jak ogólnie działa sortowanie bąbelkowe ( swoją drogą jedne z najwolniejszych,unikaj jeżeli nie musisz używać ;p ).

Jak coś to pytaj
Pozdrawiam
soyer92

Ogromnie wam bardzo dziękuję. Naprawdę to forum jest niesamowite.

Po kilka razy przeczytałem te wasze odpowiedzi, mogę powiedzieć, że trochę rozumiem. Myślę, że jeśli zrobię to na przykładzie, to już lepiej go zrozumiem.

• rozumiem, że w tym algorytmie zamiast tej drugiej linijki można napisać for i <-- 1 to n-1, ale wówczas algorytm bym wyglądał tak:

 
sort(T[1...n])
for i<--1 to n-1
    do for j<--n-1 downto i
           do if T[j] > T[j+1]
                 then zamien(T[j], T[j+1]) 

Przykład:

Na podstawie powyższego algorytmu (tego na początku w pierwszym poście). Robi się go dłużej, więc dokonamy tylko pierwszy obieg.

• [11,8,4,20,14,7], i=2, j=6

• [11,8,4,20,7,14], i=2, j=5

• [11,8,4,7,20,14], i=2, j=4

• [11,8,4,7,20,14], i=2, j=3

• [11,4,8,7,20,14], i=2, j=2

• [4,11,8,7,20,14], i=2, j=1
  Koniec pierwszego obiegu.

• Mam wątpliwości co do zmiennej i, gdzie napisałem w przykładzie, że jest cały czas przy i=2.

• Z opisu Shaloma rozumiem, że 4 jest tą liczbą, która powinna tam być. W następnym obiegu nie jest ona sprawdzana. Czyli powinno być i=1, ale przecież algorytm rozpoczyna od drugiego elementu.

1. Rozumiem ze zakładamy numerację od 1?
2. Po pierwsze to j nigdy nie osiąga wartości mniejszej od 'i'
3. Kiedy j=2 to porónujemy ze sobą tablica[j] i tablica[j-1] czyli SPRAWDZAMY liczbę o indeksie 1. Nie rozumiem gdzie widzisz problem.

Shalom napisał(a):

1. Rozumiem ze zakładamy numerację od 1?
2. Po pierwsze to j nigdy nie osiąga wartości mniejszej od 'i'
3. Kiedy j=2 to porónujemy ze sobą tablica[j] i tablica[j-1] czyli SPRAWDZAMY liczbę o indeksie 1. Nie rozumiem gdzie widzisz problem.

Czyli w przykładzie jest źle zrobione. Powinno być:

• [11,8,4,20,14,7], i=1, j=6
• [11,8,4,20,7,14], i=1, j=5
• [11,8,4,7,20,14], i=1, j=4
• [11,8,4,7,20,14], i=1, j=3
• [11,4,8,7,20,14], i=1, j=2
• [4,11,8,7,20,14],
  Koniec pierwszego obiegu.

Czy teraz przykład jest dobrze zrobiony wraz ze zmiennymi 'i' i 'j'?

• W następnym obiegu, "i" przechodzi dalej, czyli będzie zaczynało od drugiego elementu?

Nie, nie jest. Po pierwsze dlatego że nie wiem czy to jest u ciebie stan tablicy po wykonaniu kroku z parametrami i,j czy przed jego wykonaniem. Poza tym skoro numerujemy od 1 (czyli pierwszy element tablicy ma indeks 1) to pierwsze i powinno = 2. Tak samo przecież ostatnie j powinno się równać i. Mam niestety wrażenie że ty zupełnie nie rozumiesz co się tutaj dzieje...

Myślę, że może nie umiem to wytłumaczyć, o co mi chodzi, albo źle rozumiem.

Ja rozumiem tak:

Mamy tabelę: [11,8,4,20,14,7]

• T[j] sprawdzamy od końca, więc j będzie się równać 6 czyli szósty element tablicy.
• i - tak jak napisałeś, powinno się równać 2
  Czyli będzie:
• [11,8,4,20,14,7], i=2, j=6**

*  T[j] = 7, T[j-1] = 14
*  sprawdzamy T[j] < T[j-1], czyli 7<14, zgadza się, więc zamieniamy ze sobą elementy:

• [11,8,4,20,7,14], i=2, j=5**

*  teraz j będzie się równać 5, czyli piąty element tablicy
*  T[j]=7, T[j-1]=20, 7<20, zamieniamy ze sobą elementy:

• [11,8,4,7,20,14], i=2, j=4
• [11,8,4,7,20,14], i=2, j=3
• ** [11,4,8,7,20,14], i=2, j=2**
• **[4,11,8,7,20,14], ** - koniec pierwszego obiegu, po wykonaniu kroku z parametrami i, j,
  Ale to nie jest koniec, przechodzimy do drugiego obiegu, gdzie "j" będzie się równać 6, a "i" - 3.

Jeśli za bardzo źle rozumiem, to bardzo proszę pokazać to na przykładzie albo poprawić. Może dzięki temu zrozumiem.

No ale to jest wszystko ok co piszesz i tak to właśnie działa. Zauważ dodatkowo że po pierwszym obiegu który opisałeś pierwsza liczba w tablicy jest na dobrym miejscu. Po drugim druga i tak aż do końca.

Bardzo dziękuję za odpowiedź. Cieszę się, że już to rozumiem.

Jeszcze mam tylko 2 pytania:

• czy w drugim obiegu, parametr "i" równa się 3 - pytam się, żeby mieć pewność
• czy algorytm z linijką for i <-- 1 to n-1 jest dobrze napisany? Wiem, że działa ono inaczej.

• Tak, w drugim obiegu lecisz z kolejnym i, czyli 3, potem 4 i tak do końca
• Tak, ta wersja z i od 1 do n-1 jest ok. Działa dokładnie tak samo :P