sorting array and removing duplicates

[alsz]

Hi everyone

I am writing a program to sort an array, but I have a problem removing the duplicates ... so can someone please point me to the right direction or show me a sample program based on my code.

for example, the user gives in a row the following values:
1 3 2 7 5 9 7 -1 5 7 3 -1
Then the output should be:
1
1 3
1 2 3
1 2 3 7
1 2 3 5 7
1 2 3 5 7 9
1 2 3 5 7 7 9
1 2 3 5 6 7 7 9
1 2 3 6 7 7 9
1 2 3 6 7 9
1 2 6 7 9
2 6 7 9

best regards, alsz.

My code is below

#include <iostream>

using namespace std;

const int sizeofarray = 16;

class SortedArray
{
   public:
   SortedArray();
   void insert(int);
   void remove(int);
   void print();

   private:
   int *sortedArray;
   int size;
   int totalSize;
};

SortedArray::SortedArray()
{
   size = 0;
   totalSize = sizeofarray;
   sortedArray = new int[totalSize];
}

void SortedArray::insert(int inp)
{
   int i;
   size++;
   if (size == totalSize)
   {
      totalSize += sizeofarray;
      int *temp = new int[totalSize];
      if (sortedArray != '\0')
      {
         for (i=0; i<(size-1) && inp > sortedArray[i]; i++)
         {
            temp[i] = sortedArray[i];
         }

         if (i < (size - 1))
         {
            temp[i] = inp;
            for ( i++; i < size; i++)
            {
               temp[i] = sortedArray[i - 1];
            }
         }

         else
         {
            temp[size - 1] = inp;
         }
         delete[] sortedArray;
      }
      sortedArray = temp;
    }

    else
    {
       for ( i = size - 1; i > 0 && inp < sortedArray[i - 1]; i--)
       {
          sortedArray[i] = sortedArray[i-1];
       }
       sortedArray[i] = inp;
    }
}

void SortedArray::remove(int inp)
{
int i;
   size;
   if (size == totalSize)
   {
      totalSize += sizeofarray;
      int *temp = new int[totalSize];
      if (sortedArray != '\0')
      {
         for (i=0; i<(size-1) && inp > sortedArray[i]; i++)
         {
            temp[i] = sortedArray[i];
         }

         if (i < (size - 1))
         {
            temp[i] = sortedArray[i - 1];
         }
         }
         }
}

void SortedArray::print()
{
   for(int i=0; i<size; i++)
   {
      cout << sortedArray[i] << " ";
   }
   cout << endl;
}



int main()
{
   SortedArray x;
   int inp;
   cin >> inp;

   do
   {
      x.insert(inp);
      x.print();
      cin >> inp;
   }while(inp>=0);

   do
   {
      cin >> inp;
      x.remove(inp);
      x.print();
   }while(inp>=0);

   system("PAUSE");
   return 0;
}

[VernonDozier]

1
1 3
1 2 3
1 2 3 7
1 2 3 5 7
1 2 3 5 7 9
1 2 3 5 7 7 9

Makes sense up to here

1 2 3 6 7 7 9
1 2 3 6 7 9
1 2 6 7 9
2 6 7 9

You lost me here. Why is this list getting smaller and what about the rest of the numbers. If this is debugging input, say so and explain what the output represents. You seem to have stopped at -1. Why? I don't want to have to read through the code to find out why.

As for not inserting duplicates, if this is an insertion sort (and if it is not an insertion sort, turn it into one or give a reason whyu it isn't), simply do not insert if the element already exists. Easy to do in an insertion sort.

Reading your code code I see that -1 serves as a sentinel. You have hard-coded the duplicates in there for some reason. Why? They should have never been introdtroduced into the list in the first place, correct?

[alsz]

hi vernon

how are you doing and to explain what i am doing I guess I will just show you what I am asked to do.

you will create your own class called SortedArray. This class is
like a common array with one major difference: the array that you have must at all
times be sorted.
As an example, assume that you start off an array (initially empty) and you add
number 2 to it. Then your array looks like this:
2
After that if you add 5 to it, you would have
2->5
Assume now that you want to input number 3. The array now should be:
2->3->5
For this project, you only need to write the class. The main is given to you in the
following section along with the output your program should produce.

Notice that inside main we have 3 major methods (plus the constructor). The
insert(int) method inserts the argument in the correct place. The remove(int)
methods removes the argument if it is in the list, otherwise leaves the array as is.
Last the print() method prints out the array as is at each time.

Also notice that we have two overloaded operators: the + and the – operators. The +
one is doing exactly the same job as the insert whule the – the same things as the
remove.
MAIN

int main(){
SortedArray x;
int inp;
cin >> inp;
do{
x.insert(inp);
x.print();
cin >> inp;
}while(inp>=0);
x+6;
x.print();
do{
cin >> inp;
x.remove(inp);
x.print();
}while(inp>=0);
x-1;
x.print();
return 0;
}

OUTPUT
Assume that the user gives in a row the following values:
1 3 2 7 5 9 7 -1 5 7 3 -1
Then the output should be:
1
1 3
1 2 3
1 2 3 7
1 2 3 5 7
1 2 3 5 7 9
1 2 3 5 7 7 9
1 2 3 5 6 7 7 9
1 2 3 6 7 7 9
1 2 3 6 7 9
1 2 6 7 9
2 6 7 9

[VernonDozier]

but I have a problem removing the duplicates

From the output, it seems like duplicates are allowed. So what precisely is the problem? You need to give the input, give the actual output, then give the correct output, then point out how the actual output differs from the corect output.

[alsz]

ok i guess i should be more explicit. I can output the first part of the program no problem

so from

1
1 3
1 2 3
1 2 3 7
1 2 3 5 7
1 2 3 5 7 9
1 2 3 5 7 7 9
1 2 3 5 6 7 7 9

I have no problem.
My main problem is that i dont know how to program the code to eliminate the the values that are entered twice
(i.e. 5, 7, and 3)

hence you see below. 5 is removed from the first line, then 7 then 3

1 2 3 6 7 7 9
1 2 3 6 7 9
1 2 6 7 9
2 6 7 9

[VernonDozier]

From the spec output, removing 7...

1 2 3 6 7 7 9
1 2 3 6 7 9

The spec removes ONE 7, not both. Hence I see nothing in the problem where you are asked to detect duplicates or handle duplicates in any way. You find a number and delete it. Key word here is "a", as in "one". Find the first or last 7 or any 7 in between, it does not matter.

So does your code work for NON-duplicates? Can yuou remove a non-duplicate? If not, the question about duplicates seems irrelevant. Assuming you successfully removed the 5 (i.e. a non-duplicate), but did not remove a 7 (you either removed no 7's or more than one 7 or something else went wrong), there's obviously a problem, but I'll reiterate my last post...

You need to give the input, give the actual output, then give the correct output, then point out how the actual output differs from the corect output.

I see the input and the correct output, but I don't see what the actual output is and how it differes from the correct output. Right off the bat though, I'm noticing your remove function on line 71. In particular, I am noticing a "temp" array and I have no idea what it does. I see nowhere where sortedArray is changed in that function.

Here's the normal way you delete an element from an array...

Let's take the array...

1 2 3 6 7 7 9

and delete a single 7.

Your process should be something like this...

• Find the index of 7.
• If 7 does not exist, return. There's nothing to do.
• If 7 exists, shift every element after 7 one space left.
• Reduce the array sdize by 1.

So in this case, you find the index of 7. It's 4. We could not care less whether 7 is a duplicate.
The array size is currently 7, so we want to move indexes 5 and 6 to spaces 4 and 5.
Decrease the array size by 1. You end up with...

1 2 3 6 7 9

Array size is 6.

Nowhere in this process is a temporary array required. So find the index, then set up a for-loop for all indexes AFTER that index and shift left one space. Then, as mentioned, decrease the array size by 1.