Hejsan..
Jag har läst in en txt-fil till en länkad lista, tänkte nu sortera denna lista genom nästlade for-loopar (bubble-sort), tycker det är lite krångligt att få till. Någon som har en lösning / tips eller en bättre idé???

Tack på förhand
/ Uffe

Tja bubblesort är väl typ den enklaste sorteringsalgoritm som finns så
tycker du den är jobbig att få till. Så lär du få mer problem med
QuickSort, Radix Sort, Heap Sort eller Merge Sort.

En Bubblesort är dessutom en kass algoritm då du har O(n^2) Ordo n
kvadrat. Vilket betyder att tiden det tar att sortera ökar i kvadrat med
antalet ingående element.

Men du har ju en länkad lista som du fyller med data från en textfil..

JAG skulle göra så att jag sorterade den när jag fyller den.

Först sätter du in den första noden
Nästa nod hamnar före eller efter denna
Nästa nod hamnar först i mitten eller sist..

Det enda som måst till är en funktion som klara av detta. Sedan
beroende på om din lista är dubbelklänkad eller inte så kanske du
måste använda dig av flera pekare när du traverserar din lista.

Men här kommer lite pseudokod som du kan omsätta i c++ kod om
du vill.

Det första exemplet är om du har en enkellänkad lsista. Det vill säga
dina noder har endast en pekare till nästa element i listan. pekare
till föregående element saknas.

// Skicka in data samt pekare till listan
int insertSorted(STRUCT data, STRUCT * lista) {
STRUCT * current; //Pekare för att traversera listan
STRUCT * last; //Pekare på föregående element
current = lista; //Peka på headnoden
repeat
if (data.data > lista.data) {
//Data skall inte in på denna plats
current==current.nextnode;
last==current;
}
else {
//Stoppa in datat i listan
data.nextnode == current.nextnode; //Sätt pekare
last.nextnode == data; //Sätt pekare
Return (SUCCESS);
}

until (current.nextnode == NULL);
}


Nja syntaxen kanske inte är korrekt, det var ett tag sedan jag sysslade
med C/C++ men hoppas du förstår prinipipen. Nu skall du få en sorterad
länkad lista.

WorstCase Scenario är ju att noderna i textfilen ligger i omvänd sorterad ordning, då får du en i alla fall en ordo n^2, men du har
sparat tiden det tog att först läsa in filen.

BestCase Scenario är att textfilen är sorterad då får du en linjär historia

Räkna med att det ligger nånstans mitt i melllan.... O((n^2-n)/2) alltså tror jag det blir, ej säker dock om det är så.

Men har du mycket element i din lista... Kan det i alla fall vara id'e att satsa på en MergeSort... Ta den framför QuickSOrt..

Dessa algortimer tillämpar något som heter Divide and Conquer, Som
betyder typ Dela och Härska. I princip går det ut på att... Tänka att du
har en textsträ'ng du vill sortera. "hujkli" med mergesort delas
strängen i två lika delar "huj","kli" proceduren upprepas med "huj"
till "h","uj" nu uppträder något väldigt intressant. en sträng med ett
tecken är ju rätt sorterad redan eller hur....!!!!. Nu är det den andra
grenens tur... "uj" -> "u","j" och nu sorteras dessa löv. när de på väg
upp ur rekursionen skall slås ihop till en sträng igen så sker ju givetvis
detta i föräldranoden... SOm redan innehåller det sorterade h:et.. Nu
kommer det sorterade u:et och j:et dit och dessa sätts ihop till "hju", nu
fortsätter traverseringen av det binärträd som skapas och när vi
kommer tillbaka till rootnoden har vi en sorterad sträng "hijklu".
Tiden det tar blir logaritmisk, mer eller mindre. O(log n) Alltså som för
ett binärträd. Tag en lista med 256 noder log(2) 256 = 8 jämför detta
med en bubblesort där vi har O(n^2) = 256*256 = jävlit mycket mer
än log(2) 256.

Nu har jag svävat ut hoppas jag hjälpt dig bara.

Köp boken Algoritmer och Datastrukturer av Kruse... Den har allt du
vill veta om enklare algoritmer som MergeSort och Sånt. AVL-träd mm.

/peterh