Writing a selection sort for STL list?

Question

I am writing a particular c++ program to use selection sort on an STL list as it is required by my professor.

I am using Netbeans 9.2. Currently, I got stuck with my algorithm. For the first few times, the program compiles but the list after selection always ends up with the same values(say it was supposed to be 99, 24, 15, 80, 27, it would always be 1, 1, 1, 1, 2 after the sort). Now the algorithm just straight up wouldn't compile. I am relatively new to coding. Could someone please tell me what I've gotten wrong and how I should go about it? Much thanks!

Here's my code:

void selectionSort(list<short> l, int size) {
    list<short>::iterator it1;
    list<short>::iterator it2;
    list<short>::iterator it3;
    short min, temp; 
    for(it1 = l.begin(); it1 != l.end(); it1++) {
        temp = min = *it1;
        it2 = it1;
        for(it2 = it1; it2 != l.end(); it2++) {
            if(*it2 < min) {
                min = *it2;
                it3 = it2;
            }    
        }
        *it1 = min;
        *it3 = temp;
        //Increment the first counter at the end
        temp = min = *it1;
    }
}

Probably won't fly for homework, but check out the example here for one approach to selection sort: https://en.cppreference.com/w/cpp/algorithm/iter_swap — Shawn, Jun 01 '19 at 20:25
[How to implement classic sorting algorithms in modern C++](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c/24650627). Please see the "Selection Sort" implementation. — PaulMcKenzie, Jun 01 '19 at 21:24
It would be easier to figure out what went wrong if you included the complier's error message in your question. — JaMiT, Jun 02 '19 at 01:30
Could you show us how exactly (based on what criterion) you need to sort the list? Greatest to smallest? You could have a look at quicksort: https://en.wikipedia.org/wiki/Quicksort . — borizzzzz, Jun 02 '19 at 08:52
You need to improve your question to avoid it being closed, you are far more likely to get a useful answer if your question is very clear. please review how to ask questions: https://stackoverflow.com/help/how-to-ask Newbies must be given an opportunity to improve their question https://stackoverflow.com/conduct — Martin Spamer, Jun 02 '19 at 11:43
@V.Reeve If one of the answers is correct you should accepted https://stackoverflow.com/help/someone-answers — dreamcrash, Nov 20 '20 at 09:21

score 1 · Answer 1 · answered Jun 02 '19 at 08:00

There is a bug in your code which will lead to a crash. I've fixed it in the following code.

But I still don't know why it outputs strange numbers like 1, 1, 1, 1, 2. Maybe it's caused by the rest of your code. It would be helpful if more code or information can be provided.

void selectionSort(list<short> l, int size) {
    list<short>::iterator it1;
    list<short>::iterator it2;
    list<short>::iterator it3;
    short min, temp;
    for(it1 = l.begin(); it1 != l.end(); it1++) {
        temp = min = *it1;
        it2 = it1;
        it3 = l.end();  // NOTE: to fix the bug
        for(it2 = it1; it2 != l.end(); it2++) {
            if(*it2 < min) {
                min = *it2;
                it3 = it2;
            }
        }
        if (it3 != l.end()) {  // NOTE: to fix the bug
            *it1 = min;
            *it3 = temp;
        }  // NOTE: to fix the bug
        //Increment the first counter at the end
        temp = min = *it1;  // NOTE: This is unnecessary
    }
}

To make your answer useful to a broader audience, you should include an explanation of what the bug is. — JaMiT, Jun 08 '19 at 06:14

score 0 · Answer 2 · answered Jun 02 '19 at 11:39

You're passing the parameter l by value, not by reference. That's why the manipulation you do within the function selectionSort does nothing to change the list. Here's a version that works:

#include <iostream>
#include <list>

void selectionSort(std::list<short>& l) {
  std::list<short>::iterator it1;
  std::list<short>::iterator it2;
  std::list<short>::iterator it3;
    short min, temp;
    for(it1 = l.begin(); it1 != l.end(); it1++) {
        temp = min = *it1; 
        it3 = l.end();
        for(it2 = it1; it2 != l.end(); it2++) {
            if(*it2 < min) {
                min = *it2;
                it3 = it2;
            }
        }
        if (it3 != l.end()) {
            *it1 = min;
            *it3 = temp;
        }
    }
}

int main()
{
  std::list<short> mylist= {10,1,8,13,14,7,6,5,18,9,19,12,17,15,4,2};
  selectionSort(mylist);
  std::list<short>::iterator it;
  std::cout << "elements in list\n";
  for (it = mylist.begin(); it != mylist.end(); it++) {
      std::cout << *it << std::endl;
    }
  return 0;
}

In short, you need to add an & after the type of l in the declaration of your selectionSort function.

Update

I removed the size parameter from the code because you're not using it, and really don't need it anyway.

Writing a selection sort for STL list?

2 Answers2

Update