Sorting and Searching to get rid of Duplicate Numbers

Question

blackbabydoll 0 Newbie Poster

21 Years Ago

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;
}

c++

3 Contributors
11 Replies
229 Views
3 Years Discussion Span
Latest Post 18 Years Ago Latest Post by AlephOne

Dani AI

Generated 7 Months Ago

The root causes here are: (1) generating or changing random values while “searching” (so the array keeps getting mutated), (2) sorting inside the inner loop for each new element (costly and confusing), and (3) using ad‑hoc duplicate-fixing that can introduce new duplicates (exactly what pointed out). correctly spotted that the search function should not be assigning new random values into the array — generate the ticket first, ensure uniqueness, then sort once, then search if needed.

Two reliable patterns to produce N unique numbers in a range:

Shuffle a pool: build 1..M, shuffle, take first N and sort. This is simple, deterministic in cost, and perfect for lotteries (M small).
Set-based: repeatedly draw a random candidate and insert only if not already present (use std::unordered_set), stop when you have N, then copy into a vector and sort. This avoids the “replace and continue” bug that can leave unseen duplicates.

Example (modern C++, concise and safe — use instead of modifying the array inside a search):

#include <vector>
#include <algorithm>
#include <random>
#include <numeric>

// produce N unique numbers in [minv,maxv], sorted
std::vector<int> generate_unique(int N, int minv, int maxv) {
  std::vector<int> pool(maxv - minv + 1);
  std::iota(pool.begin(), pool.end(), minv);
  std::random_device rd;
  std::mt19937 g(rd());
  std::shuffle(pool.begin(), pool.end(), g);
  pool.resize(N);
  std::sort(pool.begin(), pool.end());
  return pool;
}

Practical tips: seed RNG once (or prefer <random> as above), do not call your sort routine for every inserted element — sort once after the ticket is complete, and never reassign array values inside a search routine. If you must check duplicates after generation, use a set or loop that compares the candidate to previously accepted values before inserting (not after).

All 11 Replies

prog-bman 4 Junior Poster

21 Years Ago

http://www.daniweb.com/techtalkforums/announcement.php?f=8&announcementid=3

prog-bman 4 Junior Poster

21 Years Ago

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.

prog-bman 4 Junior Poster

21 Years Ago

Well first off in all you lotto statements you have a lottoarr; 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

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

blackbabydoll 0 Newbie Poster · Answer 1 · 2004-12-15T12:21:30+00:00

blackbabydoll 0 Newbie Poster

21 Years Ago

thanks. i didnt' know.

blackbabydoll 0 Newbie Poster · Answer 2 · 2004-12-15T12:24:10+00:00

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.

blackbabydoll 0 Newbie Poster · Answer 3 · 2004-12-15T12:40:31+00:00

Well first off in all you lotto statements you have a lottoarr; 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.

prog-bman 4 Junior Poster · Answer 4 · 2004-12-15T12:46:01+00:00

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 which is really lottoarr.

prog-bman 4 Junior Poster · Answer 5 · 2004-12-15T13:09:36+00:00

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;
  
}

blackbabydoll 0 Newbie Poster · Answer 6 · 2004-12-15T13:12:31+00:00

thanks! that helped me very much with my sort. I really appreciate it.

prog-bman 4 Junior Poster · Answer 7 · 2004-12-15T15:42:50+00:00

prog-bman 4 Junior Poster

21 Years Ago

You are welcome, anytime

AlephOne 0 Newbie Poster · Answer 8 · 2008-01-03T10:37:10+00:00

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 -_-

Sorting and Searching to get rid of Duplicate Numbers

Dani AI

Recommended Answers Collapse Answers

All 11 Replies

Recommended Answers