[es] - Bubble sort problem

NYXY
Hrvatska

Član broj: 126762
Poruke: 60
*.adsl.net.t-com.hr.

Profil

^{10.05.2007. u 17:38 - pre 206 meseci}

Odlučio sam posvetiti malo više pažnje algoritmima i krenuo sam od najjednostavnijih primjera i odam na početku zapeo:
ne znam zašto ovaj kodi iz bubble sorta ne radi kako treba

Code:

#include <iostream>
#include <cstdio>

using namespace std;

int main (){
    int a;
    const int max=100;
    int polje[max]={10,3,67,8,22,9,1,17,5,11,38,97,4,34,21,6,69};

    for (int i=max-1;i>0;i--)
    {bool zamjena =false;
        for (int j=0;j<i;j++){
        if (polje[j+1]<polje[j])
        {
        a=polje[j];
        polje[j]=polje[j+1];
        polje[j+1]=a;
        zamjena=true;
         cout<<polje[j]<<endl;
        }
         }
   }

system ("pause");
return 0;
}

Unaprjed vam hvala

Odgovor na temu

mizob

Član broj: 13465
Poruke: 1108
147.91.1.*

+5 Profil

Re: Bubble sort problem

^{10.05.2007. u 18:12 - pre 206 meseci}

Mnogo si mi nesto ti to iskomplikovao, prva petlja za cega ti sluzi uopste?
Trebas to ovako da uradis npr:

Code:

int main (){
    int a;
    const int max=22;
    int polje[max]={10,3,67,8,22,9,1,17,5,11,38,97,4,34,21,6,69};

    for (int i=0; i < max-1; i++)
    {
        for (int j=0; j<max; j++){
        if (polje[j]<polje[i]) // pogledaj da se ovde koristi j,i, a ne j , j+1, kao sto si ti uradio.
        {
        a=polje[j];
        polje[j]=polje[i];
        polje[i]=a;
        }
         }
   }

    for (int i=0; i < max-1; i++)
    {
        cout<<polje[i]<<endl;
   }

return 0;
}

Odgovor na temu

NYXY
Hrvatska

Član broj: 126762
Poruke: 60
*.adsl.net.t-com.hr.

Profil

Re: Bubble sort problem

^{10.05.2007. u 18:35 - pre 206 meseci}

Hvala,ovaj kod sam našao u knjizi "Demistificirani C++

Odgovor na temu

vlaiv
Vladimir Vlaisavljevic
Novi Sad

Član broj: 15993
Poruke: 352
212.200.249.*

+1 Profil

Re: Bubble sort problem

^{11.05.2007. u 11:11 - pre 206 meseci}

ne znam da li to spada u "standardni" bubble sort ali postoji
jedna "optimizacija" koja ubrzava sortiranje ...

u navedenom primeru postoje dve petlje:

Code:

for i = 0 to n-2
  for o = 0 to n-2
    if a[o]>a[o+1]
     swap(o,o+1)

(ovo gore navedeno je cini mi se ispravan bubble sort)

Spoljasnja petlja se koristi za slucaj "najgoreg" slucaja kada je najveci element na prvom
mestu ili najmanji element na zadnjem mestu pa je potrebno N-1 pomeranja da bi
dati element dosao na pravu poziciju.

primer

X Y 0 startna pozicija

X 0 Y 1 prolaz

0 X Y 2 prolaz

X,Y > 0

e sada, u opstem slucaju nije potrebno toliko pomeranja tako da savetujem modifikaciju:

Code:

bool swapped = true

while(swapped){
  swapped = false
  for i = 0 to n-2
    if a[i]>a[1+1]{
      swap(i,i+1)
      swapped = true
    }
}

U ovom slucaju pratimo da li je bilo zamena mesta - ukoliko nije - sortiranje je gotovo ...

Dati primer ima manu u slucaju da je u pitanju "worst case" scenario, u tom slucaju umesto
N-1 prolaza imamo N prolaza (poslednji da se utvrdi da je niz sortiran, odnosno da swapped ostane false)

Odgovor na temu