Temat: sortowanie bąbelkowe-problem

Witam serdecznie.
Mam zadanie wykonania programu do obliczania czasu sortowania (różnymi metodami). Mam do posortowania kilka typów danych: losowe, częściowo posortowanie, posortowane malejąco i posortowane rosnąco (jest to ten sam zbiór liczb, tylko odpowiednio poformatowany). Sortowanie ma być wykonane rosnąco, więc wg mnie czasy powinny układać się(od najmniejszego): posortowane rosnąco (tylko porównanie, bez przestawień)-> posortowane częściowo ( około 50% już posortowanych) -> losowo (głównie przestawienia + trochę porównań) ->posortowane malejąco (100% przestawień). Przy zbiorze testowym (testuję zakres 10k-20k elementów) wyniki pokazują taki układ: posortowane rosnąco-> posortowane malejąco-> częściowo posortowane-> losowe. Gdzie leży problem?

poniżej kod programu:

package javaapplication7;



import java.util.*;



class Sortowanie

{

 private int ilosc;

 final private int MAX;

 final private String[] NAZWY={"Babelkowe","Przez zliczanie","Przez wstawianie",

                               "Quick sort","Przez wybieranie","przez wstrząsanie",

                                "Przez scalanie"};

 final private String[] TYP={"losowo: ","czesciowo: ","rosnaco: ","malejaco: "};

 private int[][] liczby; 

 private long[][] czas;

 

 public Sortowanie()

 {

  Scanner pobierz=new Scanner(System.in);

  

    System.out.print("podaj ilosc elementow do sortowania: ");

    ilosc=pobierz.nextInt();

    liczby=new int[TYP.length][ilosc];

    czas=new long[NAZWY.length][TYP.length]; //0-losowo,1-czesciowo,2-rosnaco,3-malejaco

    MAX=10000; 

    

    losowanie();

    babelki();

    zliczanie();   

    //odpalenie sortowania przez wstawianie

    //odpalenie sortowania quick sort

    //odpalenie sortowania przez wybieranie

    //odpalenie sortowania przez wstrzasanie

    //odpalenie sortowania przez scalanie

    wypisz_dane();

 }

 

 void losowanie()

 {

  int i,j,bufor,maks=0;   

  Random losuj=new Random();  



//--------------------losowo--------------------

  

    for(i=0;i<ilosc;i++)

      liczby[0][i]=losuj.nextInt(MAX)+1; 

    

//--------------------czesciowo--------------------    

    

    System.arraycopy(liczby[0], 0, liczby[1], 0, liczby[0].length);

    for(i=0;i<liczby[1].length-1;i++)

    {    

      for(j=0;j<liczby[1].length-i-1;j++)

        if(liczby[1][j]>liczby[1][j+1])

        {

           bufor=liczby[1][j];

           liczby[1][j]=liczby[1][j+1];

           liczby[1][j+1]=bufor;

        }

      i++; 

    }



//--------------------rosnaco/malejaco--------------------    

    

    System.arraycopy(liczby[0], 0, liczby[2], 0, liczby[0].length); 

    for(i=0;i<liczby[2].length;i++)

      if(liczby[2][i]>maks) maks=liczby[2][i];

  int[] tab=new int[maks+1];

    j=0;

    for(i=0;i<tab.length;i++)

      tab[i]=0;  

    for(i=0;i<liczby[2].length;i++)

      tab[liczby[2][i]]++;

    for(i=0;i<tab.length;i++)

      if(tab[i]>0)

        for(int k=0;k<tab[i];k++)

        {

           liczby[2][j]=i;

           liczby[3][liczby[3].length-j-1]=i; //malejaca

           j++;

        } 

} 

 

 void wypisz_dane()

 {

    for(int i=0;i<2;i++)  //NAZWY.length

    {    

       System.out.println(NAZWY[i]);

       for(int j=0;j<TYP.length;j++) 

         System.out.println(TYP[j]+czas[i][j]);

       System.out.println();

    }

 }        

 

 void babelki()

 {

  int[] tab=new int[ilosc];         

  int i,j,bufor;

  long start,stop;



    for(int n=0;n<liczby.length;n++)

    {    

       System.arraycopy(liczby[n], 0, tab, 0, liczby[n].length); 

       start=System.currentTimeMillis();    

       for(i=0;i<tab.length-1;i++)

         for(j=0;j<tab.length-i-1;j++)

           if(tab[j]>tab[j+1])

           {

              bufor=tab[j];

              tab[j]=tab[j+1];

              tab[j+1]=bufor;

           } 

       stop=System.currentTimeMillis();  

       czas[0][n]=stop-start;  

    }         

 }    

 

 void zliczanie()

 {

  int maks,i;

  long start,stop;



    for(int n=0;n<liczby.length;n++)

    {  

       start=System.currentTimeMillis();  

       maks=0;

       for(i=0;i<liczby[n].length;i++)

         if(liczby[n][i]>maks) 

           maks=liczby[n][i];   

  int[] tab=new int[maks+1];    

       for(i=0;i<tab.length;i++)

         tab[i]=0;  

       for(i=0;i<liczby[n].length;i++)

         tab[liczby[n][i]]++;    

       stop=System.currentTimeMillis();  

       czas[1][0]=stop-start;    

    }   

 }        

 

 void wstawianie()

 {

  int[] tab=new int[ilosc];

  int bufor;

  

 

 }        

}





public class JavaApplication7 

{    

 public static void main(String[] args) 

 {

   Sortowanie sort=new Sortowanie();     

 }   

}

z góry dziękuję za pomoc :)Marcin Barańczak edytował(a) ten post dnia 24.05.12 o godzinie 20:57

Temat: sortowanie bąbelkowe-problem

Marcin,

Przepraszam, że nie na temat sortowania, ale.... ten kod czyta się fatalnie. Tak bardzo, że nawet nie chciało mi się wczytywać. Sorry...

Być może powinieneś spojrzeć na te pozycje:
Java Coding Conventions
Clean Code

A co do samych algorytmów tutaj znajdziesz ich porównanie z czasami średnimi, pesymistycznymi itd.

Rafał

Temat: sortowanie bąbelkowe-problem

void babelki()
{
int[] tab=new int[ilosc];
int i,j,bufor;
long start,stop;

for(int n=0;n<liczby.length;n++)
{
System.arraycopy(liczby[n], 0, tab, 0, liczby[n].length);
start=System.currentTimeMillis();
for(i=0;i<tab.length-1;i++)
for(j=0;j<tab.length-i-1;j++)
if(tab[j]>tab[j+1])
{
bufor=tab[j];
tab[j]=tab[j+1];
tab[j+1]=bufor;
}
stop=System.currentTimeMillis();
czas[0][n]=stop-start;
}
}

zamień na to:

void babelki()
{
int[] tab=new int[ilosc];
int i,j,bufor;
long start,stop;
start=System.currentTimeMillis();
for(int n=0;n<liczby.length;n++)
{
System.arraycopy(liczby[n], 0, tab, 0, liczby[n].length);
for(i=0;i<tab.length-1;i++)
for(j=0;j<tab.length-i-1;j++)
if(tab[j]>tab[j+1])
{
bufor=tab[j];
tab[j]=tab[j+1];
tab[j+1]=bufor;
}
}
stop=System.currentTimeMillis();
czas[0][n]=stop-start;
}

a jeszcze lepiej daj brejka, który wywala z zewnętrznej pętli jeżeli w wewnętrznej nie było zamiany

poza tym:
- funkcje powinny być krótkie
- stosuj się do javowej konwencji pisania kodu (mi się co prawda to lepiej czyta, bo w .netach siedzę, ale tak się nie robi)

Temat: sortowanie bąbelkowe-problem

1) W konstruktorze nie powinno się znajdować całe działanie programu. Konstruktory nie są od tego. Deleguj działanie obiektu do metod.
2) currentTimeMillis może mieć zbyt małą rozdzielczość (na Win to chyba 3ms) na tego typu badania. Warto używać System.nanoTime().
3) przy każdym if, for, while, etc. warto wstawiać {}. Jest to czytelniejsze, ułatwia debugowanie, no i nie trzeba tego robić potem, kiedy i tak się okaże, że musisz coś dodać do danej pętli.

Temat: sortowanie bąbelkowe-problem

Dariusz Wawer:
2) currentTimeMillis może mieć zbyt małą rozdzielczość (na Win to chyba 3ms) na tego typu badania. Warto używać System.nanoTime().

jak ma wykonać 20k^2 operacji to myślę, że wystarczy. problem był taki, że mierzony był czas tylko wewnętrznej pętli

Temat: sortowanie bąbelkowe-problem

Dziękuję bardzo za odpowiedzi.:)

Temat: sortowanie bąbelkowe-problem

spoko ;) powodzenia w nauce