selection algorithm with vectors

[JayGln]

Good afternoon,
I am trying to do a sorting algorithm using vectors. I am trying to let the user input any number positive or negative. then once they enter any character it is supposed to exit, sort and print out the sorted list. The problem is that it doesn't sort the list. I did a successful program using arrays but using a vector i'm having difficulty. Any advice would be great just to get back on track.

#include <iostream>
#include <vector>

using namespace std;

//selection algortithm with a vector
void SelectionSort (vector<int> myVector, int sizeOfVect)//vector<int> sizeOfVector)
{
    for (unsigned int i = 0; i < sizeOfVect - 1; i++)
    {
        int vectMin = i;
        for (int j = i + 1; j < sizeOfVect; j++)
        {
            if(myVector[j] < myVector[vectMin])
            {
                vectMin = j;
            }
        }
        int temp = myVector[i];
        myVector[i] = myVector[vectMin];
        myVector[vectMin] = temp;
    }
}

int main()
{

    vector <int> unSortedVector;
    int sizeOfVect;
    int vectElement;



    //myVector.push_back(4);

    //enter the integers in the vector

        cout << "Enter an integer into the vector to be sorted " << endl;
        while (cin >> vectElement)
        {
            unSortedVector.push_back(vectElement);
            cout << "would you like to enter more numbers \n"
                << "enter any non integer character " << endl ;

             //unSortedVector.push_back(vectElement);
        }

    sizeOfVect = unSortedVector.size();

    SelectionSort(unSortedVector, sizeOfVect);

    for (int i = 0; i < sizeOfVect; i++)
    {

        cout << unSortedVector[i] << " " << "i is " << i << endl;
    }

    return 0;
}

[tpb]

You are passing a copy of the vector, then sorting that local copy in the sort function. Try passing it by reference instead. BTW, sizeOfVect is worse than pointless. Just use vect.size().

#include <iostream>
#include <vector>
using namespace std;

void SelectionSort(vector<int> &v) {
    for (size_t i = 0; i < v.size() - 1; i++) {
        size_t min = i;
        for (size_t j = i + 1; j < v.size(); j++)
            if (v[j] < v[min])
                min = j;
        int t = v[i];
        v[i] = v[min];
        v[min] = t;
    }
}

int main() {
    vector<int> v;

    int n = 0;
    while (true) {
        cout << "Enter an integer: ";
        if (!(cin >> n)) break;
        v.push_back(n);
    }

    SelectionSort(v);

    for (size_t i = 0; i < v.size(); i++)
        cout << v[i] << '\n';
}

[JayGln]

That worked great thank you very much. I see how the sizeOfVect is not needed now, I haven't truly grasped vectors and sorting algorithms yet. I do have another question if you don't mind and just to see if i'm on the right track or if there is an easier way to approach the problem. I am trying to print out the smallest positive integer that is not included in the array. I was going to make another vector to compare with positive integers, once the loop hits a number that is not in the test vector. I would then print out that integer, am I on the right track thinking that way? Thank you for your help

[jonnin]

yes, you can sort it, find the first positive value, and then start looking for a gap (if the first one is not 1, you found it, so you can just look for 1 to initialize ). Remember that you might have repeated values, such as 0,0,0,1,1,2,4 and it has to come up with 3.

[tpb]

If I understand you I don't think you need another vector. Just a counting loop starting at 1 to compare to the sorted vector. There's faster ways to do it (such as faster sorts) but it depends on what exactly you need. If you describe exactly what you are trying to do someone might be able to give a better solution.

[jonnin]

right. you don't need a vector.
find the 1 (if not there, answer is 1).
look for 1 or 2 in the next location. if its 1, move on. If its 2, increment look for to 3 and move on. If its anything else, answer is 2. Repeat this idea until you find the missing value.

How you sort aside, there may be ways to do it without sorting for specific problems, but the general problem you describe, I think this is as good as it gets (you can cheat and roll the gap finder into your sort code, but that is rather complex for this discussion and not generally useful since you wouldn't write your own sort in general.. and it does not work on the better sorting algorithms as easily as it does for the N*N sorts which leave a partially sorted list you can look at after each iteration )

[JayGln]

Thank you everyone, I am attempting a problem that I haven't fully learned, I saw this problem and my professor gave me his data abstraction and problem solving with c++ book and said to look at selection sort. I just finished basic c++, and never learned vectors so I guess this just might be outside my scope right now.

This was the original question I was trying to answer:

Write a function:

int solution(vector<int> &A);

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];
each element of array A is an integer within the range [−1,000,000..1,000,000].

[jonnin]

give it a try. Vectors are virtually identical to arrays at their most basic level.
vector<int> v(1000);
is the same as
int v[1000];
as a starting point. The vector has a LOT of other stuff going on (it can have a variable size, its size can change, it has a couple dozen algorithms built into it like sorting, and more) that you can ignore for this problem.

you can substitute the vector where you had an array the rest of the code is the same; you can access the vector with v[index] just like an array.

--------------------------------------------
the constraint on A makes it possible to use another algorithm. its a little big but modern PC can handle it.
vector<bool> wow(1000001,false); //holds one used or not used token for positive values.
for(all the values in your array)
if value > 0
wow[value] = true;

int i = 1;
while(wow[i++]); //the missing integer is either i or i-1, Im trying to multitask at work and having a senior moment thinking it through.

so it marked every value you had in your data that was positive as 'have it' then looks through every possible value to find the first unmarked value, that is your missing one. You don't need to sort the data for this, it works without it. If the user types in the values, you don't even need the array of values, you can just do this directly off the user's input.