[ NYXY @ 10.05.2007. 17:38 ] @
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
[ mizob @ 10.05.2007. 18:12 ] @
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;
}



[ NYXY @ 10.05.2007. 18:35 ] @
Hvala,ovaj kod sam našao u knjizi "Demistificirani C++
[ vlaiv @ 11.05.2007. 11:11 ] @
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)