Hello Pascal!

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.

Here we go getting expensive again.  ;-)

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

// takes sorted array of integers (int, long, long long, etc.)
// and overwrites it with out the dupes.  Returns how many were
// removed.  Updates *len with the new size.
size_t remove_dupes(some_integral_t* array, size_t* len)
{
  size_t removed = 0;
  size_t i, j;
  for (i = 1, j = 1; i < *len; ++i)
  {
    assert(array[i-1] <= array[i]); // make sure it's sorted!
    if (array[j] != array[i])
    {
      array[j] = array[i];
      ++j;
    }
    else ++removed;
  }
  *len -= removed;
  return removed;
}

Something like that.  We go through the array only once.  The above could
be adapted to use a second, output array, independant from the input array.
 Thus, this, too, would have O(n) characteristics.

Darin

---