Mise en œuvre du tri par sélection sur une liste chaînée unique

Question

Heya, je suis en train d'essayer de mettre en œuvre l'algorithme de tri par sélection sur une liste simplement chaînée, je suis conscient qu'il y a un problème dans le code mais même si ma liste contient les nombres 7 1 2 6, la sortie après l'exécution est 7777. Toute aide serait appréciée.

template
void UnOrderedLinkedList::selectionSort()
{
nodeType* loc;
nodeType* minIndex;
nodeType* temp;
temp = first;
if(temp == NULL)
    cerr<<"Impossible de trier une liste vide."<link == NULL)
    cerr<<"La liste ne contient qu'un élément donc elle est déjà triée."<link;
}
}

template
nodeType* UnOrderedLinkedList::minLocation(nodeType* first, nodeType* last)

nodeType* minIndex;
nodeType* 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;
}

Ensuite pour échanger:

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

Answer 1

De votre fonction swap :

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

Il s'agit d'un cas clair de comportement indéfini! Vous déclarez une variable locale, un pointeur, sans initialisation. Ensuite, vous utilisez directement la variable non initialisée, ce qui entraîne ledit CI. Étant donné que vous utilisez des pointeurs, vous devriez en fait être heureux que le programme n'ait pas planté.

Ici, vous n'avez pas besoin d'un pointeur ou d'un nœud car vous ne swappez pas réellement les nœuds. Tout ce dont vous avez besoin est une instance de ce que info est, et utilisez cela :

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

Answer 2

La réponse de @JoachimPileborg fonctionne bien sûr, mais notez que vous n'avez pas besoin d'écrire une fonction membre sort de votre propre liste chaînée simplement liée pour effectuer un tri par sélection.

La raison en est qu'une version générique de selection_sort (avec une complexité de O(N^2)) est déjà compatible avec n'importe quelle liste chaînée simplement liée qui expose des itérateurs avant, comme celle de la bibliothèque standard, std::forward_list:

#include     // min_element, iter_swap, is_sorted
#include       // assert
#include  // forward_list
#include    // less
#include      // cout
#include           // boolalpha
#include      // distance, next

template>
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 { 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';
}

Exemple en direct

Notez que std::forward_list implémente également sa propre fonction membre sort. Cette version - qui effectue un tri fusion en O(N log N) - ne peut pas être implémentée uniquement sur la base de l'interface publique (en fait, vous pouvez, mais avec un stockage supplémentaire en O(N) au lieu du stockage en O(1) que forward_list garantit).