Quicksort has an _average_ time of O(n log n) for random data, but it
can degenerate to O(n^2) for certain initial orderings. Thus, your
statement that it will take O(n log n) time is not justified. That is
why it has been suggested to use a heapsort or mergesort, both of
which are O(n log n).
Dave
On Dec 20, 8:02 pm, Bookpet <[EMAIL PROTECTED]> wrote:
> I think this method will solve the problem:
> 1). first, sort the linear array using quick sort method, it will take
> n(logn) time
> 2).second, scan the sorted linear array:
> Array[nLen] //sorted data Array.
> T tSameData;
> int iNum;
> int i, j, k, iLast = nLen; //nLen is the length of the array.
> for (i=0; i<iLast; i++)
> {
> tSameData = Array[i];
> j = i;
> while (Array[j+1] == tSameData) j++;
> if (j > i)
> {
> iNum = j - i;
> for(k=iLast-1, i=i+1; k>iLast-1-iNum; k--, i++)
> {
> Array[i] = Array[k];
> }
> iLast -= iNum;
> }}
>
> nLen = iLast;
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
