Sortowanie bąbelkowe (wyjaśnienie)

Cześć,
zajmuję się właśnie sortowaniem bąbelkowym w ANSI C, ale kompletnie nie wiem o co chodzi w tym. Sam algorytm jest prosty, jednak ze stworzeniem kodu już trudniej. Nawet nie za bardzo potrafię go odczytać prawidłowo ;(

Znalazłem na wikipedii kod w ANSI C dotyczący sortowania bąbelkowego:

void boublesort(int table[], int size)
{
        int i, j, temp;
        for (i = 0; i<size; i++)
                for (j=0; j<size-1; j++)
                        {
                                if (table[j] > table[j+1])
                                {
                                        temp = table[j+1];
                                        table[j+1] = table[j];
                                        table[j] = temp;
                                }
                        }
}


 

Jestem na prawdę laikiem, jeśli ktoś mógłby "wykomentować" kod tak żeby w każdej linii było wiadomo co się dzieje. Żeby nie było że czekam na gotowca, sam trochę popracowałem, sądzę że mnie poprawicie jeśli moje rozumowanie będzie złe.

Deklarujemy funkcję void, która przyjmuje jako argumenty zmienną w postaci tablicy jednowymiarowej tab o nieokreślonej liczbie elementów i jakąś zmienną size, która w ogóle nic mi nie mówi.

A potem to już czarna magia... zaczynamy jeździć po tablicy forem na początku od pierwszego indeksu (i=0). Rozumiem że za zmienną j odpowiada wartość elementu o indeksie i ? Inaczej "i" to indeks tablicy a "j" wartość przechowywana w dowolnym indeksie.

Do czego służy ta funkcja temp, i jak zachodzi zamiana miejsc wartości ?

Reszta, po prostu kompletna magia.

Za wszelkie podpowiedzi z góry dziękuję!

Zmienna size (ang. rozmiar) to jest właśnie rozmiar Twojej tablicy, także nie jest nieokreślony tylko jest Ci przekazany. Iterujesz 2 razy ponieważ po przejściu jednej iteracji po wszystkich elementach będziesz miał tylko gwarancję, że na ostatnim miejscu masz największą liczbę w tablicy. Aby na przedostatnim była 2-ga największa to musisz jeszcze raz "przelecieć" po tablicy i porównywać element po elemencie. Wewnątrz ostatniego if-a tylko zamieniasz elementy miejscami jeżeli spełniony jest warunek.

Zasadę dobrze obrazuje animacja na wiki:
http://en.wikipedia.org/wiki/Bubble_sort
(Po prawej stronie jest ta animacja z takimi przesuwającymi się czerwonymi kwadratami)

http://pl.wikipedia.org/wiki/Sortowanie_bąbelkowe
Lecisz przez tablicę i zamieniasz ze sobą sąsiednie elementy które nie są w dobrej kolejności. Oznacza to ze jeden przebieg przez całą tablicę spowoduje w przypadku pesymistycznym przesunięcie jednej wartości na skrajną poprawną pozycję. Oznacza to że żeby posortować całą tablicę trzeba tą czynność powtórzyć n razy (tą też mamy dwie pętle zagnieżdżone).
Zmienna size (rozumiem że oprócz informatyki nie umiesz też angielskiego?) określa rozmiar tablicy. Trudno byłoby przelecieć przez całą tablicę nie wiedząc ile ma ona elementów...

Sortowanie bąbelkowe nie musi mieć całkowicie złożoności kwadratowej.. można to napisać n^2 minus kilka.

#include <stdio.h>
int main(){
    int i,n,j,p,*tab;
    scanf("%d",&n);
    tab=malloc(sizeof*tab*(n));
    for(i=0;i<n;i++)
        scanf("%d",&tab[i]);
    for(i=0;i<n-1;i++){
        for(j=i+1;j<n;j++){
            if(tab[j]>tab[i]){
                p=tab[j];
                tab[j]=tab[i];
                tab[i]=p;
            }
        }
    }
    for(i=0;i<n;i++)
        printf("%d ",tab[i]);
    free(tab);
    return 0;
}

sephirot8608> dzięki za odpowiedź. Trochę jaśniej.

Shalom> niestety nie, jedynymi językami obcymi jakie znam są języki wołżańskie.

Nie chodziło mi o size tylko o zmienną temp.
Pierwsza część kodu jest dość zrozumiała, niestety od momentu otworzenia ostatniej klamry to już czarna magia.
Nie rozumiem tego fragmentu.

{
temp = table[j+1];
table [j+1] = table [j];
table [j] = temp;

Założmy że poprzedni warunek jest spełniony tj. element o indeksie j, dajmy na to foo6foo jest większy od elementu po nim (o wyższym indeksie) powiedzmy niech to będzie foo5foo. Wtedy:

1. W pierwszej linijce przypisujemy zmiennej temp wartość mniejszą, tj. 5.

2. W drugiej linijce tą wartość przypisujemy wartości większej, czyli tak jakby 5 miało by się równa 6.

3. A na koniec skoro w drugim wyszła nam równośc to znaczy że tablej[j] czyli 6 też równa się temp.

Gdzie tu dochodzi do jakiejś zamiany ? Bo ja tego nie widzę ? Mógłby ktoś to po ludzku mi wytłumaczyć ?

Koperniku> nie komplikujmy sprawy... masz doczynienia z laikiem ;)

for(i=0;i<n-1;i++){
        for(j=i+1;j<n;j++){
            if(tab[j]>tab[i]){
                p=tab[j];
                tab[j]=tab[i];
                tab[i]=p;
            }
        }
    }

mamy taki kod oraz tablicę z elementami: 5,3,6,1,7
Na początku i=0;j=1
wiec sprawdzamy 3>5 ? Nie! więc powiększamy j.
i=0;j=2;
sprawdzamy 6>5? Tak.
W takim wypadku:
Do zmiennej pomocniczej podstawiamy 6.
w miejsce szóstki wstawiamy 5.
A na samym końcu w miejsce piątki wstawiamy sześć, które było w zmiennej pomocniczej..
I tak aż do zajebania..

Zauważ, że potrzebujesz dodatkowej zmiennej aby zamienić te dwie liczby miejscami. W przeciwnym wypadku stracisz jedną wartość.

temp = table[j+1];

1. W pierwszej linijce przypisujemy temp wartość mniejszą, tj. 5. Od tej pory temp jest równe 5.

table [j+1] = table [j];
2) W drugiej linijce na miejsce tej wartości wpisujemy wartość większą, czyli 6. Od teraz table[j+1] jest równe 6.

table [j] = temp;
3) A na koniec przypisujemy na miejsce table[j] to co mamy w temp, czyli 5.

3. A na koniec skoro w drugim wyszła nam równośc to znaczy że tablej[j] czyli 6 też równa się temp.

Nie wyszła nam tam żadna równość, bo nie było tam porównania. W C++, gdy porównujesz liczby piszesz: if (a == b)
a gdy przypisujesz, to piszesz a = b. W swoim rozumowaniu - pomieszałeś te dwa pojęcia.

@psikuta222 o_O?
Początkowo temp jest bez znaczenia. table[j+1] = 1, table[j] = 10
temp = table[j+1]; // więc temp = 1, zapamiętujemy tą wartość w temp
table [j+1] = table [j]; // pozbywamy się tej wartości i wpisujemy tam 10, stara wartość jest tylko w temp! zarówno w table[j+1] i table[j] jest 10
table [j] = temp; // do table[j] wpisujemy co to było w temp, czyli 1
Więc na koniec table[j+1] = 10, table[j] = 1
Widzisz chyba ze zaszła wymiana wartości...

That's what I'm talking about !

Wyjaśnione bardzo dokładnie i zrozumiale :) Dzięki wielkie chłopcy !

Faktycznie, mój błąd. Jako początkujący programista myli się czasami te operatory. Przypisanie, a nie porównanie ! :)

Podbijam temat, bo teraz chciałbym wytestować to na jakimś przykładzie. W sumie wystarczy tylko w tablicy zadeklarować jakieś elementy, ale niestety potem coś mi nie wychodzi z printf :(. Chyba nie zagnieździłem go dobrze... nie za bardzo wiem co mam wpisywać w printf i co tam umieścić.

Pomożecie ?

 

#include <windows.h>
#include <stdio.h>
#include <stdlib.h>


void boublesort (int table[]={83, 99, 203, 399, 994, 22, 442, 332, 445, 32, 32, 22}, int size)
{
	int i, j, temp;
	
	for(i=0; i<size; i++)
		for(j=0; j<size-1; j++)
			{
				if (tab[j]>tab[j+1])
				{
					temp=	table[j+1];
					table[j+1]=	table[j];
					table[j]=	temp;
				}
		
}

}
  getchar();
  return 0;
}

**Mam pomysł z pętlą for, co Wy na to ? Oprócz tego mam cholerny problem z kompilatorem, bo ciągle wywala mi następujące błędy:

[Error] expected ';', ',' or ')' before '=' token

w linii w której wypisuje wartości do tablicy. Czy można tak wpisywać wartości do tablicy, jeśli stanowi ona argument funkcji ?**

Spokojnie, to że wrzuciłem kilka minut po ostatnim poście nie znaczy że ten czas określa okres mojej "wytężonej" pracy. Uwierz mi że sporo już czasu poświeciłem nad tym jednym małym problemem, inaczej nie prosiłbym o podpowiedzi tylko o gotowca. Próbuję temat zgłębić i zrozumieć ;)

void bSort(int* tab,int size){
    int i=0,j=0,p;
    for(i=0;i<size-1;i++){
        for(j=i+1;j<size;j++){
            if(tab[j]>tab[i]){
                p=tab[j];
                tab[j]=tab[i];
                tab[i]=p;
            }
        }
    }
}
int main(){
    int tab[]={83, 99, 203, 399, 994, 22, 442, 332, 445, 32, 32, 22};
    int size=sizeof(tab)/sizeof(int),i=0;
    bSort(tab,size);
    for(i;i<size;i++)
        printf("%d ",tab[i]);
    return 0;
}

Argumenty domyśle są w C++, a nie w C. To był twój problem.

Dużo rzeczy do nauczenia, ale chyba wiem gdzie szukać pomocy. Dziękuję jeszcze raz za pomoc !