3.6. Homework

This section explains the homework assignment regarding Hybrid Sort.

Hybrid Sort

Your task is to write a program that sorts a 2D-array of comparable keys into an 1D-array where all the keys are sorted in ascending order. Here is a sample input to your program:

Integer[][] input = {{0,  1,  2,  3},
                     {7,  6,  5,  4},
                     {0,  3,  1,  2},
                     {4,  7,  6,  5},
                     {9,  8, 11, 10}};

Here is the expected output given the sample input:

[0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 9, 10, 11]

Each row in the input array has one of the following properties:

• Sorted in ascending order (e.g., the 1st row).

• Sorted in descending order (e.g., the 2nd row).

• Mostly sorted in ascending order (e.g., the 3rd row).

• Mostly sorted in descending order (e.g., the 4th row).

• Randomly distributed (e.g., the 5th row).

The easiest way is to merge all rows in the input array into an 1D-array then sort it using IntroSort. The implementation of this strategy is provided to establish the baseline: HybridSortBaseline. Your goal is to design a sorting mechanism that gives a noticeable speed-up over this baseline.

Tasks

• Create a class HybridSortHW inheriting HybridSortunder the package hybridsort.

• Override the sort() method and evaluate your program for robustness and runtime speeds using HybridSortTest:

  • Try different input arrays; you are responsible for the robustness of your program.

  • Try different configurations for speed comparison (e.g., row size, column size, shuffle ratio).

• Write the report hw1.pdf describing the logic behind your mechanism and the speed comparison against the baseline.

Submission

• Commit and push everything under the hybrid package.

• Submit hw1.pdf to Canvas.

Notes

• You are not allowed to:

  • Use any implementation that is not written by you nor provided by this course.

  • Call any sorting methods built-in Java or 3rd-party libraries.

  • Merge all rows first and apply a fancy sorting algorithm to the 1D array as the baseline does.

• The input matrix can:

  • Contain an arbitrary number of rows, where the size of each row is also arbitrary.

  • Include any type of the keys that are Comparable.

Results

Baseline: 20697

• Cannot run: 7

• Extremely slow: 6

• Code not found: 1

6873	21512	23027	25573
15545	21599	23209	25825
18443	21802	23411	25928
18618	22037	23417	28756
18676	22038	23622	29390
18933	22073	24988	43903
19787	22217	25289	67900
19851	22222	25531	99835
20378	22480	25536	217868