All files mentioned here can be found in ~raw/public/cps206/

File "Sqt2.java" defines a test program for sorting programs, called "Sqt2", which includes in this case a version of QUICKSORT implemented by method Qs. The main method of Sqt2 reads one integer parameter from the command line. This parameter, N, must be > 1, and gives the number of elements in each sequence to be sorted. The program then generates every possible sequence of N integers, calls Qs on each, and checks the result for being in non-decreasing order. The program as a whole reports the total number of sequences generated, and the number of comparisons needed by Qs() calls, total.

Example of use:

java Sqt2 5

should produce test output for sorting ALL sequences of 5 integers, selected from the set {1, ..., 5}, including those with multiple copies of the same integer:

The output above took 15 secs to produce on my Pentium II 266.

A subclass of Sqt2, called "Stream", implements the code for each Fiber.

Variable P is the number of Fibers simulated. In this code, P is declared "final int", and is set to 2, at line 136 of Sqt2.

This code is duplicated in file "Sqt2.java", except that P = 3 in that version. Similarly, file "Sqt1.java" sets P=10.

This version of the program makes use of two classes, which are used to perform the "Fiber" simulation. Class "StreamRun" (file StreamRun.java) is derived from "Thread", and implements methods which simulate "Branch and dismiss", along with code to initialize fibers, and to start and kill them.

Class StreamRun makes use of class "Sem" (file Sem.java), which implements the classic form of Dijkstra semaphore.

Files "Swq.java", "Swq3.java", and "Swq4.java" all run the same Qs() method as do the "Sqti" classes, but these files allow a specified sequence to be read from stdin. The read-in sequence is printed, then sorted by Qs(), then printed again.

Swq sets P=10, Swq3 sets P=3, and Swq4 sets P=4. In addition, Swq3 and Swq4 print more debugging information, and Swq4 does its recursive calls in the reverse order from the others.

Finally, file "qsort.java" implements the original QUICKSORT algorithm, without the changes needed to allow it to run multiple fibers.