Sorting Contest

[md]

Sorry, I have clarified the original post.

There are four data sets to be sorted, a 256mb file containing single-byte values (unsigned char), a 256mb file containing 2-byte values(unsigned short), a 1gb file containing single-byte values (unsigned char) and a 1gb file containing 2-byte values (unsigned short).

They are to be sorted from least to greatest.

[zylum]

http://compsci.ca/v3/viewtopic.php?t=10521

[md]

I should point out that the files to be sorted are binary, not text. And there has been one submission already.

[bugzpodder]

[deletia]

md says: What part of "Contest" did you miss? Try not to give out solutions for others to copy; it makes the whole thing more fun for all involved.

[klopyrev]

I bet Knuth has a faster way to sort without reading the tapes more than once:P

[md]

Thanks bugz... where before it was left to people to figure that out on their own, now there is a solution they can just copy.

Helping people is good and all, but giving away most of one of the better solutions is just ass-hat-ery.

[zylum]

well its the most obvious solution

and i dont think my solution will work as it reads text not binary :S

[md]

feel free to fix that part

Also, it's only the obvious solution if you think of it. There are more then a few people on IRC that missed it.

[md]

Results

There were two entries, one from saad and one from zylum. I of course have written my own sorts to compare against.

results for sorting bytes:

code:

256MB                        1GB md                      5.0s                         32.0s saad                    10.1s                        48.1s zylum                   SF                           SF

results for sorting shorts:

code:

256MB                        1GB md                        -                           - saad                      -                           - zylum                    SF                           SF

I didn't run the sorts for shorts, since in prevous testing I've shown that my sort is faster then saads, and because zylums segfaulted again. Therefor... the winner is...

Saad

+360bits

[wtd]

The winning submission should be posted in source form.

[Saad]

Done in C++, compiled via g++ compiler

c++:

/* For this sort we will be calculating the number of each byte occurs and then output each byte in the number of times it occurs Data type changes this is for short int */ #include <fstream> using std::ifstream; using std::ofstream; using std::ios; int main(int argc, char **args){     unsigned int count[65536];     ifstream in;     in.open(*(args + 1), ios::binary);     // Initialise all the counters to 0     for (int i = 0; i <= 65535; i++){         count[i] = 0;     }     in.seekg(0, ios::end);     register int max = in.tellg();    // Find the number of bytes in the file     in.seekg(0,ios::beg);         register unsigned long long int num;     for (register unsigned int i = 0; i < max; i+= 8){         // Read in bytes 8 at a time and then add one to that array location         in.read((char *) &num, 8);         (*(count + (num & 65535)))++;         (*(count + ((num >> 16) & 65535)))++;         (*(count + ((num >> 32) & 65535)))++;         (*(count + ((num >> 48) & 65535)))++;     }     // Output the data     ofstream out;     out.open (*(args + 1), ios::binary);     for (unsigned int i = 0; i <= 65535; i++){         register unsigned int c = *(count + i);         // Save constantly indexing the array         if (c > 0){             // Generate an array containing the number of bytes occured so we output that array at once instead of cosntantly calling write             unsigned short int *a = new unsigned short int[c];             for (unsigned int j = 0; j < c; j++)                 *(a + j) = i;             out.write((char *) a, c << 1);             delete [] a;         }     }     // Close the streams     in.close();     out.close();     return 0; }

I dont know which source forum to post it to.

md asked me to post his so here it is

[A.J]

erm.....................saad, is this similar to what i did in turing (at school)? cause i sorted it using your algorithm but i did not know what you mean by sorting bytes (and I never heard about compsci.ca until about a week ago)

plus I started turing recently so I needed to ask you if this is sort of what your algorithm was ?

code:

var stream, x : int open : stream, "ENTER TEXT FILE NAME HERE.txt", get var sort : array 1 .. (max value being tested) of int % initialize the 'sort' array to 0 for all values loop     exit when eof (stream)     get : stream, x     sort (x) += 1 end loop for i : 1 .. (max value being tested)     for j : 1 .. sort (i)         put i, " " ..     end for end for

[Saad]

Yes it is, although you should change the code so that it supports binary files. Its read/write in Turing.

[A.J]

could you give man example saad?

[Saad]

Turing:

var file : int open : file, "foo.dat", write for i : 1 .. 10     write : file, i end for close : file open : file, "foo.dat", read for i : 1 .. 10     var number : int     read : file, number     put number end for close : file

One advantage is to binary files is that binary files can be accessed at random location vs an ASCII (text) file which you need to access sequentially.