07. oktober 2002 - 18:23Der er
7 kommentarer og 1 løsning
Quicksort
Hej alle! Mit program skal kunne sorterer et array i størrelsesorden efter pricippet "opdel", hvor arrayet hele tiden bliver opdelt i mindre bidder. De mindre tal før privot tallet og de større tal efter osv. Mit problem er at programmet udskriver arrayet som flg: 47 33 24 13 8 6 7 23 - imens jeg gerne vil have en udskrift der er : 6 7 8 1 23 24 33 47 Hvad er forkert? På forhånd tak Hilsner karina
mit program ser ud som flg:
#include <iostream> #include <conio> using namespace std;
Du har lavet en grundlæggende fejl i qsort algoritmen og din opdel() metode. Princippet i en qsort er at opdele data-sættet et eller andet sted (pivot'en), og så sørge for at alle elementer til venstre for dette sted er MINDRE og alle elementer til højre er STØRRE en elementet på stedet.
En almindelig teknik til at sikre dette, er at vælge det element der ligger i midten at tabellen og så bytte med elementer fra venstre side, som er større end midten. Derefter at gøre det samme med højre side. Dette gentages indtil der er byttet rundt så pivot'en opfylder ovenstående.
while (opIx < nedIx) { // B* Ingen optælning af opIx her. while (opIx < pivot && arr[opIx] <= arr[pivot]) // C* Kun op til pivot'en opIx++; while (arr[nedIx] > arr[pivot]) nedIx--;
if (opIx < nedIx) { ombyt(arr[opIx], arr[nedIx]);
// D* Flyt pivot til nye plads, hvis pivot blev ombyttet. if (pivot == opIx) pivot = nedIx; else if (pivot == nedIx) pivot = opIx; }; };
// Nu står 'pivot' korrekt. skriv(arr, startIx, slutIx);
/* Så skal venstre og højre side sorteres. */ quick(arr, startIx, pivot - 1); quick(arr, pivot + 1, slutIx); }
Du skal bemærke følgende ændringer:
A* Pivot vælges simpelthen som det midterste element. B* opIx må IKKE tælles op uden for while løkken. C* opIx må ikke overstige pivot'en indeks D* Indeks på pivot'en skal justeres hvis ombytningen "ramte" pivot'en.
Jeg har lagt ovenstående ind i dit program, og så kører det.
hej soepro! kan du så ikke skrive noget med et "svar", jeg vil meget gerne give dig point også. hilsner karina ps for det er jo altid rart at der er nogle som gider hjælpe
Jotak som byder - men man kan ikke svare på denne her mere.
Synes godt om
Ny brugerNybegynder
Din løsning...
Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.