Hi Darin.

19-May-04 17:32:14, Darin McBride wrote to Pascal Schmidt


 DM> Hello Pascal!

 DM> Replying to a message of Pascal Schmidt to Neil Heller:

 PS>> Hi Neil! :-)

 NH>>> How does this sound:  do a QuickSort on the array (after it's 
 NH>>> been determined to all fit easily into memory).  QuickSort does an 
 NH>>> in-place sort.  The Bit-O QuickSort is n log n.
 PS>> Quicksort has a worst-case of O(n^2), in the case of an already sorted
 PS>> array. But your right, on random data it's O(n log n).

 NH>>> Then go once through the array eliminating the dupes.
 PS>> Still O(n log n) in total, luckily.

 NH>>> The question then becomes: how does one 
 NH>>> eliminate the holes once all the duplicates are eliminated>
 PS>> I thought you wanted to find out whether there are any duplicates at
 PS>> all? Anyway, eliminating the holes would just be a memcpy, copying
 PS>> everything above the hole down.

 DM> Here we go getting expensive again.  ;-)

 DM> If you want to eliminate the dupes at this point, simply skip them 
 DM> through the 
 DM> array

 DM> // takes sorted array of integers (int, long, long long, etc.)
 DM> // and overwrites it with out the dupes.  Returns how many were
 DM> // removed.  Updates *len with the new size.
 DM> size_t remove_dupes(some_integral_t* array, size_t* len)
 DM> {

 DM>   for (i = 1, j = 1; i < *len; ++i)
 DM>   {
 DM>     assert(array[i-1] <= array[i]); // make sure it's sorted!
 DM>     if (array[j] != array[i])
 DM>     {
 DM>       array[j] = array[i];
 DM>       ++j;
 DM>     }

 DM> Something like that.

something,  start it with j=0, and  ++j  before  array[j]=array[i]

your way {1,2,3} becomes {1,3}

 -=> Bye <=-

---