Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Algorytm partycjonowania pod quicksort

Ostatnio zmodyfikowano 2018-01-16 00:31
Autor Wiadomość
Kejsar
Temat założony przez niniejszego użytkownika
Algorytm partycjonowania pod quicksort
» 2018-01-13 14:31:40
Witam.
Ostatnio postanowiłem nauczyć się pisać i zrozumieć algorytm quicksort. Zacząłem od analizy algorytmu partycjonującego. Niestety program, który napisałem z pomocą pewnych źródeł nie zawsze dzieli liczby prawidłowo. Poniżej wklejam kod źródłowy zawierający jeden z przykładowych zbiorów liczb, które program błędnie partycjonuje.

C/C++
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
    //srand(time(NULL));
    int p, q, o, * tab, n;
    //cin>>n;
    n = 5;
    tab = new int[ n ];
   
    /*cout<<endl;
        for(int i=0; i<n; i++)
        {
            tab[i]=rand()%101+1;
            if(i==((n-1)/2)) cout<<tab[i]<<" <--"<<endl;
                else cout<<tab[i]<<endl;
        }
        cout<<endl;*/
    tab[ 0 ] = 86;
    tab[ 1 ] = 37;
    tab[ 2 ] = 45;
    tab[ 3 ] = 62;
    tab[ 4 ] = 85;
   
    p = 0;
    q = n - 1;
    o = tab[( n - 1 ) / 2 ];
    do
    {
        while( tab[ p ] < o ) p++;
       
        while( tab[ q ] > o ) q--;
       
        if( p <= q )
        {
            swap( tab[ p ], tab[ q ] );
            p++;
            q--;
        }
    } while( p <= q );
   
    for( int i = 0; i < n; i++ )
    {
        if( tab[ i ] == o ) cout << tab[ i ] << " <---" << endl;
        else cout << tab[ i ] << endl;
       
    }
   
    return 0;
}

W takiej kolejności zostają wyświetlone liczby: 45, 37, 86, 62, 85.
37 jest mniejsze od 45, więc raczej powinno znaleźć się po lewej stronie tego separatora w poprawnie napisanym algorytmie (no chyba że w quicksort taka sytuacja jest dopuszczalna).

Z góry dziękuję za pomoc :)
P-168687
nanoant20
» 2018-01-13 19:32:05
brak rekurencji
to jest algorytm, który został napisany jako funkcja rekurencyjna
zobacz jak wyglada funkcja, której u ciebie defacto nie ma.
http://cpp0x.pl/kursy​/Algorytmy/Sortowanie-danych​/Sortowanie-szybkie-ang-quick-s​ort​/450

P.S.
1. jak tworzysz tablice dynamiczną, to na końcu zwalniaj pamięć
2. daj linka do twojego źródła
P-168691
Kejsar
Temat założony przez niniejszego użytkownika
» 2018-01-15 23:04:10
Źle mnie zrozumiałeś. Wiem, że quicksort to algorytm rekurencyjny, że funkcja musi się odwoływać do samej siebie, ale najpierw chciałem napisać ten algorytm segregujący liczby na większe i mniejsze od separatora, a niestety nie zawsze on działa poprawnie.
P-168777
DejaVu
» 2018-01-16 00:31:32
Użyj debuggera i przeanalizuj co się dzieje w Twoim programie.
P-168778
« 1 »
  Strona 1 z 1