[ create a new paste ] login | about

Link: http://codepad.org/6AxFM1C2    [ raw code | output | fork ]

C++, pasted on Nov 17:
#include <iostream>
//#include <windows.h>
//#include <time.h>
//#include <stdlib.h>
 
using namespace std;
 
template <typename T> void CountingSort(T *A, long n, long * comperisons, long * exchanges);
template <typename T, typename Func> bool Sort(Func funcSort, 
   T * A, long n, long * com, long * exc, long * time);
 
int main(void)
{
       // srand((unsigned) time(NULL));
        long N = 100000;
        long * A = new long[N];
        long com = 0;
        long exc = 0;
        long timet = 0;
        for(int i = 0; i < N; i++)
        {
                A[i] = i;//rand()%100000;
        }
        Sort(CountingSort<long>, A, N, &com, &exc, &timet);
        cout << com << "   " << exc << "   ";// << time;
}
 
template <typename T> void CountingSort (T *A, long n, long * comperisons, long * exchanges)
{
        T max = A[0];
        T min = A[0];
        for(int i = 0; i < n; i++)
        {
                if(A[i] > max) 
                {
                        (*comperisons)++;
                        max = A[i];
                }
                if(A[i] < min)
                {
                        (*comperisons)++;
                        min = A[i];
                }
        }
        int i, j; 
        T c;
        T *B = (T *)calloc(max - min + 1, sizeof(T));
        for (i = 0; i < n; i++) 
                ++B[A[i] - min];
        for (j = min; j <= max; ++j)
        {
                c = B[j - min];
                while (c > 0)
                {
                        *A = j; 
                        ++A; 
                        --c;
                }
        }
        free(B);
}
 
template <typename T, typename Func> bool Sort(Func funcSort, 
              T * A, long n, long * com, long * exc, long * time)
{
       // LARGE_INTEGER freq, t1, t2;
       // if(QueryPerformanceFrequency(&freq))
       // {
       //        QueryPerformanceCounter(&t1);
                funcSort(A, n, com, exc);
       //        QueryPerformanceCounter(&t2);
       //       time = 1000 * (t2.QuadPart - t1.QuadPart) / freq.QuadPart;
                return true;
       // }
       // else
       // {
       //        return false;
       //}
//}
}


Output:
1
99999   0   


Create a new paste based on this one


Comments: