Bubblesort metoda

[ Danijel Bulic @ 12.02.2010. 23:13 ] @

Ako nije problem da mi netko malo objasni ovu metodu, kapisam sta trebati raditi ali ne kapiram zasto. Evo konkretno prijmer koji u mene ne radi.

Evo sad radi ali i dalje mi nije jasno zasto ovako idu petlje.

Code:
#include <stdio.h>
#include <stdlib.h>

int main ()
{
    int n[10], i, j, t;
    for (i=0; i<10; i++)
        scanf ("%d", &n[i]);
    for (i=9; i>=0; i--)
        for (j=0; j<=i; j++)
            if (n[j+1] < n[j])
                       {
                t = n[j];
                n[j] = n[j+1];
                n[j+1] = t;
            }
        for (i=0; i<10; i++)
            printf ("%d\n", n[i]);

    system("PAUSE");
    return 0;
}

[ Picsel @ 13.02.2010. 10:45 ] @

Svakim prolazom se najveci (ili najmanji broj, zavisi kako se sortira) "gura" na kraj. Naravno, posle prvog prolaza najveci je na kraju, tako da se u sledecem prolazu on ne mora ni posmatrati, vec samo prvih n-1 clanova (gde je n broj clanova). Na sledecem prolazu n-2 clanova itd.
Ukupan broj prolaza ce biti n.
Spoljasnja petlja oznacava taj broj prolaza, odnosno ima ih 10 jer ima 10 clanova. Petlja ide od 9 do 0. Moglo se napisati i da ide od 0 do 9 i malo izmeniti unutrasnja petlja, ali ipak ide od 9 do 0 zbog optimizacije. Evo u cemu je stvar. Pored toga sto spoljasnja petlja broji prolaze kroz niz, ona takodje oznacava i do kojeg clana unutrasnja petlja treba da ide, odnosno koji deo niza jos nije sortiran. Znaci, u prvom prolazu u ovom primeru i je 9. To znaci da niz nije sortiran od 0. do 9. clana, pa se unutrasnjom petljom "gura" najveci clan na 9. poziciju. U sledecem prolazu i je 8, sto znaci da se sad sortira samo deo do 8. pozicije, jer se na 9. mestu vec nalazi najveci clan i nije potrebno porediti ga, jer je on vec na svom mestu.
Unutrasnja petlja bi trebalo da je jasna, ide od pocetka do kraja nesortiranog dela niza (znaci na pocetku ide do 9. pozicije, pa posle toga do 8. pozicije itd.) i zamenjuje trenutni clan sa sledecim ukoliko je trenutni veci, odnosno svaki put "uzima" veci clan i pomera ga prema kraju niza, tako da se na kraju prolaza najveci nalazi na kraju.

[ X Files @ 13.02.2010. 13:08 ] @

Poenta je:

1) uporediti svaki sa svakim clanom niza (bez ponavljanja i bez uporedjivanja sa samim sobom)
2) ustanoviti neki red, koji ce garantovati da je donesena odluka o zameni (swap) elemenata 100% logicki u redu

Uparivanje svakog sa svakim clanom niza se postize dvostrukom unutrasnjiom petljom, sto je cest algoritam za mnoge slicne zadatke. Granice indeksa u tim petljama obezbedjuju da se uporedjivanje izvrsi u minimalnom broju ponavljanja i bez uporedjivanja elementa sa samim sobom.

Klasicana dvostruka unutrasnja petlja ide ovako:

Code:

I=PRVI_INDEKS_NIZA ... POSLEDNJI_INDEKS_NIZA - 1
J=TRENUTNI_INDEKS_SPOLJASNJE_I_PETLJE + 1 ... POSLEDNJI_INDEKS_NIZA

Zasto "minus jedan" (POSLEDNJI_INDEKS_NIZA - 1) ?

- Ako imas niz: 123456789, ono "-1" obezbedjuje da I petlja u svjoj poslednjoj iteraciji uzme broj 8 (ne 9!), a J petlja ce uzeti broj 9, tako da ce poslednje uporedjivanje biti: 8 sa 9.

Zasto "plus jedan" (TRENUTNI_INDEKS_SPOLJASNJE_I_PETLJE + 1) ?

- Ako imas niz: 123456789, ono "+1" obezbedjuje da J petlja u svjoj prvoj iteraciji uzme broj 2 (ne 1!), a I petlja ce uzeti broj 1, tako da ce prvo uporedjivanje biti: 1 sa 2.

Polako prati sta se s cime uporedjuje i kada se vrsi zamena elemenata i uvideces da sve to zajedno ima smisla.

E sad, kod tebe u zadatku je slicno tome, samo sto porednjenje ide unazad. Mada algoritam je semanticki isti.

[ Shadowed @ 13.02.2010. 15:20 ] @

S' tim da nije lose dodati i proveru da li je bilo nekih zamena i ako nije, prestati sa sortiranjem.

[ Danijel Bulic @ 13.02.2010. 18:06 ] @

Aha, hvala puno na objasnjenu, sad mi je vec dosta jasnije. Samo sto mi je trebalo malo vremena da ja to sve provjerim :=)

[ Danijel Bulic @ 16.02.2010. 18:35 ] @

Eo jedno pitanjce.

Jel se moze ovom metodom sortirati npr. slova u matrici. dakle, incijaliziramo matricu (sa slvoima tipa A B D, G E S itdd.) i onda ovom metodom sortirati po abecedi ?

[ X Files @ 16.02.2010. 20:10 ] @

Citat:

Jel se moze ovom metodom sortirati npr. slova u matrici. dakle, incijaliziramo matricu (sa slvoima tipa A B D, G E S itdd.) i onda ovom metodom sortirati po abecedi ?

Sve što ima definisan "redosled" se može sortirati.

Slova u ASCII tabeli imaju svoj redni broj, a C/C++ jezici "char" tip praktično konvertuju u "int", tako da svakako može. Drugim rečima, niz koj se sortira bez problema moze biti "char" tipa, ne mora biti "int" tipa.

Ako je potrebno uvrstiti i ŠĐČĆžšđčć (ili ćiriličnu verziju istog), onda je najbolje napraviti konverzionu tabelu, koja je u suštini paralelna tabela koja definiše željeni redosled.

Ne razumem o kakvoj matrici govoriš. Možda si mislio na niz?

[ Wajda.W @ 16.02.2010. 20:32 ] @

Mozda je mislio da sortira stringove, pa mu je niz stringova delovao kao matrica...

[ Danijel Bulic @ 17.02.2010. 01:03 ] @

Aha , mislim da sam onda ok napravio. Ne znam je li to matrica ali trebalo je napraviti tablicu 3x3 sa slovima i onda slova po abecedi napisati. Ja sam to radio pomocu matrice (T[3][3]) i onda sortirao slova po abecedi ovom metodom.

[ Shadowed @ 17.02.2010. 02:56 ] @

Ako mozes napraviti funkciju Compare(x, y) koja vraca x ukoliko je veci ili jedna y a y ako nije kojoj ces prosledjivati elemente niza - mozes sortirati, ma sta x i y bili.
Matrica se moze predstaviti i kao niz pa samim tim i sortirati.

[ X Files @ 17.02.2010. 07:42 ] @

Kao što reče Shadowed, matrica se može predstaviti kao niz, a može i obrnuto (pogotovo preko pokazivača, ali to je druga tema).

Recimo možeš podatke koji su već u matrici posmatrati kao jedan niz od N*N elemenata, pa iskoristiti pomenuti bubble-sort algoritam da sortiraš po redu.

Pretvaranje rednog broja niza u vrstu & kolonu matrice možeš uraditi sa deljenjem i modulom:

vrsta = REDNI_BROJ_ELEMENTA_NIZA_OD_NULTOG_INDEKSA / DIMENZIJA_MATRICE;
kolona = REDNI_BROJ_ELEMENTA_NIZA_OD_NULTOG_INDEKSA % DIMENZIJA_MATRICE;

Dakle, ako imaš neki niz kao što je prikazano, broj 6, (njegov indeks je 5, jer indeksi idu od 0):



1 2 3 4 5 6 7 8 9

... u matrci (posmatrano kao matrica):

... ima položaj:
vrsta = 5 / 3 = 1
kolona = 5 % 3 = 2

... odnosno:
matrica[1][2] == 6

// evo i parce koda, da se vidi o cemu se radi:

Code:

// netestirano
#include <stdio.h>
#include <stdlib.h>

int main()
{
    /* indeksi za dvostruku unutrasnju petlju */
    int i, j;

    /* izracunavanje vrste i kolone kvadratne matrice, za oba broja (slova) koji ce se uporedjivati u bubble sortu */
    int i_vrsta, i_kolona, j_vrsta, j_kolona;

    /* za zamenu vrednosti */
    char pomocni;

    /* test podaci */
    const int n=4;
    char matrica[4][4]=
    {
        { 'd','o','j','f' },
        { 'e','p','k','m' },
        { 'n','l','b','g' },
        { 'i','a','h','c' }
    };

    /* ispis pre sortiranja */
    for ( i=0; i<n; i++ )
    {
        for ( j=0; j<n; j++ )
            printf( "%c", matrica[i][j] );
        printf( "\n" );
    }

    /* sortiranje */
    printf("\n\nSortiranje...\n\n");
    for ( i=0; i<n*n-1; i++ )
        for ( j=i+1; j<n*n; j++ )
        {
            i_vrsta = i / n;
            i_kolona = i % n;

            j_vrsta = j / n;
            j_kolona = j % n;

            if ( matrica[i_vrsta][i_kolona] > matrica[j_vrsta][j_kolona] )
            {
                pomocni = matrica[i_vrsta][i_kolona];
                matrica[i_vrsta][i_kolona] = matrica[j_vrsta][j_kolona];
                matrica[j_vrsta][j_kolona] = pomocni;
            }
        }

    /* ispis posle sortiranja */
    for ( i=0; i<n; i++ )
    {
        for ( j=0; j<n; j++ )
            printf( "%c", matrica[i][j] );
        printf( "\n" );
    }

    return 0;
}

[ Danijel Bulic @ 17.02.2010. 18:46 ] @

Hvala na objasnjenju, mislio sam da je jednostavnije, izgleda da ipak nisam dobro radio.

[ Shadowed @ 17.02.2010. 19:53 ] @

Citat:

X Files:
vrsta = REDNI_BROJ_ELEMENTA_NIZA_OD_NULTOG_INDEKSA / DIMENZIJA_MATRICE;
kolona = REDNI_BROJ_ELEMENTA_NIZA_OD_NULTOG_INDEKSA % DIMENZIJA_MATRICE;

'De li je Rajko sad da te vidi

[ X Files @ 17.02.2010. 19:56 ] @

Off: Gde li je stvarno taj čovek, nema diskusije bez njega...