Project 03: Sorting

Individual, Due: 2025 Oct 17, 11:59pm

In this assignment, you will implement a variety of tests for sorting algorithms and modify some common sorting algorithms.

Warning

Not only should your implementation work correctly, but it will need to use space and time efficiently to receive full credit.

Important

The web contains solutions to some of these problems. You are NOT allowed to use the web as a reference or resource!

This assignment is based on exercises from the Algorithms 4/e book and website.

Doubling Test (2.1.31)

Write a client that performs a doubling test for the following sorting algorithms:

Sorting Alg Name	How to Call	File / Code	Documentation
Bubble Sort	`Bubble.sort`	`Bubble.java`	wikipedia
Selection Sort	`Selection.sort`	code	docs
Insertion Sort	`Insertion.sort`	code	docs
Shell Sort	`Shell.sort`	code	docs
Top-Down Merge Sort	`Merge.sort`	code	docs
Bottom-Up Merge Sort	`MergeBU.sort`	code	docs
Quicksort	`Quick.sort`	code	docs
Quicksort Median-of-3	`QuickSortMedian3.sort`	`QuickSortMedian3.java`	wikipedia
Quicksort Median-of-5	`QuickSortMedian5.sort`	`QuickSortMedian5.java`	wikipedia
Linked-List Sort	`LinkedListSort.sort`	`LinkedListSort.java`	wikipedia

Note

You will need to implement Quicksort Median-of-3, Median-of-5, and Linked-List Sort before you can run doubling tests on them.

Start at \(N\) equal to \(1000\), and then print \(N\), the number of seconds to perform the sort, and the ratio as \(N\) doubles. Using the actual times given, derive an equation that predicts how long the sorting algorithm takes to sort \(N\) random values. Use your program and equations to validate that insertion sort and selection sort are quadratic for random inputs, and formulate and test a hypothesis for shellsort.

Warning

Be careful that your timing does not include the allocation and initialization of the array, and be sure not to sort an already sorted array!

You may want to average the running times over a few runs for each \(N\).

Tip

Try to organize and generalize this test, so you can easily use it with other sorting algorithms (see below).

Median-of-3 Partitioning (2.3.18)

Add median-of-3 partitioning to quicksort, as described in the text (pg 296), by implementing the median function in QuickSortMedian3.MedianOf3 class. Run doubling tests to determine the effectiveness of the change in comparison to the standard algorithm (Quick.sort()).

Median-of-5 Partitioning (2.3.19)

Add median-of-5 partitioning to quicksort by implementing the median function in QuickSortMedian5.MedianOf5 class.

Run doubling tests to determine the effectiveness of the change in comparison both to the standard algorithm (Quick.sort()) and to median-of-3 partitioning (previous exercise).

Note

For full credit, devise a median-of-5 algorithm that uses fewer than seven compares on any input.

Linked-List Sort (2.2.17)

Implement a natural merge sort for linked lists. This is the method of choice for sorting linked lists because it uses no extra space (beyond a few local variables) and is guaranteed to have a linearithmic runtime in the worst case.

For full credit, implementation must:

use natural merge sort,
must allocate only a constant amount of additional space,
efficiently (linearithmic!) sort lists that contain a large number of entries (ex: 1 million).

To prove empirically the last item, run doubling tests on your implementation.

Warning

Merge sort is straightforward to implement recursively, but the JVM stack size becomes an issue with some of the parts; use loops instead.

The main implementation of linked list is in LinkedList.java, while the sorting algorithm is in LinkedListSort.java.

Edge Cases (2.1.34, 2.3.30)

Write a client that runs sort() on difficult or pathological cases that might turn up in practical applications. Examples include arrays that are already in order, arrays in reverse order, arrays where all keys are the same, arrays consisting of only two distinct values, and arrays of size 0 or 1. Use standard bubble sort, selection sort, insertion sort, shellsort, quicksort.

Tip

You may want to write functions that generate a pathological arrays of a given size \(N\).

Important

Be careful that your timing does not include the allocation and initialization of the array, and be sure not to sort an already sorted array!

External

For this assignment, the only library functions you may call are those in java.util, stdlib.jar, java.lang.Math, and algs4.jar.

Submission

You will need to implement and analyze several tests, median of 3, median of 5, and natural merge sort for linked list.

Readme

Do all of the problems above in the appropriate Java file, and then write about your findings in the readme.md. Show your work and be thoughtful. Your job is to convince me that you have done the work and that you have either learned something new or verified an already understood concept.

Files

The diagram below indicate which files you can edit, which files/folder you should not edit, and the rest are files/folders that might be changed by IntelliJ or git but you should not change directly.

P03_Sorting/...
 ├─ P03_Sorting.iml
 ├─ .idea/...
 ├─ .git/...                    <- **DO NOT EDIT**
 ├─ .gitignore                  <- **DO NOT EDIT**
 ├─ .gitmodules                 <- **DO NOT EDIT**
 ├─ out/...
 ├─ libs/...
 ├─ src/...
 │   ├─ Bubble.java             <- **DO NOT EDIT**
 │   ├─ DoublingTest.java       <- Java file that you might need to modify
 │   ├─ EdgeCases.java          <- Java file that you might need to modify
 │   ├─ LinkedList.java         <- **DO NOT EDIT**
 │   ├─ LinkedListSort.java     <- Java file that you might need to modify
 │   ├─ MedianOfN.java          <- **DO NOT EDIT**
 │   ├─ QuickSortMedian.java    <- **DO NOT EDIT**
 │   ├─ QuickSortMedian3.java   <- Java file that you might need to modify
 │   └─ QuickSortMedian5.java   <- Java file that you might need to modify
 ├─ data/...                    <- Additional test input files you create
 ├─ data_ref/..                 <- **DO NOT EDIT**
 └─ readme.md                   <- Fill this out before submission!

We will supply an IntelliJ project with stdlib.jar and algs4.jar libraries, MedianOfN abstract class, QuickSortMedian class, and a standard bubble sort algorithm. The libraries contain many useful classes.

Submission

Once you have completed the assignment requirements, simply stage, commit, and push your changes to the CSE GitLab, and then close the issues.

Do NOT submit anything to the course Brightspace page.

Grading Rubric


	Implementation
3pts	Correct and efficient implementation of `QuickSortMedian3.MedianOf3.median()`
3pts	Correct and efficient implementation of `QuickSortMedian5.MedianOf5.median()`
3pts	Correct implementation of `LinkedList.sort()`
3pts	Efficient implementation of `LinkedList.sort()`
	Readme
3pts	Completed `readme.md`
9pts	Doubling tests are reasonable for all 10 sorting algorithms
3pts	Convincing edge cases and analysis