1

I'm trying to demonstrate an Insertion sort on a STL list for class I'm in. I'm running into an issue where the second expression of the while loop is never true, so the inner loop doesn't run. Should I be decrementing the iterator in a different way? I'm seeding a test list with random values but the function doesn't swap any values. "front" and "end" will be passed in with the values myList.begin() and myList.end().

template <typename dT>
void ListSort(list<dT>& lis, typename list<dT>::iterator front, typename list<dT>::iterator end) {
    auto start = ++front;
    for (; start != end; start++) {
        auto curr = start;
        while (curr != front && *curr < *(curr--)) {
            swap(*curr, *(curr--));
            curr--;
        }
    }
}
kfly2fly
  • 25
  • 4
  • [How to implement classic sorting algorithms using modern C++](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c). Look at the insertion sort implementation -- compare it with yours. – PaulMcKenzie Oct 06 '21 at 03:31
  • 1
    You're decrementing `curr` *three* times when swapping, which can't possibly be correct. It looks like the code was translated from a random-access iterator solution that used `curr - 1`. – molbdnilo Oct 06 '21 at 05:01
  • 2
    If it didn't have undefined behaviour, and it was evaluated left-to-right, `*curr < *(curr--)` would compare `*curr` to `*curr`. (This is probably what's happening in reality.) You're looking for `std::prev(curr)` – molbdnilo Oct 06 '21 at 05:05

0 Answers0