04. april 2008 - 12:59Der er
7 kommentarer og 1 løsning
merge() funktion
Hej, er der nogen som kan spotte en fejl i min merge() funktion? Meningen er, at jeg skal sortere mit data-array således, at alle tal står i stigende orden. Det jeg gør er at flytte indholdet af mit data-array over i et temp-array, hvorefter jeg gemmer alt hvad jeg har i temp-array over i data-array igen. Problemet er, at det ikke virker efter hensigten, eftersom jeg ikke får sorteret tallene korrekt.
Jeg forstår ikke helt måden du implementerer din Merge-Sort ... Hvad angiver n1, n2, p1 og p2??
Merge-Sort fungerer på følgende måde: 1) Merge-Sort modtager et array. 2) Den deler det op i midten og kalder sig selv rekursivt på begge dele. 3) Den merger (fletter) de to sorterede arrays den modtager fra de rekursive kald.
Jeg håber det kan hjælpe dig lidt. Jeg er ikke C++-programmør, men jeg kan lige se på om jeg kan implementere det :)
Forusætning: For at det kan virke skal de 2 dele af arrayet være sorteret i stigende orden allerede.
p2 = ( n1 + 1 ); <---- hvorfor dette?
ellers bør den indre betingelse nok omskrives til noget lettere hvis der ikke er tale om at sortere unike objekter.
for( int i = 0; i < ( n1 + n2 ); i++ ) { if( ((data[p1] <= data[p2]) && (p1 != n1)) || (p2 == n2+n1) ) { // slut på del 2. tempData[i] = data[p1]; p1++; } else { // hvis den ikke er mindre eller lig med så er den større, eller del 1 er slut. tempData[i] = data[p2]; p2++; } }
Tak for din interesse. Jeg har fået det til at virke nu. Jeg sætter lige implementeringen ind, så du kan se, hvordan jeg gør.
void mergesort(int data[], size_t n) { size_t n1; // size of the first subarray size_t n2; // size of the second subarray
if (n > 1) { n1=n/2; n2=n-n1;
mergesort(data,n1); mergesort(data+n1, n2);
merge(data, n1, n2); } }
segmose:
Efter jeg satte p2 = n1, så virker det :) Jeg tænkte at hvis arrayet var af ulige størrelse, så skulle dette problem håndteres, men... ja det gav ikke nogen mening alligevel :) Tak for hjælpen.
Det var også det jeg havde tænkt til at starte med, men det er ikke nødvendigt for selvom n1 og n2 ikke er lig hinanden, så kører min for løkke jo n1+n2 gange. Jeg skal bare sørge for, at min "pegepind" p1 går fra plads 0 til plads n1 og at min pegepind p2 starter fra n1 og går til n1 + n2.
n = 13; n1 = 13 / 2 = 6 n2 = n - n1 = 13 - 6 = 7
p1 går fra 0 til 6 (n1) p2 går fra 6 (n1) til 13 (n1 + n2)
Yes yes, men det er fordi a 13 / 2 = 6 ... Det er jo 6½, og så vil det ikke fungere helt ... Men godt det virker :)
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.