|
TwojePC.pl © 2001 - 2025
|
 |
A R C H I W A L N A W I A D O M O Ś Ć |
 |
| |
|
Problem z quicksortowym rozdzielaniem w C , laciak88 9/12/09 17:47
Rozwiazanie pewnie jest jak zwykle banalne, ale cos nie moge na nie wpasc. Problemem jest podzial quicksorta (potrzebuje podzial, bez rekurencji) - przy sortowaniu rosnacym za os dostaje sie 1 mniejsza od niej liczba. Kod wyglada tak:
odp.tablica[0] = 44;
odp.tablica[1] = 75;
odp.tablica[2] = 98;
odp.tablica[3] = 43;
odp.tablica[4] = 55;
odp.tablica[5] = 12;
odp.tablica[6] = 64;
odp.tablica[7] = 77;
odp.tablica[8] = 33;
odp.tablica[9] = 14;
odp.tablica[10] = 31;
odp.tablica[11] = 13;
odp.tablica[12] = 27;
odp.tablica[13] = 56;
odp.tablica[14] = 66;
odp.tablica[15] = 62;
odp.tablica[16] = 54;
odp.tablica[17] = 45;
odp.tablica[18] = 11;
odp.tablica[19] = 99;
test[0] = 44;
test[1] = 75;
test[2] = 98;
test[3] = 43;
test[4] = 55;
test[5] = 12;
test[6] = 64;
test[7] = 77;
test[8] = 33;
test[9] = 14;
test[10] = 31;
test[11] = 13;
test[12] = 27;
test[13] = 56;
test[14] = 66;
test[15] = 62;
test[16] = 54;
test[17] = 45;
test[18] = 11;
test[19] = 99;
lewa=0;
prawa=19;
osa=test[(lewa+prawa)/2];
do
{
while (test[lewa]<osa)
{
lewa++;
}
while (test[prawa]>osa)
{
prawa--;
}
if (lewa <= prawa)
{
tempp = test[lewa];
test[lewa] = test[prawa];
test[prawa] = tempp;
lewa++;
prawa--;
}
} while (lewa < prawa);
printf("\nTABLICA TESTOWA: %d");
for(i=0;i<20;i++)
printf("%d ",test[i]);
wynik wyglada tak: 11 13 14 12 55 43 64 77 33 98 31 75 27 56 66 62 54 45 44 99
a powinien tak: 11 13 12 14 55 43 64 77 33 98 31 75 27 56 66 62 54 45 44 99
Co ta dwunastka chce od wiekszych? Prosze o pomoc. Dzieki z gory za nakierowanie/poprawe :)"To Alcohol! The cause of, and solution to, all of
life's problems." - za szybko , laciak88 9/12/09 17:48
wkleilem. oczywiscie mialo byc bez odp.tablica"To Alcohol! The cause of, and solution to, all of
life's problems." - Wynik jest OK , Visar 10/12/09 14:15
Na końcu algorytmu podział masz po 4 elemencie i wszystkie elementy <=14 są po lewej stronie podziału, a większe po prawej. Nie ustaliłeś granicy podziału jako indeksu tylko jako wartość i na końcu masz to spełnione.
Zaś 12 jako osatnia została porównana, dlatego ustawiła się na końcu liczb mniejszych lub równych od 14, ale wciąż dobrze.
Na początku 11 jest zamieniana z 44, 13 z 75, 14 z 98 i w końcu 12 z 43.Visar - ale , laciak88 10/12/09 14:19
liczba 14 zostaje elementem osiowym, nie 4 element. Czyli, ze jak? Brakuje jednego porownania? 14 z 12?"To Alcohol! The cause of, and solution to, all of
life's problems."
- Element osiowy , Visar 10/12/09 14:52
W podanym przykładzie kodu, kiedy wybierasz element osiowy z połowy tablicy, element ten może się przemieścić. Możesz zapamiętać jego indeks podczas przemieszczania i na końcu zamieniać go z elementem na granicy podziału, ale nie ma takiej konieczności, gdyż następne wywołanie qsorta (od lewej granicy do granicy podziału) i tak go w końcu ustawi.
Jeśli chcesz aby element osiowy rzeczywiście znalazł się na granicy to najprościej wybierz go jako pierwszy element z tablicy, podziel tablicę zaczynając od drugiej pozycji i na końcu zamień wartości pierwszą i tą z granicy podziału. Wtedy element osiowy rozgraniczy elementy mniejsze od niego od tych większych.Visar
|
|
|
|
 |
All rights reserved ® Copyright and Design 2001-2025, TwojePC.PL |
 |
|
|
|
