Implementing selection sort on a singly linked list

Question

Heya I'm trying to implement selection sort algorithm on a singly linked list , I'm aware that there is some problem in the code but although My linked list includes the numbers 7 1 2 6 the output after running is 7777 . Any help would be appreciated.

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;
}

Then to swap:

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;
}

score 2 · Answer 1 · answered Apr 25 '16 at 05:54

From your swap function:

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

That is a clear case of undefined behavior! You declare a local variable, a pointer, without initialization. Then you directly uses the uninitialized variable, leading to said UB. Since you use pointers, you should actually be happy that the program didn't crash.

Here you don't need a pointer or a node as you don't actually swap nodes. All you need is an instance of what info is, and use that:

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

Joachim Thank you so much my code perfectly works now! :) – Didem Apr 25 '16 at 05:58 — Didem, Apr 25 '16 at 05:58

score 1 · Answer 2 · edited May 23 '17 at 12:31

The answer by @JoachimPileborg works of course, but note that you don't need to write a member function sort of your own singly linked list in order to do selection sort.

The reason is that a generic version of selection_sort (with O(N^2) complexity) is already compatible any singly linked list that exposes forward iterators, such as the one from the Standard Library, std::forward_list:

#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

Note that std::forward_list also implements its own member function sort. This version -which does an O(N log N) merge sort- can not be implemented based on the public interface alone (actually you can, but with O(N) extra storage instead of the O(1) storage that forward_list guarantees).

Implementing selection sort on a singly linked list

2 Answers2