Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Bubblesort metoda

[es] :: C/C++ programiranje :: C/C++ za početnike :: Bubblesort metoda

[ Pregleda: 3330 | Odgovora: 13 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Danijel Bulic
Danijel Bulic
Split

Član broj: 140925
Poruke: 116
*.adsl.net.t-com.hr.



+4 Profil

icon Bubblesort metoda12.02.2010. u 23:13 - pre 171 meseci
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;
}



ex. malak
 
Odgovor na temu

Picsel
Beograd

Član broj: 39817
Poruke: 440
95.180.74.*



+7 Profil

icon Re: Bubblesort metoda13.02.2010. u 10:45 - pre 171 meseci
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.
 
Odgovor na temu

X Files
Vladimir Stefanovic
Pozarevac

SuperModerator
Član broj: 15100
Poruke: 4901
*.dynamic.sbb.rs.

Jabber: xfiles@elitesecurity.org


+638 Profil

icon Re: Bubblesort metoda13.02.2010. u 13:08 - pre 171 meseci
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.



 
Odgovor na temu

Shadowed
Vojvodina

Član broj: 649
Poruke: 12846



+4783 Profil

icon Re: Bubblesort metoda13.02.2010. u 15:20 - pre 171 meseci
S' tim da nije lose dodati i proveru da li je bilo nekih zamena i ako nije, prestati sa sortiranjem.
 
Odgovor na temu

Danijel Bulic
Danijel Bulic
Split

Član broj: 140925
Poruke: 116
*.adsl.net.t-com.hr.



+4 Profil

icon Re: Bubblesort metoda13.02.2010. u 18:06 - pre 171 meseci
Aha, hvala puno na objasnjenu, sad mi je vec dosta jasnije. Samo sto mi je trebalo malo vremena da ja to sve provjerim :=)
ex. malak
 
Odgovor na temu

Danijel Bulic
Danijel Bulic
Split

Član broj: 140925
Poruke: 116
*.adsl.net.t-com.hr.



+4 Profil

icon Re: Bubblesort metoda16.02.2010. u 18:35 - pre 171 meseci
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 ?
ex. malak
 
Odgovor na temu

X Files
Vladimir Stefanovic
Pozarevac

SuperModerator
Član broj: 15100
Poruke: 4901
*.dynamic.sbb.rs.

Jabber: xfiles@elitesecurity.org


+638 Profil

icon Re: Bubblesort metoda16.02.2010. u 20:10 - pre 171 meseci
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?


 
Odgovor na temu

Wajda.W
Vladimir Vajda
Zrenjanin

Član broj: 127039
Poruke: 323
109.93.216.*



+101 Profil

icon Re: Bubblesort metoda16.02.2010. u 20:32 - pre 171 meseci
Mozda je mislio da sortira stringove, pa mu je niz stringova delovao kao matrica...
 
Odgovor na temu

Danijel Bulic
Danijel Bulic
Split

Član broj: 140925
Poruke: 116
*.adsl.net.t-com.hr.



+4 Profil

icon Re: Bubblesort metoda17.02.2010. u 01:03 - pre 171 meseci
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.
ex. malak
 
Odgovor na temu

Shadowed
Vojvodina

Član broj: 649
Poruke: 12846



+4783 Profil

icon Re: Bubblesort metoda17.02.2010. u 02:56 - pre 171 meseci
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.
 
Odgovor na temu

X Files
Vladimir Stefanovic
Pozarevac

SuperModerator
Član broj: 15100
Poruke: 4901
212.200.65.*

Jabber: xfiles@elitesecurity.org


+638 Profil

icon Re: Bubblesort metoda17.02.2010. u 07:42 - pre 171 meseci
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):

1 2 3
4 5 6
7 8 9

... 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;
}
 
Odgovor na temu

Danijel Bulic
Danijel Bulic
Split

Član broj: 140925
Poruke: 116
*.adsl.net.t-com.hr.



+4 Profil

icon Re: Bubblesort metoda17.02.2010. u 18:46 - pre 171 meseci
Hvala na objasnjenju, mislio sam da je jednostavnije, izgleda da ipak nisam dobro radio.
ex. malak
 
Odgovor na temu

Shadowed
Vojvodina

Član broj: 649
Poruke: 12846



+4783 Profil

icon Re: Bubblesort metoda17.02.2010. u 19:53 - pre 171 meseci
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
 
Odgovor na temu

X Files
Vladimir Stefanovic
Pozarevac

SuperModerator
Član broj: 15100
Poruke: 4901
*.dynamic.sbb.rs.

Jabber: xfiles@elitesecurity.org


+638 Profil

icon Re: Bubblesort metoda17.02.2010. u 19:56 - pre 171 meseci
Off: Gde li je stvarno taj čovek, nema diskusije bez njega...
 
Odgovor na temu

[es] :: C/C++ programiranje :: C/C++ za početnike :: Bubblesort metoda

[ Pregleda: 3330 | Odgovora: 13 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.