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.
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; } } }
prinzipiell ist eine sortieralgorithmus dank OOP sehr einfach für ziemlich alle arten von zu implementieren – ob es jetzt eine arraylist, eine matrix oder sonstwas ist. ich würde aber den selectsort empfehlen – ist in vielen fällen einfacher und schneller zu implementieren.