First round of sorting lab competition.

Problem description

Develop a sorting algorithm to sort words in a long text file (a few thousand words) by the following criteria: by word length as a primary criteria and alphabetically as a secondary one. This means that all shorter words come before all longer words and within each group of words of the same length the words are sorted alphabetically (more precisely, according to compareTo method of String class).

Your goal is to develop an algorithm that sorts as fast as possible. "Fast" here means direct timing of the program, not just the Big-Theta approximation.

More details about the lab are posted here.

Results of the preliminary round.

These are the results of the first (initial) round of the lab. The test was run on discovery in /tmp. The input file is here.

The script ran each program with 10 rounds of sorting 6 times. All 6 timing results are displayed. It then checked whether the output file was sorted and displayed the word count for the output file. The correct word count is 24240.


 Group1: 

664
668
650
675
658
653
Congratulations! Your sorting is correct.
24239 out1.txt

 Group2: 

Total Time: 475 for 10 loops.
Total Time: 493 for 10 loops.
Total Time: 404 for 10 loops.
Total Time: 401 for 10 loops.
Total Time: 366 for 10 loops.
Total Time: 402 for 10 loops.
Congratulations! Your sorting is correct.
24240 out2.txt

 Group3: 

14478
14541
14620
14669
14472
14533
The ordering condition is broken: a appears before A
Sorry, your sorting failed.
24240 out3.txt

 Group4: 

130
133
136
134
131
112
Congratulations! Your sorting is correct.
24240 out4.txt

 Group5: 

456
399
394
451
454
400
Congratulations! Your sorting is correct.
24240 out5.txt

 Group6: 

296
291
271
297
305
338
Congratulations! Your sorting is correct.
24240 out6.txt

 Group7: 

191
196
204
198
208
132

 Group8: 

436
306
356
319
281
435
Congratulations! Your sorting is correct.
0 out8.txt

 Group9: 

418
411
365
413
334
423
The length condition is broken: altogether is longer than amendmen
Sorry, your sorting failed.
23665 out9.txt

Based on these results, the following groups failed the basic requirements:

Failing the requirements at this point does not lead to a penalty, but these issues need to be fixed before the final round, otherwise you woudl lose a significant portion of the credit.


CSci 3501 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.