Algorytm partycjonowania pod quicksort
Ostatnio zmodyfikowano 2018-01-16 00:31
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. #include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main()
{
int p, q, o, * tab, n;
n = 5;
tab = new int[ n ];
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 :) |
|
nanoant20 |
» 2018-01-13 19:32:05 |
|
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. |
|
DejaVu |
» 2018-01-16 00:31:32 Użyj debuggera i przeanalizuj co się dzieje w Twoim programie. |
|
| « 1 » |