how to remove duplicate data while doing insertion sort?

lovekeiiiy

Member
Joined
Dec 29, 2013
Messages
12
Programming Experience
Beginner
I'm basically stump at the moment. Doing a programming assignment. The task is to remove any duplicate data while performing an insertion sort. It's a console application, and uses a class to isolate the array. The sorting code is within the class and was given. Only need to modify it.

C#:
class ArrayIns    {
        [code removed]
        public ArrayIns(int max)          // constructor
        {
            a = new long[max];                 // create the array
            nElems = 0;                        // no items yet
        }
        //--------------------------------------------------------------
        
        
[code removed]
        public void insertionSort()
        {
            int inner, outer;


            for (outer = 1; outer < nElems; outer++)     // outer is dividinner g linner e
            {
                long temp = a[outer];                       // remove marked item
                inner = outer;                              // start shifts at outer
                while (inner > 0 && a[inner - 1] >= temp)   // until one is smaller,
                {
                    a[inner] = a[inner - 1];                // shift item to right
                    --inner;                                // go left one position
                }
                a[inner] = temp;                             // inner sert marked item
            }  // end for
        }


        [code removed]
        }

What the book suggests is if a duplicate is found, change that data to a -1 (since the array is filled with numeric values that are positive). This will place the all the duplicate items in the first elements. I have zero success in getting the sort to change the values and move the indexes. I've tried adding
C#:
if(a[inner -1] == a[inner]
{
     a[inner -1] = -1;  //i've also tried a[inner];
}
I've placed this code between inner = outer line and while loop. It wrecked havoc all over the routine.

My latest attempt, still not successful, but a little closer:
C#:
if (a[inner - 1] == a[inner])                {
                    for (int x = 0; x < inner; x++)
                    {
                        long y = a[x + 1];
                        a[x] = a[x + 1];
                    }
                    a[0] = -1;  //I changed outer counter in the initial For loop to variable o.  I declared it before the initial for loop with assignment 1
                    o++;
                }
my thinking, is if a duplicate values are found, move all values up one elements up that element. This should leave index 0 (zero) free, and assign it -1. Then just increment the outer counter by 1, when sort goes to sort new values, it will start with the after the last -1. Unfortunately, it's only changing one element.

If I can the above to work, than I can just do another for loop to count how many -1s that are; although I can probably just build a the count in the for loop to change the values to -1. Then use that value with a for to move the sorted values down that many index, copy over the -1s, and changing the nElems (the programs counter for how many elements are currently used)
 
Last edited:
looks like I finally figured it out.
C#:
int inner, outer, o;
            o = 1;
            int numberOfDuplicatesFound = 0;


            for (outer = o; outer < nElems; outer++)     // outer is dividinner g linner e
            {
                long temp = a[outer];                       // remove marked item
                inner = outer;                              // start shifts at outer


                while (inner > 0 && a[inner - 1] >= temp)   // until one is smaller
                {
                    //
                    if (a[inner - 1] == temp)
                    {
                        for (int x = inner; x >0 ; x--)
                        {
                            a[x] = a[x - 1];
                        }
                        a[0] = -1;
                        o++;
                        numberOfDuplicatesFound++;
                        outer--;
                        break;
                    }
                    else
                    {
                        a[inner] = a[inner - 1];                // shift item to right
                        --inner;                                // go left one position
                    }
                }
                    a[inner] = temp;                             // inner sert marked item


            }  // end for


            
            //remove duplicate data (-1 values)


        }

I still need to write the code for the remove duplicate data, but right now, it is producing the output with a bunch a negative -1s in front, and rest of the positive numbers after them in sequential order.
 
Back
Top Bottom