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

Last updated

Was this helpful?