CSCI H343 Data Structures Fall 2023

Lab 6: Generic Quicksort

Problem Description

Implement quicksort in a way that is generic enough that it can be applied to any input sequence that is represented as an array or a linked list, by using the Iterator interface. The elements of the sequence do not have to be integers, but instead could be anything that implements the java.util.Comparable interface:

public static <E extends Comparable<? super E>>
void quicksort(Iterator<E> begin, Iterator<E> end) {
    // your code
}

Your implementation should maintain the time complexity of quicksort: it should have worst case $O(n^2)$ time complexity and average case $O(nlog(n))$ time complexity.

Test quicksort() thoroughly in StudentTest.java.

Support Code and Submission