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

Bubble sort problem

[es] :: Art of Programming :: Bubble sort problem

[ Pregleda: 3174 | Odgovora: 3 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

NYXY
Hrvatska

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



Profil

icon Bubble sort problem10.05.2007. u 17:38 - pre 185 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

icon Re: Bubble sort problem10.05.2007. u 18:12 - pre 185 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

icon Re: Bubble sort problem10.05.2007. u 18:35 - pre 185 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

icon Re: Bubble sort problem11.05.2007. u 11:11 - pre 185 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

[es] :: Art of Programming :: Bubble sort problem

[ Pregleda: 3174 | Odgovora: 3 ] > FB > Twit

Postavi temu Odgovori

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