[New C++ Programmer] Dynamic Arrays - Sorting and Duplicates

Note that I am working on a project for class and I would just like some ideas (NOT CODE) that I can use for deleting duplicates from a dynamic array containing pseudorandom numbers.

What I'm doing is allowing users to choose the range of numbers (1 through whatever they want) and how many pseudorandom numbers within that range they want to see. The array is created and filled based on this information.

Then, using sort(), the array is sorted from the least to the greatest. Which is all fine and exactly what I want.

However, here is the problem. I have no idea how to remove numbers that are duplicates or triplicates. I have developed a few lines of code to make sure that users can not force the program into a situation of returning a duplicate, but once a valid array is made, I don't know what to do.

Again, I ask that no code be given to me, but I would like some ideas as to what methods I can apply to my dynamic array. Thanks.

Code:

---

#include <iostream> //opens iostream as a standard C++ included file
#include <conio.h> //opens conio.h for use of getch() and system() commands
#include <ctime> //opens ctime for the seeding of rand() using time
#include <cstdlib> //opens cstdlib for rand() function
#include <algorithm> //opens algorithm for sort() function

using namespace std; //uses the standard C++ namespace

int main() //opens the main (and only) function
    {
        int maxnum = 0; //sets the variable "maxnum" as an integer and sets it to 0 as a reset
        int numofnums = 0; //sets the variable "numofnums" as an integer and sets it to 0 as a reset
        int watcher = 0; //sets the variable "watcher" as in integer and sets it to 0 as a reset
        int endopt = 0; //sets the variable "endopt" as in integer and sets it to 0 as a reset
        int i;

        srand(time(0)); //seeds rand() by using the system time; exact outcome is based on OS

        cout << "Welcome to the Random Number Generator." << endl;
        cout << "Press any key to continue." << endl;
        getch(); //pauses the program until the user hits any key
        system("cls"); //a system call to clear the screen

        do //initial do...while loop allowing for the repetition of the entire program
              {
                  do
                        {
                            cout << "Enter the maximum number to be returned." << endl;
                            cout << "This number must be bigger than the number of times you want to return a random number." << endl;
                            cout << "This number is the highest possible random number." << endl;
                            cin >> maxnum; //this stores a user input as the highest number to be returned

                            while (maxnum <= 0) //executes lines 32 through 36 if maxnum is 0 or a negative number
                                  {
                                      system("cls"); //a system call to clear the screen
                                      cout << "You entered an invalid maximum number." << endl;
                                      cout << "The maximum number must be greater than 0." << endl;
                                      cout << "Please try again. Enter the maximum number to be returned." << endl;
                                      cin >> maxnum;
                                  }

                            system("cls"); //a system call to clear the screen
                            cout << "Enter the number of random numbers you want to be returned." << endl;
                            cout << "This number must be smaller than the highest number in the range of random numbers." << endl;
                            cout << "This number is the total number of numbers that you will see." << endl;
                            cin >> numofnums;

                            while (numofnums <= 0) //executes lines 46 through 50 if numofnums is 0 or a negative number
                                  {
                                        system("cls"); //a system call to clear the screen
                                        cout << "You entered an invalid total number of numbers to display." << endl;
                                        cout << "At least 1 number must be displayed." << endl;
                                        cout << "Please try again. Enter the number of times to return a random number." << endl;
                                        cin >> numofnums;

                                        system("cls"); //a system call to clear the screen
                                  }

                            system("cls"); //a system call to clear the screen
                        }
                  while (numofnums <= maxnum);

                  int* array = new int[numofnums]; //allocates memory for the array

                  for (i = 0; i < numofnums; i++) //sets the parameters for the array
                        array[i] = ((rand() % maxnum) + 1); //loads the array

                  sort(array, array+numofnums); //sorts the array

                  int* array2 = new int[numofnums]; //allocates memory for a second array

                  array[i] = array2[i]; //sers the original array equal to another array named "array2"

                 

                  for (i = 0; i < numofnums; i++)
                        cout << "\n" << array[i]; //outputs the array

                  cout << "\n"; //a new line
                  cout << "Enter 1 to start again or 2 to quit." << endl;
                  cin >> endopt;
                  system("cls"); //a system call to clear the screen

                        while (endopt != 1 && endopt != 2)
                            {
                                  cout << "\n"; //a new line
                                  cout << "You did not enter 1 or 2." << endl;
                                  cout << "Enter 1 to start again or 2 to quit." << endl;
                                  cin >> endopt;
                            }
              }
        while (endopt == 1); //this ends the main do...while loop that wraps the entire program

        return(0); //closes main() and ends the program
    }

---

You could use another dynamic array, and so iterate over the existing array, placing elements in this new array.
Before an element is pushed onto this new array, you search this new array for the value, and only add if it is not found.

Another way would be to use a version of insertion sort and place unique elements into position in this new array, ignoring duplicates.

If you want to do it in place, then perhaps you could iterate over the array, and for each element search the subsequent elements for duplicates and remove them.

Assuming the range to be relatively small, you can create a dynamic array of [0..N) and shuffle the first k numbers using your random number generator:

Code:

---

N = get_number()
k = get_number()

a = new number[N]

# Fill a with [0..N)
for i = 0 to N
  a[i] = i

# Shuffle the first k numbers in a
for i = 0 to k
  r = random ( i, N - 1 )
  swap ( a[i], a[r] )

# Sort the first k numbers in a
sort ( a, k )

---

If the range is to large for a practical array then you need to either avoid inserting duplicates, or remove the duplicates after sorting. Removing duplicates from a sorted sequence is fairly easy, but unless you use a second array to hold the result it can get expensive to shift elements around.

Avoiding duplicates at the point of insertion is also somewhat expensive with arrays because you need to perform a linear search to see if the number is already in the array. If you make sure that the array is sorted at all times you can use a binary search, but then you have the overhead of maintaining a sorted array.

If the first solution isn't practical then I would recommend rethinking your data structure. A binary search tree would be better by leaps and bounds. You save yourself the sorting step because binary search trees are always sorted, and you can easily tell a tree insertion routine to ignore duplicates.

Actually, I think that preventing the insertation of duplicates is the method I want to go with. Although I'm sure most people would use a smaller amount of numbers with a large range, I do want my program to be safe to use with some really wacky ranges and amounts of random numbers. I'll look into that. Thanks.

You could consider using a set instead of an array. Sets do not allow duplicates and sort according to a predicate function.

Quote:

---

Originally Posted by curlious

You could consider using a set instead of an array. Sets do not allow duplicates and sort according to a predicate function.

---

Hmmm. That sounds like exactly what I want.

There is a function in the algorithm header called unique which will remove duplicate entries for a container (i.e. array, vector, list). The container needs to be sorted first, which you've already done using the sort function, so that part is done.