C++ vectors

[Bananapie]

I am working on a program that has me insert random integers into two vectors, and sort them using selection sort.

I was wondering if I was on the right path of trying to swap the elements in the vector.

void selectionSort(vector <int>& v)
{//begin selectionSort

int i, j, min, minat;

for (i = 0; i < (v.size() - 1); i++)
{//begin for
minat = i;
min = v.at(i);

for (j = (i+1); j < v.size(); j++)
{//begin inner for

if (min > v.at(j))
{//begin if
minat = j;
min = v.at(j);
}//end if

}//end inner for

swap (v.at(i), v.at(minat); //Vector swap

}//end for

}//end selectionSort

I use the swap() function, correct?

also, to insert random integers into the vector, I am supposed to use the random function. This is what I have

v1.push_back(srand(s1));

I am not sure if I would need a for loop for it, as I am not in charge of writing main(). Most of the program is already wrote for us, and she gave us the requirements for what we are supposed to write. She does not say insert "This many numbers", so I assume that she does that in her main program.

 

[mihir]

Ok I am having a bit trouble understanding your code.
So
"v" is a class object/instance right and at() is a function/method in the class?
Am I right?
Or if you can post more code, like the class which you have defined and etc.

 

[Bananapie]

Ok I am having a bit trouble understanding your code.
So
"v" is a class right and at() is a function/method in the class?
Am I right?
Or if you can post more code, like the class which you have defined and etc.

I am entirely lost as well. My professor wrote for the class the function main() and then gave us a paper and we are in charge of writing the other functions.

I would have much rather wrote it all... rather than the half that is in jeopardy of failing, depending what is exactly given to me in main()

"v" is the vector being passed in with the function selectionSort, and at(), is kind of like the array[(element position here)]

where .at((element position here))

Ye, I'll probably just go talk to the TA tomorrow and stress finishing the rest of the functions once I can find out how to get the code for main()

haha sorry..

 

[mihir]

OK I checked, and there is a template vector class. Sorry I did not know about it.

So "v" must be an object/instance of the class which has all these functions like at() and size() etc.

I think there is a problem with the selection sort.
in the first for loop it should be v.size() not v.size() - 1

And I am not sure whether at() will pass the address of the integer or the integer itself.
If it passes the address of the integer then the swap will work otherwise it won't.
You should swap in the loop itself and not call the function, and if that works then try the swap function

 

[Bananapie]

So I changed my selectionSort function. Take a look and see how it looks.

void selectionSort(vector <int>& v)
{//begin selectionSort


int i, j, firstE, size;
size = v.size();

for (i = size - 1; i > 0; i--)
{//begin for
firstE = 0;

for (j = 1; j <= i; j++)
{//begin inner for
if (v[j] > v[firstE])
        firstE = j;
}//end inner for

swap(v[firstE], v[i]);  //swap

}//end for

}//end selectionSort

and yeah. at() and size() work with the vector I called v. Take a look and see how it looks.

 

[Bananapie]

I am also working on the binarySearch function. Here is what I have so far.

int binarySearch(const vector <int>& v, int x, int& cnt)
{//begin binarySearch
int low, high, mid;
low = 0;  //might need changed
high = v.size();

while (low <= high)
{//begin while
mid = low + (high - low) /2; //finds the middle
if (v[mid] == x)
return mid;
else if (v[mid] < target)
{//begin else if
low = (mid+1); //changes low
cnt++;
}//end else if
else if (v[mid] > target)
{//begin else if
high = (mid-1); //changes high
cnt++;
}//end else if
else
return -1;

}//end while

}//end binarySearch

the first line declares the function binarySearch
'x' is the item being searched, in the vector v. Then cnt is the number of comparisons to finding x. If the search is unsuccessful, then it returns -1. If the search is successful, it returns the index value that you can find the searched item at.

We have to use cnt to count the comparisons, because we are running two searches in this program. Binary and Linear. She wants us to see the difference in comparisons between the two searches.

I wish I knew a fast way to compile/execute in Putty... I miss testing in Netbeans. Want to run and see what you have so far? Press F5 and it will execute. haha.

 

[mihir]

Your binary search will work fine given that you are not searching for multiple instances of an element in the vector.

About the selection sort I do not remember the algorithm properly.
But a small trial and error will work.

 

[Bananapie]

My binary search has an infinite loop.

//********************
//***binarySearch*****
//********************
int binarySearch(const vector <int>& v, int x, int& cnt)
{//begin binarySearch
int low, high, mid;
low = 1;  //might need changed
high = v.size();
mid = low + (high - low) /2;

while (low < high)
{//begin while
 //finds the middle
if (v[mid] == x)
{//begin if
cout << "The variable position that you will find " << x << " is at " <<  mid << endl << endl ;
cout << "The number of comparisons to find " << x << " was " << cnt;  //MIGHT NEED TO RETURN cnt and mid variable pos
}//end if
else if (v[mid] < x)
{//begin else if
low = (mid+1); //changes low
cnt++;
mid = low + (high - low) /2;
}//end else if
else
{//begin else if
high = (mid-1); //changes high
cnt++;
mid = low + (high - low) /2;
}//end else if

}//end while

return -1;
}//end binarySearch

 

[mihir]

Did you sorted the vector before running the binary search?

 

[Bananapie]

I did sort the vector before doing the search.

It is stuck in a loop while searching through my targets. For instance:

Target: 42 Index: 6 Comparisons: 6
Target: 42 Index: 7 Comparisons: 6

where the index goes up by 1 until 200.. and then it goes onto the next target

Target: 57 Index: etc etc
and the index goes up to 200 again.

Here is my code

//********************
//***binarySearch*****
//********************
int binarySearch(const vector <int>& v, int x, int& cnt)
{//begin binarySearch
int low, high, mid;
low = 0;  //might need changed
high = v.size();
mid = (high + low) /2;

while (low < high)
{//begin while
 //finds the middle
if (v[mid] == x)
{//begin if
cout << "Target: " << x << "    Index: " << i << "    Comparisons: " << cnt << endl << endl;

}//end if
else if (v[mid] < x)
{//begin else if
low = (mid+1); //changes low
cnt++;

}//end else if
else
{//begin else if
high = (mid-1); //changes high
cnt++;

}//end else if
}//end while

return -1;
}//end binarySearch

High is 200, which is the size of the vector in (v.size())

Not really sure what is making it just count the index up to 199 then change to the next target.

Anyone?

 

[Cromewell]

Can you explain your search function to me? I can gather that your vector is v, x is what you are looking for, but what is cnt for and why are you passing it in as a pointer?

I'm guessing your problem is where you use "v[mid]", you probably want v->at(mid) or possibly v.at(mid) depending on how pointers to the template class work.
edit: nevermind, the [] operator is overloaded to call at, you must have a logic error in your loop. If you have a debugger, step through the code and watch what happens with your variables.

 

[Bananapie]

Can you explain your search function to me? I can gather that your vector is v, x is what you are looking for, but what is cnt for and why are you passing it in as a pointer?

I'm guessing your problem is where you use "v[mid]", you probably want v->at(mid) or possibly v.at(mid) depending on how pointers to the template class work.
edit: nevermind, the [] operator is overloaded to call at, you must have a logic error in your loop. If you have a debugger, step through the code and watch what happens with your variables.

cnt is ideally to count the number of comparisons each search goes through, until it reaches the target.

void search (const vector <int>& v1, const vector <int>& v2,
    int ( *f )( const vector <int>&, int, int& ))
{
    int n = v2.size ( );
    int totalCnt = 0, totalSucCnt = 0;

    for ( int j = 0; j < n; j++ ) {
        int cnt = 0; int i = f ( v1, v2[j], cnt );
        totalCnt += cnt; if ( i >= 0 ) totalSucCnt++;
    }
    printStat ( totalCnt, totalSucCnt, v2.size ( ));
}

// Prints avg no of comparisons and percent of successful searches as
// right-aligned, floating-pt nos on stdout.

void printStat ( int totalCnt, int totalSucCnt, int vectorSz )
{
    cout << setiosflags ( ios::fixed | ios::showpoint )
         << setprecision ( 2 );

    cout << "\tAverage No of Comparisons      = "
         << setw ( 6 ) << ( float ) totalCnt / vectorSz << endl
         << "\tPercent of Successful Searches = "
         << setw ( 6 ) << 100 * ( float ) totalSucCnt / vectorSz << "%\n";
}

It takes the cnt, and then uses it in main(which I didn't write, but the professor did) to give us a reading on the Average number of comparisons each search does, and then how successful it actually was.

Here is main if it does help

int main ( )
{
    // Define two empty vectors of ints for given sizes and
    // fill them by random integers for given seed values.

    vector <int> A ( ARR_SIZE ), B ( TEST_ARR_SIZE );
    Vectors ( A, B, SEED1, SEED2 );

    // Print test (1st) vector before sorting its elements.
    cout << "Random Numbers Before Sorting:\n";
    printVectors ( A );

    // Sort test (1st) vector using selection sort algorithm.
    selectionSort ( A );

    // Print test (1st) vector after sorting its elements.
    cout << "\nRandom Numbers After Sorting:\n";
    printVectors ( A );

    // Print test values from 2nd vector.
    cout << "\nRandom Numbers Searched:\n";
    printVectors ( B );

    // Search each test value from 2nd vector in 1st vector
    // using linear search algorithm.

    cout << "\nLinear Search:\n";
    search ( A, B, linearSearch );

    // Search each test value from 2nd vector in 1st vector
    // using binary search algorithm.

    cout << "\nBinary Search:\n";
    search ( A, B, binarySearch );

    return 0;
}

Kind of the idea is to use rand with two different seed values, into the two vectors. Then sort the first vector using selection sort. Then use the linear search to search random numbers from the second vector, and get the average comparisons (I get 199.8 avg.) but the successful searches is somehow 0%, even though I trace through the list it gives and it clearly says the target, the index position and comparisons to get to it. Then binary search runs next to get the same info, but it just gives me the loop problem I mentioned previous.

ARR_SIZE = 200 and TEST_ARR_SIZE = 100 so you know.

 

[Cromewell]

Ah ok. It looked weird because you were obviously doing something with it but then your function is always returning -1.

I think your while condition is the problem, you probably want something like while(v[mid] != x && counter < ARR_SIZE) where counter is an integer variable initialized to 0. There are other ways to do it as well, you could even use a for loop with a similar exit condition. You could also do this (sets low to be greater than high once you've found your value):

//********************
//***binarySearch*****
//********************
int binarySearch(const vector <int>& v, int x, int& cnt)
{//begin binarySearch
	int low, high, mid;
	low = 0;  //might need changed
	high = v.size();
	mid = (high + low) /2;

	while (low < high)
	{//begin while
		//finds the middle
		if (v[mid] == x)
		{//begin if
			cout << "Target: " << x << "    Index: " << i << "    Comparisons: " << cnt << endl << endl;
			low = high + 1;
		}//end if
		else if (v[mid] < x)
		{//begin else if
			low = (mid+1); //changes low
			cnt++;

		}//end else if
		else
		{//begin else if
			high = (mid-1); //changes high
			cnt++;

		}//end else if
	}//end while

	return -1;
}//end binarySearch

 

[Bananapie]

Figured it out! So I practically kept the same while loop, and the infinite loop kept going and going.

So after realizing that nothing is kicking it out of the loop after it finds the target, I put a break; statement in.

if (v[middle] == x)
{
               cout << "Target: " << x << "       Index: " << middle << " $
break;
}

Works like a champ now. Not completely certain why the main function isn't giving me the total number of successful searches, but as far as I am concerned, the program she gave me that I can't change isn't my problem. I got the searches, and got the idea that the number of comparisons is drastically changed from using linear to binary search.

Thank you guys for your help. Really appreciate it. Feels so good working in C++ and getting the programs done, when the professor is Asian, not very fluent, and I have never worked with putty/linux/c++ before. :good:

 

[Cromewell]

You may get a slap on the wrist for using break but I suppose that works.

 

[Bananapie]

You may get a slap on the wrist for using break but I suppose that works.

I'm really not certain how they want things done here. I just transferred, and previously I took Java. Never heard of break being looked down upon, so I use it when I deem necessary. This case it worked fine haha.