Insertion sort on vector

Question

I want to do insertion sort on a vector using vector::begin and vector::end. This is my code:

#include <iostream>
#include <vector>

using namespace std;

//Checking if vector is sorted
bool isSorted(vector<int>::iterator x, vector<int>::iterator y) {
    for (vector<int>::iterator it = x; it != y; ++it) {
        if (*x > *it) return false;
    }

    return true;
}

//Doing insertion sort algorithm
void insertionSort(vector<int>::iterator x, vector<int>::iterator y) {
    while(!isSorted(x, y)) {
        int smallest = *x;
        int* pointer;
        for (vector<int>::iterator it = x; it != y; ++it) {
            if (*it < smallest) {
                smallest = *it;
                *pointer = *it;
            }
        }


        int buffer = *x;
        *x = smallest;
        *pointer = buffer; 
    }
}

int main() {
    vector<int> list;
    list.push_back(5);
    list.push_back(3);
    list.push_back(4);
    list.push_back(0);
    list.push_back(10);
    list.push_back(1);

    //Displaying
    for (int i = 0; i < list.size(); i++) {
        cout << list[i] << endl;
    }

    insertionSort(list.begin(), list.end());

    //Displaying after sort
    cout << "\nafter sort" << endl;
    for (int i = 0; i < list.size(); i++) {
        cout << list[i] << endl;
    }
}

And this is the output:

5
3
4
0
10
1

 after sort
0
3
4
0
10
1

Expected output of after sort: 0,0,1,3,4,10. The insertion sort ain't working as expected. In the function insertionSort() I want to iterate until smallest element found, if found place that one on the first index in place.

I guess the problem is occurs somewhere on line 28, however I can't figure out what the problem is because the pointers etc make it somewhat complex.

[How to implement classic sorting algorithms in modern C++](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c) and look for "Insertion Sort". — PaulMcKenzie, Nov 15 '17 at 15:01
@PaulMcKenzie Those algorithms are all for normal vectors and arrays; they don't include the complication with only having vector::begin and vector::end — O'Niel, Nov 15 '17 at 19:34
@O'Niel -- I don't understand what the issue is. Those algorithms work for any sequence container. Did you read the article carefully? What are the first two arguments to those functions? Aren't they `begin()` and `end()`? — PaulMcKenzie, Nov 15 '17 at 19:46
@PaulMcKenzie I can't do arr[index]; I can't ask any index in my code, look, I only have ::begin and end::, I don't give my vector in any parameter — O'Niel, Nov 15 '17 at 19:49
@O'Niel -- Please look again. *The first two parameters of `insertion_sort` are the being() and end() iterators*. No different than the code you have now. If you need to be convinced, [here is your code using insertion_sort](https://www.ideone.com/p8eTDe) — PaulMcKenzie, Nov 15 '17 at 19:53
@PaulMcKenzie But that makes use of built in algorithms. It's for learning purposes so I want to do it myself — O'Niel, Nov 15 '17 at 20:15
@O'Niel -- Also, most algorithms are written to take iterators, not entire containers. That same `insertion_sort` would work for a `std::deque` and any other sequence container that has forward iterators. [Same code using std::deque](https://www.ideone.com/LahH0A) — PaulMcKenzie, Nov 15 '17 at 20:17

score 0 · Answer 1 · answered Nov 15 '17 at 22:38

Just a few notes. First, as @appleapple suggested, your implementation of isSorted is incorrect, because you are comparing only the first element with each other element of the array. (i.e. if the first element is smaller then all the others, you consider the array as sorted).

At line 19

int *pointer;

this pointer is not initialized, and would be better to initialize it pointing it to some element of the array.

At line 23

*pointer = *it;

Here you are assigning the value pointed to by it to the address pointed to by pointer. However, this means that if pointer was uninitialized, you may crash the application. If it was initialized, you'll override the value of the array pointed to by pointer.

I guess what you are trying to do is to have pointer point at the same address as the iterator.

In that case you can replace the line with

pointer = &(*it);

Finally, I think you are missing one loop, since every time you loop you take the global minimum as the current minimum, while you should slide forward in the vector at each new minimum.

The problem is at the line

int smallest = *x;

You should have another loop between the while and this line, so that at each loop, you can set the smallest to the first non-sorted element, instead of the first element of the array.

Insertion sort on vector

1 Answers1