best method to find the freequent numbers

[Richard Bos]

Quicksort has complexity O(n log n). I think pure Quicksort has
worst-case complexity O(n^2), but there's no requirement for qsort()
to be implemented as pure Quicksort.

In fact, there's no requirement for it to be implemented as any kind of
quicksort at all, though for obvious reasons it often is.

Richard

 

[Mark F. Haigh]

I have a vector of integers, such as [1 3 6 7 6 3 3 4 9 10 ]

and I want to find out the number which occurs most frequently.what is the
quick method. My array size is huge.

what I am doing is

1. find out the maximum value N
2. loop through 1...N
3. count # times each occurred
4. output the most frequent one

Are there are more efficient implementations avaiable?
Thanks

Try this. Note that if there are multiple integers with the same
number of occurrances, this code returns the highest valued one.

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *p, const void *q)
{
return *((int *) p) - *((int *) q);
}

int sort_and_get_most_popular(int *arr, size_t nelem)
{
int ret = *arr;
size_t i, count = 1, best = 1;

qsort(arr, nelem, sizeof *arr, cmp);
for(i = 1; i < nelem; i++) {
if(arr == arr[i - 1])
count++;
else {
if (count > best) {
ret = arr[i - 1];
best = count;
}
count = 1;
}
}
return ret;
}

int main(void)
{
int arr[] = { 1, 3, 6, 7, 6, 3, 3, 4, 9, 10 };
int result = sort_and_get_most_popular(arr,
sizeof arr / sizeof *arr);

printf("result: %d\n", result);
return 0;
}

[mark@icepick]$ gcc -Wall -ansi -pedantic -O2 foo.c -o foo
[mark@icepick]$ ./foo
result: 3


Give it a good review, though-- It's late, I'm tired, and I whipped it
up very quickly.

Mark F. Haigh
(e-mail address removed)