Implementieren Auswahl sortieren auf einer einfach verknüpften Liste

Question

Heya Ich versuche, Auswahl Sortieralgorithmus auf einer einfach verknüpften Liste zu implementieren, ich bin mir bewusst, dass es ein Problem im Code ist, aber obwohl Meine verkettete Liste enthält die Nummern 7 1 2 6 Die Ausgabe nach dem Ausführen ist 7777. Jede Hilfe wäre willkommen.

template<class Type> 
void UnOrderedLinkedList<Type>::selectionSort() 
{ 
nodeType<Type>* loc; 
nodeType<Type>* minIndex; 
nodeType<Type>* temp; 
temp = first; 
if(temp == NULL) 
    cerr<<"Cannot sort an empty list."<<endl; 
else 
    if(temp->link == NULL) 
    cerr<<"List has only one item so it is already sorted."<<endl; 
else 

while(temp != NULL) 
{ 
    minIndex = minLocation(temp, last); 
    swap(temp, minIndex); 
    temp = temp->link; 
} 
} 


template<class Type> 
nodeType<Type>* UnOrderedLinkedList<Type>::minLocation(nodeType<Type>* first, nodeType<Type>* last) 

nodeType<Type>* minIndex; 
nodeType<Type>* other; 

minIndex = first; 
other = minIndex->link; 

while(other != NULL) 
{ 
    if(minIndex->info > other->info) 
    { 
     minIndex = other; 
     other = other->link; 
    } 

    else 
    { 
     other = other->link; 
    } 

} 
    return minIndex; 
} 

Dann zu tauschen:

template<class Type> 
void UnOrderedLinkedList<Type>::swap(nodeType<Type>* first, nodeType<Type>* second) 
{ 
    nodeType<Type>* temp; 
    temp->info = first->info; 
    first->info = second->info; 
    second->info = temp->info; 
} 

Answer 1

Von Ihrer swap Funktion:

nodeType<Type>* temp; 
temp->info = first->info; 

Das ist ein klarer Fall von undefinierten Verhalten ist! Sie deklarieren eine lokale Variable, einen Zeiger, ohne Initialisierung. Dann verwenden Sie direkt die nicht initialisierte Variable, die zu besagtem UB führt. Da Sie Zeiger verwenden, sollten Sie eigentlich froh sein, dass das Programm nicht abstürzte.

Hier benötigen Sie keinen Zeiger oder Knoten, da Sie Knoten nicht wirklich tauschen. dass alles, was Sie brauchen, ist ein Beispiel von dem, was info ist, und verwenden:

SomeType temp; 
temp = first->info; 
first->info = second->info; 
second->info = temp; 

Answer 2

Die Antwort von @JoachimPileborg Arbeiten natürlich, aber beachten Sie, dass Sie nicht über eine Memberfunktion sort der eigenen einzeln verknüpft schreiben müssen Liste, um die Auswahl zu sortieren.

Der Grund dafür ist, dass ein generic version von selection_sort (mit O(N^2) Komplexität) ist bereits kompatibel jede einzeln verknüpfte Liste, die vorwärts Iteratoren, wie die aus der Standard-Bibliothek, std::forward_list aussetzt:

#include <algorithm> // min_element, iter_swap, is_sorted 
#include <cassert>  // assert 
#include <forward_list> // forward_list 
#include <functional> // less 
#include <iostream>  // cout 
#include <ios>   // boolalpha 
#include <iterator>  // distance, next 

template<class FwdIt, class Compare = std::less<>> 
void selection_sort(FwdIt first, FwdIt last, Compare cmp = Compare{}) 
{ 
    for (auto it = first; it != last; ++it) { 
     auto const selection = std::min_element(it, last, cmp); 
     std::iter_swap(selection, it); 
     assert(std::is_sorted(first, std::next(it), cmp)); 
    } 
} 

int main() 
{ 
    auto fl = std::forward_list<int> { 2, 4, 1, 0, -1, 8, 2 }; 
    std::cout << std::boolalpha << std::is_sorted(fl.begin(), fl.end()) << '\n'; 
    for (auto const& e : fl) std::cout << e << ", "; std::cout << '\n'; 
    selection_sort(fl.begin(), fl.end()); 
    std::cout << std::boolalpha << std::is_sorted(fl.begin(), fl.end()) << '\n'; 
    for (auto const& e : fl) std::cout << e << ", "; std::cout << '\n'; 
} 

Live Example

Beachten Sie, dass std::forward_list auch eine eigene Elementfunktion sort implementiert. Diese Version - die eine O(N log N) Merge Sortierung - kann nicht basierend auf der öffentlichen Schnittstelle allein implementiert werden (eigentlich können Sie, aber mit O(N) zusätzlichen Speicher anstelle der O(1) Speicher, die forward_list garantiert).