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

Some programmer dude · Accepted Answer · 2016-04-25 05:54:33Z

2

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;

answered Apr 25, 2016 at 5:54

Some programmer dude

411k36 gold badges420 silver badges655 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Didem Over a year ago

Joachim Thank you so much my code perfectly works now! :)

Community · Accepted Answer · 2017-05-23 12:31:13Z

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).

Collectives™ on Stack Overflow

Implementing selection sort on a singly linked list

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related