03. oktober 2004 - 22:25Der er
5 kommentarer og 1 løsning
quicksort linked list ?
hejsa! Har fået til opgave (i skolen) at lave en quicksort algoritme som kunne sortere et array. Dette var ikke så vanskeligt, men så bliver jeg bedt om at få den til at virke på linked list også. Jeg har ingen anelse om hvordan jeg skal starte da jeg ikke længere kan tilgå de elementerne direkte. Eneste metode jeg kan kom i tanke om er at kopiere pointerne over i et array og så bare lave min swap funktion til håndtere struktuere istedet for int's. Men så er der jo ikke rigtig længere nogen fidus i quicksort.
Min quicksort ser således ud:
void quickSort(int a[], int left, int right){ int pivot, p_left, p_right, i, p_pos; void swap(int a[], int x, int y);
Det er ikke så traditionelt at bruge linkede lister, men man kan godt.
1) Du skal sørge for at du i dine linkede lister kan tilgå både første og sidste element direkte, så du nemt kan indsætte for enden af listen. Du skal også umiddelbart kende længden, uden at løbe listen igennem.
2) Først trin er det samme som med array. Hvis listen er på 0 eller 1 element, så er den sorteret.
3) Hvis der er 2 eller flere skal du nu vælge et pivotelement. Er listen helt usorteret, er det altid fint nok at bruge det første element, så da det er en skoleopgave, så siger vi bare det...
4) Lav 3 lister. Een liste til elementer mindre end pivot. Een liste tli dem, der er lig med pivot, og een liste til dem der er større. Løb din liste igennem og læg elemeterne i de rigtige af de 3 lister. I dette trin kan du sætte dem ind forrest, og ikke nødvendigvis bagerst, da de i forvejen ikke er sortede.
5) Kald rekursivt på første og sidste liste, men ikke listen med pivot-elementer.
6) Når de to kald er færdige, skal du sammensætte de 3 lister tli een, og her kommer det dig til gode at du kende slutelementer i alle 3 lister. Resultatet af sammensætningen afleveres som resultat.
(ja, det er mest en skitse, men du udfylder selv detaljerne ... )
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.
