Removing duplicates from array [C#]

M

Morpheus

Regular
Joined
Jan 18, 2002
Messages
62
I have an array that is sorted with insert sort:

C#: 
public void InsertionSort()
		{
			int inner, outer;

			for(outer=1; outer<nElems; outer++)     // out is dividing line
			{
				long temp = a[outer];            // remove marked item
				inner = outer;                      // start shifts at out
				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;                  // insert marked item
			}  
		}

I want to remove any duplicates with NoDups().
The problem is that it must be an effective algorithm so I can't just shift down one space everytime a duplicate is found.
No element should be moved more than one time no matter how many duplicates there are in the array.

I would be really thankfull for any kind of tip
 
How large an array are you looking at? It may be an alternative to copy the valid elements to a new array.
Alternatively could you not filter out the duplicates as you are adding them to prevent the duplicates in the first place.
also having a look under System.Collections may save some time as there is a SortedArray class that puts things into a sorted order and allows binary searches so finding duplicates would be quick. Or even just using System.Array.Sort could save you having to do your own sort routine.
 
Back
Top