Have something to say? Contribute New Article Reply to this Article
Sorting and Searching to get rid of Duplicate Numbers
I am having a problem sorting my numbers after my binary search. Can you tell me what is wrong with my code?
#include <iostream>
#include <cstdlib>
using namespace std;
void pick_three(int p3arr[]);
void pick_four(int p4arr[]);
void lotto(int lottoarr[]);
void selection_sort(int a[], int size);
int lottobsearch(int a[], int size);
int main()
{
int choice;
int p3arr[3];
int p4arr[4];
int lottoarr[6];
cout << "Welcome to the Maryland Lottery!\n";
do
{
cout << endl
<< "Choose 1 for Pick 3.\n"
<< "Choose 2 for Pick 4.\n"
<< "Choose 3 for Lotto.\n"
<< "Choose 4 for Mega Millions.\n"
<< "Choose 5 to Exit.\n"
<< "Enter choice and press Enter: ";
cin >> choice;
switch(choice)
{
case 1:
pick_three(p3arr);
break;
case 2:
pick_four(p4arr);
break;
case 3:
lotto(lottoarr);
break;
case 5:
cout << "End of Maryland Lottery.\n";
break;
default:
cout << "Not a valid choice.\n"
<< "Choose again.\n";
}
}
while(choice != 5);
return 0;
}
void pick_three(int p3arr[])
{
const int arrsize = 3;
p3arr[arrsize];
int rand_int = 0;
int tickets;
cout << "How many tickets?:\n";
cin >> tickets;
cout << endl;
if(tickets >=1 && tickets <=5)
{
while(tickets != 0)
{
for(int i=0; i<3; i++)
{
rand_int = rand()%10;
p3arr[i] = rand_int;
selection_sort(p3arr, arrsize);
cout << p3arr[i] << endl;
}
cout << endl;
tickets = tickets - 1;
}
}
else
{
cout << "Ticket number too large.\n";
}
return;
}
void pick_four(int p4arr[])
{
const int arrsize = 4;
p4arr[arrsize];
int rand_int = 0;
int tickets;
cout << "How many tickets?:\n";
cin >> tickets;
cout << endl;
if(tickets >=1 && tickets <=5)
{
while(tickets != 0)
{
for(int i=0; i<4; i++)
{
rand_int = rand()%10;
p4arr[i] = rand_int;
selection_sort(p4arr, arrsize);
cout << p4arr[i] << endl;
}
cout << endl;
tickets = tickets - 1;
}
}
else
{
cout << "Ticket number too large.\n";
}
return;
}
void lotto(int lottoarr[])
{
const int arrsize = 6;
lottoarr[arrsize];
int rand_int = 0;
int tickets;
cout << "How many tickets?:\n";
cin >> tickets;
cout << endl;
if(tickets >=1 && tickets <=5)
{
while(tickets != 0)
{
for(int i=0; i<6; i++)
{
rand_int = rand()%49+1;
lottoarr[i] = rand_int;
selection_sort(lottoarr, arrsize);
lottobsearch(lottoarr, arrsize);
cout << lottoarr[i] << endl;
}
cout << endl;
tickets = tickets - 1;
}
}
else
{
cout << "Ticket number too large.\n";
}
return;
}
void selection_sort(int a[], int size)
{
int temp, i, j;
for(i=0; i<size; i++)
for(j=i+1; j<size; j++)
{
if (a[i] > a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
return;
}
int lottobsearch(int a[], int size)
{
for ( int i = 0; i < size; ++i)
{
a[i] = rand()%49+1;
for (int j = 0; j < i; ++j)
{
if (a[i] == a[j])
{
a[j] = a[i];
}
}
}
return 0;
}What do you mean by you are having trouble sorting your numbers after a binary search, the basis of a binary search is that the numbers are already sorted.
What do you mean by you are having trouble sorting your numbers after a binary search, the basis of a binary search is that the numbers are already sorted.
They are already suppose to be sorted then i got in for the binary search but when my output comes up they are not sorted.
Well first off in all you lotto statements you have a lottoarr[size]; which is doing absoulty nothing. I recommend that you turn on all your compiler's warnings that will help out with things like that probably complier options -> commands to compiler add the switch -Wall.
As for your problem
int lottobsearch(int a[], int size)
{
for ( int i = 0; i < size; ++i)
{
//a[i] = rand()%49+1; here is your problem
for (int j = 0; j < i; ++j)
{
if (a[i] == a[j])
{
a[j] = a[i];
}
}
}
return 0;
}Your assigning a new value to your array during your binary search which is giving you unsorted numbers. Also another thing I noticed is that you get negative numbers sometimes also
Well first off in all you lotto statements you have a lottoarr[size]; which is doing absoulty nothing. I recommend that you turn on all your compiler's warnings that will help out with things like that probably complier options -> commands to compiler add the switch -Wall. As for your problem
int lottobsearch(int a[], int size) { for ( int i = 0; i < size; ++i) { //a[i] = rand()%49+1; here is your problem for (int j = 0; j < i; ++j) { if (a[i] == a[j]) { a[j] = a[i]; } } } return 0; }Your assigning a new value to your array during your binary search which is giving you unsorted numbers. Also another thing I noticed is that you get negative numbers sometimes also
I never received a negative number, they might be my logic. What is the new value? I am trying to see what you are saying, but I don't see it at all.
Ok first you are sorting a list of numbers than when you call your search(which is really flawed btw) everytime you loop through your setting a new value to a[i] which is really lottoarr[i].
Heres a little program I whipped together for you check it out hope it will help you.
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void Sort(int numbers[], int size)
{
int i, j;
int min, temp;
//selection sort
for (i = 0; i < size-1; i++)
{
min = i;
for (j = i+1; j < size; j++)
{
if (numbers[j] < numbers[min])
{
min = j;
}
}
temp = numbers[i];
numbers[i] = numbers[min];
numbers[min] = temp;
}
}
void checkForDuplicate(int numbers[], int size)
{
int i, j;
//probably someway to make this more efficent but you get the idea
for(i = 0; i < size; i++)
{
for(j = i + 1; j < size; j++)
{
if(numbers[i] == numbers[j])
{
numbers[j] = rand() % 10;
}
}
}
}
int main(void)
{
int i;
const int size = 3;
int array[size];
srand((unsigned int)time(NULL));//makes the numbers based on time
for(i = 0; i < size; i++)
{
array[i] = rand() % 10;
}
checkForDuplicate(array,size);//call check for duplicate before you sort them
//so you don't have to sort twice
Sort(array,size);
for(i = 0; i < size; i++)
{
cout<<array[i]<<endl;
}
cin.get();
return 0;
}Heres a little program I whipped together for you check it out hope it will help you.
#include <iostream> #include <cstdlib> #include <ctime> using namespace std; void Sort(int numbers[], int size) { int i, j; int min, temp; //selection sort for (i = 0; i < size-1; i++) { min = i; for (j = i+1; j < size; j++) { if (numbers[j] < numbers[min]) { min = j; } } temp = numbers[i]; numbers[i] = numbers[min]; numbers[min] = temp; } } void checkForDuplicate(int numbers[], int size) { int i, j; //probably someway to make this more efficent but you get the idea for(i = 0; i < size; i++) { for(j = i + 1; j < size; j++) { if(numbers[i] == numbers[j]) { numbers[j] = rand() % 10; } } } } int main(void) { int i; const int size = 3; int array[size]; srand((unsigned int)time(NULL));//makes the numbers based on time for(i = 0; i < size; i++) { array[i] = rand() % 10; } checkForDuplicate(array,size);//call check for duplicate before you sort them //so you don't have to sort twice Sort(array,size); for(i = 0; i < size; i++) { cout<<array[i]<<endl; } cin.get(); return 0; }
One issue with your code, one that I am currently facing in a similar problem; the problem lies in your CheckForDuplicate().
This is my pseudocode interpretation of that function, correct me if I am wrong:
n=ordinal location of a number in a 5 number sequence (1 through length)
If int n equals int n+1, assign a new random value to n+1.
---------------
The issue with this is as follows:
say you have the number sequence generated: 5 3 7 7 9
The loop first encounters the number 5. the number following is 3. 5 != 3, so it continues. Next, 3 and 7. 3 != 7, so the loop continues. Next, 7 and 7. 7 == 7, so now the program proceeds to assign a new random value to the second 7. Say the new value is 5. OK for now, so it seems....So now having "fixed" the duplicate, it continues. we now have this sequence: 5 3 7 5 9 and we are currently on the fourth number (5). So the loop has 5 and 9. 5 != 9, so the loop continues. The LCV has now reached the termination condition, so the loop terminates, with a final sequence of 5 3 7 5 9. Unfortunately, we now have two 5's. And the loop failed to address this problem.
I am working on this same problem now more or less, and can't solve it. My wily old professor caught this error, and I can't seem to fix it. The only solution I have come up with is instead of generating a new val for the number n+1, when number n and n+1 equal each other, I restart the loop by setting i=0. This works, however as my professor says, is terribly inefficient. On today's machine's, it doesn't matter, but on the machines HE used to work on, that would mean a huge difference in processing power -_-
This article has been dead for over three months
You
© 2012 DaniWeb® LLC
