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

This is a discussion on [New C++ Programmer] Dynamic Arrays - Sorting and Duplicates within the C++ Programming forums, part of the General Programming Boards category; Note that I am working on a project for class and I would just like some ideas ( NOT CODE ...

  1. #1
    Registered User
    Join Date
    Nov 2004
    Posts
    9

    Question [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
        }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,310
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    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.
    My best code is written with the delete key.

  4. #4
    Registered User
    Join Date
    Nov 2004
    Posts
    9
    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.

  5. #5
    Registered User
    Join Date
    Jul 2003
    Posts
    450
    You could consider using a set instead of an array. Sets do not allow duplicates and sort according to a predicate function.

  6. #6
    Registered User
    Join Date
    Nov 2004
    Posts
    9
    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.

  7. #7
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,793
    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.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. arrays vs lists? And containers in general!
    By clegs in forum C++ Programming
    Replies: 22
    Last Post: 12-03-2007, 01:02 PM
  2. C++ arrays, sorting
    By kylesbigdog in forum C++ Programming
    Replies: 3
    Last Post: 02-16-2003, 10:48 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21