Um eine (einfach) verkettete Liste mit C++ zu Sortieren gibt es unterschiedliche Ansätze. Ich habe die letzte Woche in einer Aufgabe im Rahmen meiner Algorithmik Vorlesung folgende Sortierungsfunktion implementiert, welche das Prinzip von Bubblesort verwendet. Achtung: Bubblesort ist ein Algorithmus, den man nicht in einer Anwendung verwenden solle. Bubblesort gehört mit eine sehr schlechte Laufzeit.
Für die verkettete Liste habe ich folgende Struktur verwendet:
struct Node {
int value;
Node* pNext;
}
Die Funktion zum Sortieren der Liste sieht wie folgt aus. Als Parameter wird die Referenz auf den Pointer welcher auf den Anfang der Liste zeigt übergeben.
void sortList(Node*& pHead) {
Node* pA = NULL;
Node* pB = NULL;
Node* pC = NULL;
Node* pE = NULL;
Node* pTmp = NULL;
while (pE != pHead->pNext) {
pC = pHead;
pA = pHead;
pB = pA->pNext;
while (pA != pE) {
if (pA->value > pB->value) {
if (pA == pHead) {
pTmp = pB->pNext;
pB->pNext = pA;
pA->pNext = pTmp;
pHead = pB;
pC = pB;
} else {
pTmp = pB->pNext;
pB->pNext = pA;
pA->pNext = pTmp;
pC->pNext = pB;
pC = pB;
}
} else {
pC = pA;
pA = pA->pNext;
}
pB = pA->pNext;
if (pB == pE)
pE = pA;
}
}
}