Řazení slov

Jednovláknová verze

c-plus-plus

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
using namespace std;

inline int value(char* str)
{
    short int ch1 = str[0] - 96;
    short int ch2;
    short int ch3;
    short int ch4;
    if(str[1] == 0)
    {
      ch2 = 0;
      return ch1*19683;
    }
    ch2 = str[1] - 96;
    if(str[2] == 0)
    {
      ch3 = 0;
      return ch1*19683 + ch2*729;
    }
    ch3 = str[2] - 96;
    if(str[3] == 0)
    {
      ch4 = 0;
      return ch1*19683 + ch2*729 + ch3*27;
    }
    ch4 = str[3] - 96;
    return ch1*19683 + ch2*729 + ch3*27 + ch4;
}

inline void ValueToStr(int value, char* str)
{
    str[0] = value / (19683) + 96;
    value %= (19683);
    if(value == 0)
    {
      str[1] = 0;
      return;
    }
    str[1] = value / (729) + 96;
    value %= (729);
    if(value == 0)
    {
      str[2] = 0;
      return;
    }
    str[2] = value / 27 + 96;
    value %= 27;
    if(value == 0)
    {
      str[3] = 0;
      return;
    }
    str[3] = value + 96;
    str[4] = 0;
}

void CountingSort(char** array, int size)
{
    const int diff = 19683;
    int countArray[511758];
    for(int i=0;i<511758;i++)
      countArray[i] = 0;
    
    for(int i=0;i<size;i++)
      countArray[value(array[i])-diff]++;
    
    for(int i=0,j=0;i<511758;i++)
    {
      for(int k=0;k<countArray[i];k++,j++)
        ValueToStr(i+diff,array[j]);
    }
}


int main()
{
    LONGLONG frequency;
    LONGLONG counter;
    LONGLONG begin;
    QueryPerformanceFrequency((LARGE_INTEGER*)&frequency);
    
    srand(time(0));
    int count;
    cin>>count;
    char** array = new char*[count];

    QueryPerformanceCounter((LARGE_INTEGER*)&begin);

    for(int i=0;i<count;i++)
    {
        int chars = rand() % 4 + 1;
        array[i] = new char[5];
        array[i][chars] = '\0';
        for(short int j=0;j<chars;j++)
          array[i][j] = rand() % 26 + 97;
    }
    
    QueryPerformanceCounter((LARGE_INTEGER*)&counter);
    cout<<(counter - begin) / (frequency / 1000)<<endl;
    
    QueryPerformanceCounter((LARGE_INTEGER*)&begin);
    CountingSort(array,count);
    QueryPerformanceCounter((LARGE_INTEGER*)&counter);
    cout<<(counter - begin) / (frequency / 1000)<<endl;
    
    /*for(int i=0;i<count;i++)
        cout<<array[i]<<endl;*/
    
    getchar();
    getchar();
    
    for(int i=0;i<count;i++)
        delete [] array[i];
    delete [] array;
}

Neformátovaný

Přidáno: 27.1.2013
Expirace: Neuvedeno

Autor: Lukáš Hruda