Elektroda.pl
Elektroda.pl
X

Wyszukiwarki naszych partnerów

Wyszukaj w ofercie 200 tys. produktów TME
Europejski lider sprzedaży techniki i elektroniki.
Proszę, dodaj wyj±tek elektroda.pl do Adblock.
Dzięki temu, że ogl±dasz reklamy, wspierasz portal i użytkowników.

[C++] Sortowanie b±belkowe

Toshib 25 Kwi 2009 00:31 16358 8
  • #1 25 Kwi 2009 00:31
    Toshib
    Poziom 15  

    Oto mój kod na sortowanie b±belkowe, będę wdzięczny za wszelkie uwagi, spostrzeżenia i porady.

    Code:
    // Sortowanie babelkowe
    

    #include <iostream>

    using namespace std;

    void babelki(int tablica[100], int n);
    int pobranie_danych(int &n, int tablica[100]); 
    // n przesylamy do funkcji przez referencje, bo chcemy pracowac na oryginalnej zmiennej w funkcji a nie jej kopii,
    // tablica z definicji jest przesylana przez referencje

    int main()
    {
       int n,tablica[100]={0};
       if(pobranie_danych(n, tablica))  // jezeli wlasciwe dane(n>0)
       babelki(tablica, n);             // to wywolujemy wlasciwa funkcje
       return 0;
    }

    //*****************************************************************************

    void babelki(int tablica[100], int n)
    {
       int temp, counter=1, liczba_zamian=0, ilosc_przejsc=0;
       while(counter) // dopoki wystepuje co najmnniej jedna zamiana 2 elementow w tablicy
       {
       counter=0;  // zerujemy licznik zamian w jednym przejsciu tablicy
          for(int j=0; j<n-1; j++)  // wlasciwa petla, do n-1 bo statniego elementu nie musimy sprawdzac
          {
             if(tablica[j]>tablica[j+1])  // warunek zamiany
             {
                temp=tablica[j+1];               //
                tablica[j+1]=tablica[j];         // zamiana
                tablica[j]=temp;                 //
                counter++;  // wewnetrzny licznik ilosci zamian w jednym przejsciu tablicy
             }
          }
          if(!ilosc_przejsc) cout << endl;  // kosmetyczne
          cout << "Przejscie nr " << ilosc_przejsc+1 << ":       [";
          for(int k=0; k<n; k++)
          {
             cout << tablica[k];      // drukujemy czastkowe wyniki sortowania po kazdym kolejnym przejsciu
             if(k<n-1) cout << ", ";  // kosmetyczne, usuwamy przecinek po ostatnim elemencie




          }
          cout << "]" << endl;
          liczba_zamian=liczba_zamian+counter;   // laczna liczba zamian
          ilosc_przejsc++;                       // liczba przejsc tablicy
       }
       cout << endl << "Posortowana tablica: " << endl << "       [";
       for(int k=0; k<n; k++)
       {
          cout << tablica[k];         // drukowanie posortowanej tablicy
          if(k<n-1) cout << ", ";
       }
       cout << "]" << endl << endl << "Ilosc zamian liczb: " << liczba_zamian << endl;
       cout << "Ilosc przejsc przez tablice: " << ilosc_przejsc << endl;
    }

    //*****************************************************************************

    int pobranie_danych(int &n, int tablica[100])
    {
       cout << "Podaj liczbe wyrazow n: ";
       cin >> n;
       if(n<=0)
       {
          cout << "Zla liczba wyrazow!" << endl;
          return 0;  // zwracamy 0 czyli sortowanie sie nie odbedzie
       }
       for(int i=0; i<n; i++)  // petla do podawania elementow
       {
          cout << "Podaj element nr " << i+1 << ": ";
          cin >> tablica[i];
       }
       return 1;  // zwracamy 1 i mozemy sortowac
    }

  • #2 25 Kwi 2009 00:46
    elektryk
    Poziom 42  

    Wygl±da OK, nie podoba mi się tylko mieszanie ze zmienn± counter, ja bym użył pętli do...while, wtedy nie trzeba inicjować na pocz±tku zmiennej counter. Ja bym jeszcze zmienił nazwy zmiennych 'counter' i 'temp' na co¶ polskojęzycznego, tak żeby ujednolicić styl. Można jeszcze poprawić

    Code:
    liczba_zamian=liczba_zamian+counter 
    
    liczba_zamian+=counter

  • #3 25 Kwi 2009 01:38
    Dr.Vee
    VIP Zasłużony dla elektroda

    W sortowaniu b±belkowym w k-tym przebiegu możesz nie sprawdzać k-1 ostatnich elementów, ponieważ z definicji będ± one już w odpowiedniej kolejno¶ci - np. po pierwszym przebiegu największa liczba w tablicy zostanie przeniesiona na ostatnie miejsce.

    Poza tym w pobranie_danych() nie sprawdzasz stanu strumienia cin przy wczytywaniu liczb.

    Pozdrawiam,
    Dr.Vee

  • #4 25 Kwi 2009 10:41
    elektryk
    Poziom 42  

    Dr.Vee napisał:
    W sortowaniu b±belkowym w k-tym przebiegu możesz nie sprawdzać k-1 ostatnich elementów, ponieważ z definicji będ± one już w odpowiedniej kolejno¶ci - np. po pierwszym przebiegu największa liczba w tablicy zostanie przeniesiona na ostatnie miejsce.
    Tyle że to nie jest wtedy "czysty" wariant, a wariant z b±belkiem i kamieniem. Do tego po k przej¶ciach także elementy od 0 do k-1 (b±belki wypływaj± na wierzch) s± już posortowane. Te drugie o który Dr.Vee wspomniał to s± "kamienie które opadły na dno".

  • #5 25 Kwi 2009 14:09
    Toshib
    Poziom 15  

    Nie rozumiem o co wam chodzi z tymi b±belkami, kamieniami i wypływaniem na wierzch? Mogliby¶cie przedstawić to bardziej obrazowo? Jaki¶ obrazek, animacja?

  • #6 25 Kwi 2009 15:33
    peterpz
    Poziom 9  

    A po co to tak komplikować???? Przecież to najprostsze do zaimplementowania sortowanie. Oto kod w matlabie, bo nie chce mi się przerabiać na c++:

    Code:
    function a=bubblesort (a)
    
    for j =length(a)-1:-1:1
       for i =1:j
             if (a(i+1)<a(i))
                pom=a(i); a(i)=a(i+1); a(i+1)=pom;
             end
       end
    end

  • #7 25 Kwi 2009 22:24
    Toshib
    Poziom 15  

    Dokonałem paru poprawek:
    1. Tablice przesyłane do funkcji w sposób tablica[], a więc poprzez wskaĽnik do ich zerowego elementu;
    2. Lepsza kontrola danych wej¶ciowych (n>100);
    3. Funkcja nie sortuje elementów już posortowanych, co przyspiesza algorytm i zmniejsza liczbę wywołań wewnętrznej funkcji;
    4. Funkcja pobierania danych zwraca typ bool;

    Code:
    // Sortowanie babelkowe
    

    #include <iostream>

    using namespace std;

    void babelki(int tablica[], int n);
    bool pobranie_danych(int &n, int tablica[]); 
    // n przesylamy do funkcji przez referencje, bo chcemy pracowac na oryginalnej zmiennej w funkcji a nie jej kopii,
    // tablica z definicji jest przesylana przez referencje

    int main()
    {
       int n,tablica[100]={0};
       if(pobranie_danych(n, tablica))  // jezeli wlasciwe dane(n>0)
       babelki(tablica, n);             // to wywolujemy wlasciwa funkcje
       return 0;
    }

    //*****************************************************************************

    void babelki(int tablica[], int n)
    {
       int temp, counter=1, liczba_zamian=0, ilosc_juz_posortowanych=1, ilosc_przejsc=0, licz=0;
       while(counter) // dopoki wystepuje co najmnniej jedna zamiana 2 elementow w tablicy
       {
       counter=0;  // zerujemy licznik zamian w jednym przejsciu tablicy
          for(int j=0; j<n-ilosc_juz_posortowanych; j++)  // wlasciwa petla, do n-1 bo statniego elementu nie musimy sprawdzac
          {
             if(tablica[j]>tablica[j+1])  // warunek zamiany
             {
                temp=tablica[j+1];               //
                tablica[j+1]=tablica[j];         // zamiana
                tablica[j]=temp;                 //
                counter++;  // wewnetrzny licznik ilosci zamian w jednym przejsciu tablicy
             }
          }
          ilosc_juz_posortowanych++;
          if(!ilosc_przejsc) cout << endl;  // kosmetyczne
          cout << "Przejscie nr " << ilosc_przejsc+1 << ":       [";
          for(int k=0; k<n; k++)
          {
             cout << tablica[k];      // drukujemy czastkowe wyniki sortowania po kazdym kolejnym przejsciu
             if(k<n-1) cout << ", ";  // kosmetyczne, usuwamy przecinek po ostatnim elemencie
          }
          cout << "]" << endl;
          liczba_zamian=liczba_zamian+counter;   // laczna liczba zamian
          ilosc_przejsc++;                       // liczba przejsc tablicy
       }
       cout << endl << "Posortowana tablica: " << endl << "       [";
       for(int k=0; k<n; k++)
       {
          cout << tablica[k];         // drukowanie posortowanej tablicy
          if(k<n-1) cout << ", ";
       }
       cout << "]" << endl << endl << "Ilosc zamian liczb: " << liczba_zamian << endl;
       cout << "Ilosc przejsc przez tablice: " << ilosc_przejsc << endl;
    }

    //*****************************************************************************

    bool pobranie_danych(int &n, int tablica[])
    {
       cout << "Podaj liczbe wyrazow n: ";
       cin >> n;
       if((n<=0) || (n>100))
       {
          cout << "Zla liczba wyrazow!" << endl;
          return 0;  // zwracamy 0 czyli sortowanie sie nie odbedzie
       }
       for(int i=0; i<n; i++)  // petla do podawania elementow
       {
          cout << "Podaj element nr " << i+1 << ": ";
          cin >> tablica[i];
       }
       return 1;  // zwracamy 1 i mozemy sortowac
    }


    Będę nadal wdzięczny za wszelkie uwagi, spostrzeżenia i porady.

  • #8 26 Kwi 2009 08:58
    peterpz
    Poziom 9  

    Toshib napisał:
    Dokonałem paru poprawek:
    3. Funkcja nie sortuje elementów już posortowanych, co przyspiesza algorytm i zmniejsza liczbę wywołań wewnętrznej funkcji;

    Też kiedy¶ implementowałem tak "poprawiony" algorytm, jednak na ostatnim semestrze miałem przedmiot o algorytmach i teraz nie jest to takie pewne dla mnie, że ten algorytm będzie szybszy. Dodanie if-a w ¶rodku, sprawdzaj±cego posortowalno¶ć może jeszcze bardziej zwiększyć złożono¶ć obliczeniow±. Mniejsza liczba wywołań wewnętrznych nie oznacza, że będzie szybciej, bo zależy ile w ¶rodku wszystko będzie się liczyło. If-y s± do¶ć złożone obliczeniowo. Należałoby przeprowadzić stosowne testy na konkretnej maszynie...

  • #9 26 Kwi 2009 12:27
    Toshib
    Poziom 15  

    Ale zauważ, że ja nie dodałem żadnego if-a, tylko zmodyfikowałem warunek końcowy głównego fora.

 Szukaj w ofercie
Zamknij 
Wyszukaj w ofercie 200 tys. produktów TME