A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Given a string "ABCDE"

• Substring: {"A", "BC", "CDE", ...}

• Subsequence: {all substrings, "AC", "ACE", ...}

• Not subsequence: {"BA", "DAB", ...}

Longest common subsequence

• The longest subsequence commonly shared by multiple strings.

• e.g., “baal” is a LCS of “bilabial” and “balaclava”.

Can there be more than one longest common subsequence?

Application

• Find the longest common subsequence in DNA (e.g., GAATGTCCTTTCTCTAAGTCCTAAG).

Abstraction

Let us create the abstract class LCS:

public abstract class LCS {
    /**
     * @param a the first string.
     * @param b the second string.
     * @return a longest common sequence of the two specific strings.
     */
    public String solve(String a, String b) {
        return solve(a.toCharArray(), b.toCharArray(), a.length() - 1, b.length() - 1);
    }

    /**
     * @param c the first array of characters.
     * @param d the second array of characters.
     * @param i the index of the character in {@code c} to be compared.
     * @param j the index of the character in {@code d} to be compared.
     * @return a longest common sequence of the two specific strings.
     */
    protected abstract String solve(char[] c, char[] d, int i, int j);
}

Recursion

Let us create the LCSRecursive inheriting LCS:

public class LCSRecursive extends LCS {
    @Override
    protected String solve(char[] c, char[] d, int i, int j) {
        if (i < 0 || j < 0) return "";
        if (c[i] == d[j]) return solve(c, d, i - 1, j - 1) + c[i];

        String c1 = solve(c, d, i - 1, j);
        String d1 = solve(c, d, i, j - 1);
        return (c1.length() > d1.length()) ? c1 : d1;
    }
}

• L4: no character is left to compare for either string.

• L5: when two characters match, move onto c[:i-1] and d[:j-1].

• L7: gets the longest common subsequence between c[:i-1] and d[:j].

• L8: gets the longest common subsequence between c[:i] and d[:j-1].

• L9: returns the longest subsequence.

The followings demonstrate a recursive way of finding a LCS between two strings:

Dynamic Programming

Let us create the LCSDynamic class inheriting LCS.

public class LCSDynamic extends LCS {
    @Override
    protected String solve(char[] c, char[] d, int i, int j) {
        return solve(c, d, i, j, createTable(c, d));
    }

    /**
     * @param c the first string.
     * @param d the second string.
     * @return the dynamic table populated by estimating the # of LCSs in the grid of the two specific strings.
     */
    protected int[][] createTable(char[] c, char[] d) {
        final int N = c.length, M = d.length;
        int[][] table = new int[N][M];

        for (int i = 1; i < N; i++)
            for (int j = 1; j < M; j++)
                table[i][j] = (c[i] == d[j]) ? table[i - 1][j - 1] + 1 : Math.max(table[i - 1][j], table[i][j - 1]);

        return table;
    }
}

• L4: creates a dynamic table and passes it to the solver.

• L12: the dynamic table is pre-populated before any recursive calls.

The following show the dynamic table populated by the previous example:

Let us define the solve() method:

protected String solve(char[] c, char[] d, int i, int j, int[][] table) {
    if (i < 0 || j < 0) return "";
    if (c[i] == d[j])  return solve(c, d, i - 1, j - 1, table) + c[i];
    
    if (i == 0) return solve(c, d, i, j - 1, table);
    if (j == 0) return solve(c, d, i - 1, j, table);
    return (table[i - 1][j] > table[i][j - 1]) ? solve(c, d, i - 1, j, table) : solve(c, d, i, j - 1, table);
}

• L2: no character is left to compare for either string.

• L3: when two characters match, move onto c[:i-1] and d[:j-1].

• L5: gets the longest common subsequence between c[:i] and d[:j-1].

• L6: gets the longest common subsequence between c[:i-1] and d[:j].

• L9: returns the longest subsequence by looking up the values in the dynamic table.

The followings demonstrate how to find a LCS using the dynamic table:

This is an advanced programming course in Computer Science that teaches how to design efficient structures and algorithms to process big data and methods to benchmark their performance for large-scale computing. Topics cover data structures such as priority queues, binary trees, tries, and graphs and their applications in constructing algorithms such as sorting, searching, balancing, traversing, and spanning. Advanced topics such as network flow and dynamic programming are also discussed. Throughout this course, students are expected to

• Have a deep conceptual understanding of various data structures and algorithms.

• Implement their conceptual understanding in a programming language.

• Explore the most effective structures and algorithms for given tasks.

• Properly assess the quality of their implementations.

There are topical quizzes and homework assignments that require sufficient skills in Java programming, Git version control, Gradle software project management, and scientific writing. Intermediate-level Java programming is a prerequisite of this course.

• Syllabus

• Schedule

Contents

1. Environment Setup

2. Quiz

Resources

• Main: src/main/java/edu/emory/cs/utils/Utils.java

• Test: src/test/java/edu/emory/cs/utils/UtilsTest.java

General

• Book: https://emory.gitbook.io/dsa-java/

• GitHub: https://github.com/emory-courses/dsa-java

• Time: MW 11:30AM - 12:45PM

• Location: Atwood 240

Instructors

• Jinho Choi Associate Professor of Computer Science Office Hours → MW 4PM - 5:30PM, MSC W302F

• Peilin Wu BS in Computer Science; BA in Physics and Astronomy Office Hours → TuTh 10:30AM - 12PM, MSC E308

• Jeongrok Yu BS in Computer Science and Economics Office Hours -> MW 2:30PM - 4PM, MSC E308

• Zinc Zhao BS in Computer Science; BA in Music Office Hours → TuTh 1PM - 2:30PM, MSC E308

Grading

• 1 + 10 topical quizzes: 70%

• 3 homework assignments: 30%

• Your work is governed by the Emory Honor Code. Honor code violations (e.g., copies from any source, including colleagues and internet sites) will be referred to the Emory Honor Council.

• Excuses for exam absence/rescheduling and other serious personal events (health, family, personal related, etc.) that affect course performance must be accompanied by a letter from the Office of Undergraduate Education.

Notes

• For every topic, one quiz will be assigned to check if you keep up with the materials.

• Homework assignments assess conceptual understanding, programming ability, and analytical writing skills relevant to this course.

• All quizzes and assignments must be submitted individually. Discussions are allowed; however, your work must be original.

• Late submissions within a week will be accepted with a grading penalty of 15% and will not be accepted once the solutions are discussed in class.

Development Kit

Install the latest version of the Java SE Development Kit (JDK) on your local machine:

• The required version: 17.x.x (or higher)

Version Control

Install Git using any of the following instructions:

• Git Installation Guide by Bitbucket

• Git Installation Guide by GitHub

Run the following commands on a terminal by replacing user.email and user.name with your email address and name:

git config --global user.email "your_id@emory.edu"
git config --global user.name "Your Name"

Integrated Development Environment

Install the latest version of IntelliJ IDEA on your local machine:

• The recommended version: 2022.3.x (Ultimate Edition)

• Apply for the academic license with your school email address to use the ultimate version.

Project Management

Launch IntelliJ and create a Gradle project by clicking the [New Project] button at the top:

• Name: dsa-java

• Location: local_path/dsa-java

• Check "Create Git repository"

• Language: Java

• Build system: Gradle

• JDK: 17

• Gradle DSL: Groovy

• Uncheck "Add sample code"

• Advanced Settings:

  • GroupId: edu.emory.cs

  • ArtifactId: dsa-java

Open gradle/wrapper/gradle-wrapper.properties and make sure distributionUrl indicates the latest version of Gradle:

distributionUrl=https\://services.gradle.org/distributions/gradle-7.6-all.zip

Click [Settings - Build, Execution, Deployment] on the menu:

• Click [Build Tools - Gradle] and set Gradle JVM to 17.

• Click [Compiler - Java Compiler] and set Project bytecode version to 17.

Click [File - Project Structure] and select [Project Settings]:

• Click [Project Settings - Project] and set SDK to 17 and Project language level to SDK default.

• Click [Project Settings - Modules - Dependencies] and set Module SDK to 17.

• Go to [Platform Settings - SDKs] and select 17.

Open build.gradle and make sure sourceCompatibility and targetCompatibility are set to java version 17 (add the following configurations if they do not exist already):

compileJava {
    sourceCompatibility = JavaVersion.VERSION_17
    targetCompatibility = JavaVersion.VERSION_17
}

Lastly, check mavenCentral() is configured as a repository in your build.gradle:

repositories {
    mavenCentral()
}

GitHub Integration

To integrate the project with your GitHub repository, click [Settings]:

• Choose [Version Control - Github] on the left pane.

• Click [+] and login with your GitHub ID and password.

• If you use two-factor authentication, log in with your personal access token.

Create .gitignore under the project and add the following contents:

/.gradle/
/.idea/
/.vscode/
/build/

Click [Git - GitHub - Share Project on Github] and create a repository:

• Make sure to check private.

• Repository name: dsa-java

• Remote: origin

• Description: Data Structures and Algorithms in Java

Add all files and make the initial commit. Check if the repository is created under your GitHub account: https://github.com/your_id/dsa-java.

Contents

1. Abstraction

2. Implementation

3. Unit Testing

4. Quiz

Resources

• Main: src/main/java/edu/emory/cs/algebraic

• Test: src/test/java/edu/emory/cs/algebraic

References

• TIOBE Programming Community Index

• PYPL Popularity of Programming Language

Auxiliary Method

Let us create and define testRobustnessAux() that checks the robustness of any PQ inheriting AbstractPriorityQueue:

• L6: the generic type T is defined specifically for this method such that the priority queue pq, the list keys, and the comparator comp take the same type T that is comparable.

• L7: any collection that inherits the interface has the member method that takes a and applies each key in the collection to the consumer.

• L8: any collection has the member method that returns the of the collection.

  • : creates a stream of the collection whose keys are sorted

  • : creates a collection specified by the .

  • : returns a collector that transforms the stream into a list.

• L9: iterates each of the sorted keys and compares it to the returned value of pq.remove().

What are the advantages of defining a method-level generic type?

Functional Programming

The following code shows a traditional way of iterating over a list (that is equivalent to L7 above):

Java 5 introduced an enhanced for loop that simplified the traditional for loop:

Java 8 introduced that enabled functional programming in Java. The following code takes each key (as a variable) in keys and applies it to pq.add():

The syntax of the above code can be simplified as follows (as shown in L7):

What are the main differences between object-oriented programming and functional programming?

Test: Robustness

Let us define the testRobustness() method that calls the auxiliary method testRobustnessAux():

• L7-9: tests different types of max-PQs. The keys need to be sorted in reverse order for it to test the remove() method.

• L11-13: tests different types of min-PQs. The keys need to be sorted in the natural order for it to test the remove() method.

The generic types of the PQs in L4-5 are explicitly coded as <Integer>, whereas they are simplified to <> in L7-13. When do generic types need to be explicitly coded?

Class

A class is a template to instantiate an object.

What is the relationship between a class and an object?

Let us create a class called Numeral that we want to be a super class of all numeral types:

package edu.emory.cs.algebraic;

public class Numeral {
}

• L1: packageindicates the name of the package that this class belongs to in a hierarchy.

• L3: public is an access-level modifier.

What are the acceptable access-level modifiers to declare a top-level class?

Let us declare a method, add() , that is an operation expected by all numeral types:

public class Numeral {
    /**
     * Adds `n` to this numeral.
     * @param n the numeral to be added.
     */
    public void add(Numeral n) { /* cannot be implemented */ }
}

• L4: @param adds a javadoc comment about the parameter.

The issue is that we cannot define the methods unless we know what specific numeral type this class should implement; in other words, it is too abstract to define those methods. Thus, we need to declare Numeral as a type of abstract class.

What are the advantages of havingNumeral as a super class of all numeral types?

There are two types of abstract classes in Java, abstract class and interface.

Can an object be instantiated by an abstract class or an interface?

Interface

Let us define Numeral as an interface:

public interface Numeral {
    void add(Numeral n);
}

• L2: abstract method

  • All methods in an interface are public that does not need to be explicitly coded.

  • Abstract methods in an interface are declared without their bodies.

Who defines the bodies of the abstract methods?

Let us create a new interface called SignedNumeral that inherits Numeral and adds two methods, flipSign() and subtract():

Can an interface inherit either an abstract class or a regular class?

public interface SignedNumeral extends Numeral {
    /** Flips the sign of this numeral. */
    void flipSign();

    /**
     * Subtracts `n` from this numeral.
     * @param n the numeral to be subtracted.
     */
    default void subtract(Numeral n) {
        n.flipSign();
        add(n);
        n.flipSign();
    }
}

• L1: extends inherits exactly one class or interface.

• L9: default allows an interface to define a method with its body (introduced in Java 8).

Can we call add() that is an abstract method without a body in the default method subtract()?

Although the logic of subtract() seems to be correct, n.flipSign() gives a compile error because n is a type of Numeral that does not include flipSign(), which is defined in SignedNumeral that is a subclass of Numeral.

What kind of a compile error does n.flipSign() cause?

There are three ways of handling this error: casting, polymorphism, and generics.

Casting

The first way is to downcast the type of n to SignedNumeral, which forces the compiler to think that n can invoke the flipSign() method:

default void subtract(Numeral n) {
    ((SignedNumeral)n).flipSign();
    add(n);
    ((SignedNumeral)n).flipSign();
}

This removes the compile error; however, it will likely cause a worse kind, a runtime error.

Why is a runtime error worse than a compile error?

Downcasting, although allowed in Java, is generally not recommended unless there is no other way of accomplishing the job without using it.

How can downcasting cause a runtime error in the above case?

Polymorphism

The second way is to change the type of n to SignedNumeral in the parameter setting:

default void subtract(SignedNumeral n) {
    n.flipSign();
    add(n);
    n.flipSign();
}

This seems to solve the issue. Then, what about add() defined in Numeral? Should we change its parameter type to SignedNumeral as well?

It is often the case that you do not have access to change the code in a super class unless you are the author of it. Even if you are the author, changing the code in a super class is not recommended.

Why is it not recommended to change the code in a super class?

How about we override the add() method as follows?

public interface SignedNumeral extends Numeral {
    @Override
    void add(SignedNumeral n);
    ...

• L2: @Override is a predefined annotation type to indicate the method is overridden.

The annotation @Override gives an error in this case because it is not considered an overriding.

What are the criteria to override a method?

When @Override is discarded, the error goes away and everything seems to be fine:

public interface SignedNumeral extends Numeral {
    void add(SignedNumeral n);
    ...

However, this is considered an overloading, which defines two separate methods for add(), one taking n as Numeral and the other taking it as SignedNumeral. Unfortunately, this would decrease the level of abstraction that we originally desired.

What are good use cases of method overriding and overloading?

Generics

The third way is to use generics, introduced in Java 5:

public interface Numeral<T extends Numeral<T>> {
    void add(T n);
}

• L1: T is a generic type that is a subtype of Numeral.

  • A generic type can be recursively defined as T extends Numeral<T>.

• L2: T is considered a viable type in this interface such that it can be used to declare add().

Can we define more than one generic type per interface or class?

The generic type T can be specified in a subclass of Numeral:

public interface SignedNumeral extends Numeral<SignedNumeral> {
    void flipSign();

    default void subtract(SignedNumeral n) {
        n.flipSign();
        add(n);
        n.flipSign();
    }
}

• L1: T is specified as SignedNumeral.

This would implicitly assign the parameter type of add() as follows:

void add(SignedNumeral n);

The issue is that the implementation of add() may require specific features defined in the subclass that is not available in SignedNumeral. Consider the following subclass inheriting SignedNumeral:

public class LongInteger implements SignedNumeral {
    @Override
    public void flipSign() { /* to be implemented */ }

    @Override
    public void add(SignedNumeral n) { /* to be implemented */ }
}

• L1: implements inherits multiple interfaces.

• L2-6: LongInteger is a regular class, so all abstract methods declared in the super classes must be defined in this class.

Since the n is typed to SignedNumeral in L6, it cannot call any method defined in LongInteger, which leads to the same issue addressed in the casting section.

Would the type of n being SignedNumeral an issue for the subtract() method as well?

Thus, SignedNumeral needs to define its own generic type and pass it onto Numeral:

public interface SignedNumeral<T extends SignedNumeral<T>> extends Numeral<T> {
    void flipSign();

    default void subtract(T n) {
        n.flipSign();
        add(n);
        n.flipSign();
    }
}

• L1: T is a generic type inheriting SignedNumeral, that implies all subclasses of SignedNumeral.

T can be safely passed onto Numeral because if it is a subclass of SignedNumeral, it must be a subclass of Numeral, which is how T is defined in the Numeral class.

Enum

Let us create an enum class called Sign to represent the "sign" of the numeral:

public enum Sign {
    POSITIVE,
    NEGATIVE;
}

• All items in an enum have the scope of static and the access-level of public.

• Items must be delimited by , and ends with ;.

The items in the enum can be assigned with specific values to make them more indicative (e.g., +, -):

public enum Sign {
    POSITIVE('+'),
    NEGATIVE('-');

    private final char value;

    Sign(char value) {
        this.value = value;
    }

    /** @return the value of the corresponding item. */
    public char value() {
        return value;
    }
}

• L5: final makes this field a constant, not a variable, such that the value cannot be updated later.

• L8: this points to the object created by this constructor.

• L11: @return adds a javadoc comment about the return value of this method.

Why should the member field value be private in the above example?

Note that value in L8 indicates the local parameter declared in the constructor whereas value in L13 indicates the member field declared in L5.

Limit of Interface

In SignedNumeral, it would be convenient to have a member field that indicates the sign of the numeral:

public interface SignedNumeral<T extends SignedNumeral<T>> extends Numeral<T> {
    Sign sign = Sign.POSITIVE;
    ...

• L2: All member fields of an interface are static and public.

Can you declare a member field in an interface without assigning a value?

Given the sign field, it may seem intuitive to define flipSign() as a default method:

/** Flips the sign of this numeral. */
default void flipSign() {
    sign = (sign == Sign.POSITIVE) ? Sign.NEGATIVE : Sign.POSITIVE;
}

• L3: condition ? A : B is a ternary expression that returns A if the condition is true; otherwise, it returns B.

Is there any advantage of using a ternary operator instead of using a regular if statement?

Unfortunately, this gives a compile error because sign is a constant whose value cannot be reassigned. An interface is not meant to define so many default methods, which were not even allowed before Java 8. For such explicit implementations, it is better to declare SignedNumeral as an abstract class instead.

Abstract Class

Let us turn SignedNumeral into an abstract class:

public abstract class SignedNumeral<T extends SignedNumeral<T>> implements Numeral<T> {
    /** The sign of this numeral. */
    protected Sign sign;

    /**
     * Create a signed numeral.
     * the default sign is {@link Sign#POSITIVE}.
     */
    public SignedNumeral() {
        this(Sign.POSITIVE);
    }

    /**
     * Create a signed numeral.
     * @param sign the sign of this numeral.
     */
    public SignedNumeral(Sign sign) {
        this.sign = sign;
    }
    ...

• L9: the default constructor with no parameter.

• L17: another constructor with the sign parameter.

• L10: this() calls the constructor in L17.

Why calling this(Sign.POSITIVE) in L10 instead of stating this.sign = Sign.POSITIVE?

    ...
    /** @return true if this numeral is positive; otherwise, false. */
    public boolean isPositive() {
        return sign == Sign.POSITIVE;
    }

    /** @return true if this numeral is negative; otherwise, false. */
    public boolean isNegative() {
        return sign == Sign.NEGATIVE;
    }

    /** Flips the sign of this numeral. */
    public void flipSign() {
        sign = isPositive() ? Sign.NEGATIVE : Sign.POSITIVE;
    }
    
    /**
     * Subtracts `n` from this numeral.
     * @param n the numeral to be subtracted.
     */
    public void subtract(T n) {
        n.flipSign(); add(n); n.flipSign();
    }

    /**
     * Multiplies `n` to this numeral.
     * @param n the numeral to be multiplied.
     */
    public abstract void multiply(T n);
}

• L29: abstract indicates that this is an abstract method.

Member fields and methods in an abstract class can be decorated by any modifiers, which need to be explicitly coded.

Is there anything that is not allowed in an abstract class but allowed in a regular class?

In summary, SignedNumeral includes 2 abstract methods, add() inherited from Numeral, and multiply() declared in this class.

Can you define an abstract class or an interface without declaring an abstract method?

Contents

Resources

• Main:

• Test:

References

Abstract Sort

Let us create an abstract class AbstractSort:

public abstract class AbstractSort<T extends Comparable<T>> {
    private final Comparator<T> comparator;
    protected long comparisons;
    protected long assignments;

    /** @param comparator specifies the precedence of comparable keys. */
    public AbstractSort(Comparator<T> comparator) {
        this.comparator = comparator;
        resetCounts();
    }

    /** @return the total number of comparisons performed during sort. */
    public long getComparisonCount() {
        return comparisons;
    }

    /** @return the total number of assignments performed during sort. */
    public long getAssignmentCount() {
        return assignments;
    }

    public void resetCounts() {
        comparisons = assignments = 0;
    }
}

• L2-4: member fields:

  • comparator: specifies the precedence of comparable keys.

  • comparisons: counts the number of comparisons performed during sorting.

  • assignments: counts the number of assignments performed during sorting.

Let us define three helper methods, compareTo(), assign(), and swap():

/**
 * @param array an array of comparable keys.
 * @param i     the index of the first key.
 * @param j     the index of the second key.
 * @return array[i].compareTo(array[j]).
 */
protected int compareTo(T[] array, int i, int j) {
    comparisons++;
    return comparator.compare(array[i], array[j]);
}

/**
 * array[index] = value.
 * @param array an array of comparable keys.
 * @param index the index of the array to assign.
 * @param value the value to be assigned.
 */
protected void assign(T[] array, int index, T value) {
    assignments++;
    array[index] = value;
}

/**
 * Swaps array[i] and array[j].
 * @param array an array of comparable keys.
 * @param i     the index of the first key.
 * @param j     the index of the second key.
 */
protected void swap(T[] array, int i, int j) {
    T t = array[i];
    assign(array, i, array[j]);
    assign(array, j, t);
}

• L7: compares two keys in the array and increments the count.

• L18: assigns the value to the specific position in the array and increments the count.

• L29: swaps the values of the specific positions in the array by calling the assign() method.

These helper methods allow us to analyze the exact counts of those operations performed by different sorting algorithms.

How is it different to benchmark runtime speeds from counting these two operations?

Finally, let us define the default sort() that calls an overwritten abstract method, sort():

/**
 * Sorts the array in ascending order.
 * @param array an array of comparable keys.
 */
public void sort(T[] array) {
   sort(array, 0, array.length);
}

/**
 * Sorts the array[beginIndex:endIndex].
 * @param array      an array of comparable keys.
 * @param beginIndex the index of the first key to be sorted (inclusive).
 * @param endIndex   the index of the last key to be sorted (exclusive).
 */
abstract public void sort(T[] array, int beginIndex, int endIndex);

• L5: calls the abstract method sort() that overwrites it.

• L15: sorts the array in the range of (beginIndex, endIndex) as specified in comparator.

When would it be useful to sort a specific range in the input array?

Test: LongInteger()

Let us create a testing class called LongIntegerTest and make a unit test for the constructors:

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;

public class LongIntegerTest {
    @Test
    public void testConstructors() {
        // default constructor
        assertEquals("0", new LongInteger().toString());

        // constructor with a string parameter
        assertEquals("12", new LongInteger("12").toString());
        assertEquals("34", new LongInteger("+34").toString());
        assertEquals("-56", new LongInteger("-56").toString());
        assertEquals("-0", new LongInteger("-0").toString());

        // copy constructor
        assertEquals("12", new LongInteger(new LongInteger("12")).toString());
        assertEquals("-34", new LongInteger(new LongInteger("-34")).toString());
    }
}

• L6: the @Test annotation indicates that this method is used for unit testing.

• L7: methods used for unit testing must be public.

• L8: tests the default constructor

  • assertEquals(): compares two parameters where the left parameter is the expected value and the right parameter is the actual value.

• L12-15: tests the constructor with a string parameter.

• L18-19: tests the copy constructor.

When should we use import static instead of import?

When you run this test, you see a prompt similar to the followings:

Tests passed: 1 of 1 test

Test: multiply()

Let us define another method for testing the multiply() method:

@Test
public void testMultiply() {
    LongInteger a = new LongInteger("123456789");

    a.multiply(new LongInteger("1"));
    assertEquals("123456789", a.toString());

    a.multiply(new LongInteger("-1"));
    assertEquals("-123456789", a.toString());

    a.multiply(new LongInteger("-1234567890123456789"));
    assertEquals("152415787517146788750190521", a.toString());

    a.multiply(new LongInteger("0"));
    assertEquals("0", a.toString());

    a.multiply(new LongInteger("-0"));
    assertEquals("-0", a.toString());
}

• L11-12: a can hold the integer 152415787517146788750190521 ($\approx 2^{87}$), which is much larger than the maximum value of long that is $2^{63}-1$.

Test: compareTo()

Let us define a method for testing the compareTo() method:

@Test
public void testCompareTo() {
    assertTrue(0 < new LongInteger("0").compareTo(new LongInteger("-0")));
    assertTrue(0 > new LongInteger("-0").compareTo(new LongInteger("0")));

    assertTrue(0 < new LongInteger("12").compareTo(new LongInteger("-34")));
    assertTrue(0 > new LongInteger("-12").compareTo(new LongInteger("34")));

    assertTrue(0 > new LongInteger("-34").compareTo(new LongInteger("12")));
    assertTrue(0 < new LongInteger("34").compareTo(new LongInteger("-12")));
}

• assertTrue(): passes if the parameter returns true.

A priority queue (PQ) is a data structure that supports the following two operations:

• add(): adds a comparable key to the PQ.

• remove(): removes the key with the highest (or lowest) priority in the PQ.

A PQ that removes the key with the highest priority is called a maximum PQ (max-PQ), and with the lowest priority is called a minimum PQ (min-PQ).

Does a priority queue need to be sorted at all time to support those two operations? What are the use cases of priority queues?

Abstract Priority Queue

Let us define AbstractPriorityQueue that is an abstract class to be inherited by all priority queues:

public abstract class AbstractPriorityQueue<T extends Comparable<T>> {
    protected final Comparator<T> priority;

    /**
     * Initializes this PQ as either a maximum or minimum PQ.
     * @param priority if {@link Comparator#naturalOrder()}, this is a max PQ;
     *                 if {@link Comparator#reverseOrder()}, this is a min PQ.
     */
    public AbstractPriorityQueue(Comparator<T> priority) {
        this.priority = priority;
    }
}

• L1: declares the generic type T that is the type of input keys to be stored in this PQ.

  • T must be comparable by its priority.

• L2: is a comparator that can compare keys of the generic type T.

  • final: must be initialized in every constructor.

  • Comparators: naturalOrder(), reverseOrder().

• L6: the javadoc {@link} hyperlinks to the specified methods.

What are comparable data types in Java? Can you define your own comparator?

Let us define three abstract methods, add(), remove(), and size() in AbstractPriorityQueue:

/**
 * Adds a comparable key to this PQ.
 * @param key the key to be added.
 */
abstract public void add(T key);

/**
 * Removes the key with the highest/lowest priority if exists.
 * @return the key with the highest/lowest priority if exists; otherwise, null.
 */
abstract public T remove();

/** @return the size of this PQ. */
abstract public int size();

Given the abstract methods, we can define the regular method isEmpty():

/** @return true if this PQ is empty; otherwise, false. */
public boolean isEmpty() {
    return size() == 0;
}

Lazy Priority Queue

Let us define LazyPriorityQueue whose core methods satisfy the following conditions:

• add(): takes$O(1)$to add a key to the PQ.

• remove(): takes$O(n)$ to remove the key with the highest/lowest priority from the PQ.

In other words, all the hard work is done at the last minute when it needs to remove the key.

public class LazyPriorityQueue<T extends Comparable<T>> extends AbstractPriorityQueue<T> {
    private final List<T> keys;

    /** Initializes this as a maximum PQ. */
    public LazyPriorityQueue() {
        this(Comparator.naturalOrder());
    }

    /** @see AbstractPriorityQueue#AbstractPriorityQueue(Comparator). */
    public LazyPriorityQueue(Comparator<T> priority) {
        super(priority);
        keys = new ArrayList<>();
    }
    
    
    @Override
    public int size() {
        return keys.size();
    }
}

• L1: declares T and passes it to its super class, AbstractPriorityQueue.

• L2: defines a list to store input keys.

• L17-19: overrides the size() method.

Can you add keys to the member field keys when it is declared as final (a constant)? Why does all constructors in LazyPriorityQueue need to call the super constructor?

We then override the core methods, add() and remove():

/**
 * Appends a key to {@link #keys}.
 * @param key the key to be added.
 */
@Override
public void add(T key) {
    keys.add(key);
}

/**
 * Finds the key with the highest/lowest priority, and removes it from {@link #keys}.
 * @return the key with the highest/lowest priority if exists; otherwise, null.
 */
@Override
public T remove() {
    if (isEmpty()) return null;
    T max = Collections.max(keys, priority);
    keys.remove(max);
    return max;
}

• L6-8: appends a key to the list in $O(1)$.

• L15-20: removes a key to the list in $O(n)$.

  • L16: edge case handling.

  • L17: finds the max-key in the list using Collections.max() in $O(n)$.

  • L18: removes a key from the list in $O(n+n) = O(n)$.

Is ArrayList the best implementation of List for LazyPriorityQueue? Why does remove() in L18 cost $O(n+n)$?

Eager Priority Queues

Let us define EagerPriorityQueue whose core methods satisfy the following conditions:

• add(): takes$O(n)$to add a key to the PQ.

• remove(): takes$O(1)$ to remove the key with the highest/lowest priority from the PQ.

In other words, all the hard work is done as soon as a key is added.

What are the situations that LazyPQ is preferred over EagerPQ and vice versa?

public class EagerPriorityQueue<T extends Comparable<T>> extends AbstractPriorityQueue<T> {
    private final List<T> keys;

    public EagerPriorityQueue() {
        this(Comparator.naturalOrder());
    }

    public EagerPriorityQueue(Comparator<T> priority) {
        super(priority);
        keys = new ArrayList<>();
    }
    
    @Override
    public int size() {
        return keys.size();
    }
}

• The implementations of the two constructors and the size() method are identical to the ones in LazyPriorityQueue.

Should we create an abstract class that implements the above code and make it as a super class of LazyPQ and EagerPQ? What level of abstraction is appropriate in object-oriented programming?

We then override the core methods, add() and remove():

/**
 * Adds a key to {@link #keys} by the priority.
 * @param key the key to be added.
 */
@Override
public void add(T key) {
    // binary search (if not found, index < 0)
    int index = Collections.binarySearch(keys, key, priority);
    // if not found, the appropriate index is {@code -(index +1)}
    if (index < 0) index = -(index + 1);
    keys.add(index, key);
}

/**
 * Remove the last key in the list.
 * @return the key with the highest priority if exists; otherwise, {@code null}.
 */
@Override
public T remove() {
    return isEmpty() ? null : keys.remove(keys.size() - 1);
}

• L6-12: inserts a key to the list in $O(n)$ .

  • L8: finds the index of the key to be inserted in the list using binary search in $O(\log n)$.

  • L10: reverse engineers the return value of Collections.binarySearch() .

  • L11: inserts the key at the index position in $O(n)$.

• L19-21: removes a key from the list in $O(1)$.

What are the worst-case complexities of add() and remove() in LazyPQ and EagerPQ in terms of assignments and comparison?

Time

Let us define a static nested class Time under PriorityQueueTest that stores runtimes for the add() and remove() methods in any PQ:

static class Time {
    long add = 0;
    long remove = 0;
}

What is the advantage of defining static nested class over non-static nested class?

Runtime Estimation

Let us define addRuntime() that estimates the runtime for add() and remove()for a particular PQ:

<T extends Comparable<T>> void addRuntime(AbstractPriorityQueue<T> queue, Time time, List<T> keys) {
    long st, et;

    // runtime for add()
    st = System.currentTimeMillis();
    keys.forEach(queue::add);
    et = System.currentTimeMillis();
    time.add += et - st;

    // runtime for remove()
    st = System.currentTimeMillis();
    while (!queue.isEmpty()) queue.remove();
    et = System.currentTimeMillis();
    time.remove += et - st;
}

• L5-8: estimates the runtime for add():

  • L5: gets the snapshot of the starting time using currentTimeMillis().

  • L7: gets the snapshot of the ending time using currentTimeMillis().

  • L8: accumulates the runtime to times.add.

• L11-14: estimates the runtime for remove().

Is the approach using currentTimeMillis() a proper way of benchmarking the speed?

We then define benchmark() that estimates the speeds of multiple PQs using the same lists of keys by calling addRuntime():

<T extends Comparable<T>> Time[] benchmark(AbstractPriorityQueue<T>[] queues, int size, int iter, Supplier<T> sup) {
    Time[] times = Stream.generate(Time::new).limit(queues.length).toArray(Time[]::new);

    for (int i = 0; i < iter; i++) {
        List<T> keys = Stream.generate(sup).limit(size).collect(Collectors.toList());
        for (int j = 0; j < queues.length; j++)
            addRuntime(queues[j], times[j], keys);
    }

    return times;
}

• L1: method declaration:

  • AbstractPriorityQueue[]: It is unusual to declare an array of objects involving generics in Java (you will see the unique use case of it in the testSpeedAux() method).

  • Supplier: passes a function as a parameter that returns a key of the generic type T.

• L2: generates an array of Time using several stream operations. The dimension of times[] is the same as the dimension of queues such that times[i] accumulates the speeds taken by the queue[i], respectively.

  • generate(): creates a stream specified by the supplier.

  • limit(): creates a stream with a specific size.

  • toArray(): returns an array of the specific type.

• L4: benchmarks the PQs multiple times as specified by iter.

• L5: generates the list of keys specified by the supplier sup.

• L6-7: estimate the runtimes by using the same list of keys for each PQ.

Why do we need to benchmark the priority queues multiple times?

Benchmark

Let us define testSpeedAux() that takes multiple PQs and prints out the benchmarking results:

@SafeVarargs
final void testRuntime(AbstractPriorityQueue<Integer>... queues) {
    final int begin_size = 1000;
    final int end_size = 10000;
    final int inc = 1000;
    final Random rand = new Random();

    for (int size = begin_size; size <= end_size; size += inc) {
        // JVM warm-up
        benchmark(queues, size, 10, rand::nextInt);
        // benchmark all priority queues with the same keys
        Time[] times = benchmark(queues, size, 1000, rand::nextInt);

        StringJoiner joiner = new StringJoiner("\t");
        joiner.add(Integer.toString(size));
        joiner.add(Arrays.stream(times).map(t -> Long.toString(t.add)).collect(Collectors.joining("\t")));
        joiner.add(Arrays.stream(times).map(t -> Long.toString(t.remove)).collect(Collectors.joining("\t")));
        System.out.println(joiner.toString());
    }
}

• L1: annotates safeVarargs indicating that this method takes vararg parameters.

• L2: declares a final method that cannot be overridden by its subclasses.

  • It can take a 0-to-many number of abstract PQs.

  • The type of queues is AbstractPriorityQueue<Integer>[] such that it can be directly passed to the benchmark() method.

• L5: creates a random generator.

• L8: benchmarks different sizes of PQs.

• L10: warms up the Java Virtual Machine (JVM) before the actual benchmarking.

  • rand::nextnt that is equivalent to the lambda expression of () -> rand.nextInt().

• L12: benchmarks add() and remove() in the PQs.

• L14-18: prints the benchmark results.

  • L14: uses StringJoiner to concatenate strings with the specific delimiter.

  • L16: exercise.

Why is it recommended to declare the method final if it takes vararg parameters? Why does JVM need to be warmed-up before the actual benchmarking? Why should you use StringJoiner instead of concatenating strings with the + operator?

Speed Comparison

The followings show runtime comparisons between LazyPQ, EagerPQ, and BinaryHeap:

A binary heap is a PQ that takesfor both add() and remove(), where keys are stored in a balanced binary tree in which every node has a higher priority than its children (when used as a max-PQ).

When should we use a binary heap over a lazy PQ or an eager PQ?

Balanced Binary Tree

A balanced binary tree can be implemented by a list such that given the 'th key in the list:

• The index of its parent:

• The index of its left child: .

• The index of its right child: .

• e.g., given the list [1, 2, 3, 4, 5], 1 is the root, 2 and 3 are the left and right children of 1, and 4 and 5 are the left and right children of 2, respectively.

Is the tree represented by the list [1, 2, 3, 4, 5] balanced?

Implementation

Let us create the class inheriting AbstractPriorityQueue:

• L11: adding null as the first item makes it easier to calculate the indices of parents and children.

• L16: keys has the extra item of null from L11 that is not an input key.

How does adding null make the calculation of the indices easier?

Additionally, let us define the helper method compare() that compares two keys in the list:

• L8: calls the compare() method in the member field priority declared in the super class.

Add() with Swim

The add() method in a heap uses the operation called swim as follows:

• L3: appends the new key to the list.

• L7-10: keeps swimming until the list becomes a heap:

  • L8: compares the new key to its parent if exists.

  • L9: if the new key has a higher priority than its parent, them.

How many keys are compared at most for the `add operation?

Remove() with Sink

The remove() method in a heap uses the operation called sink as follows:

• L3: checks if the heap is empty.

• L4: swaps the root and the last key in the list.

• L3: removes the (swapped) last key with the highest priority in this heap.

• L10-16: keeps sinking until the list becomes a heap:

  • L12: finds the child with a higher priority.

  • L13: breaks if the parent has a higher priority than the child.

  • L14: swaps if the child has a higher priority than the parent.

How many keys are compared at most for the remove operation?

Selection-based Sort

Selection-based sorting algorithms take the following steps:

• For each key where and :

  • Search the maximum key where .

  • Swap and

The complexities differ by different search algorithms:

Selection Sort uses linear search to find the minimum (or maximum) key, whereas Heap Sort turns the input array into a heap, so the search complexity becomes instead of .

Can the search be faster than ?

Selection Sort

Let us create the class inheriting AbstractSort:

Let us then override the sort() method:

• L3-12:

  • L3: iterates all keys within the range .

  • L4-9: finds the index of the maximum key within the range .

  • L11: swaps the maximum key with the last key in the range .

How does the sort() method work with Comparator.reverseOrder()?

Heap Sort

Let us create the class inheriting AbstractSort:

Before we override the sort() method, let us define the following helper methods:

• L1-7: finds the right position of the k'th key by using the sink operation.

• L9-11: finds the parent index of the k'th key given the beginning index.

• L13-15: finds the left child index of the k'th key given the beginning index.

How is this sink() method different from the one in the class?

Finally, we override the sort() method:

• L4-5: turns the input array into a heap :

  • L4: iterates from the parent of the key in the ending index .

  • L5: sinks the key .

• L8-11: selection sort :

  • L8: iterates all keys within the range .

  • L9: swaps the maximum key with the beginning key in the range .

  • L10: sinks to heapify .

What is the worst-case scenario for Selection Sort and Heap Sort?

Insertion-based Sort

Insertion-based sorting algorithms take the following steps:

• For each key where and :

  • Keep swapping and until .

The complexities differ by different sequences:

Insertion Sort

Let us create the class inheriting AbstractSort:

Let us then define an auxiliary method, sort():

• L4: iterates keys in the input array .

• L5: compares keys in the sublist of the input array .

• L6: swaps the two keys.

Given the auxiliary method, the sort() method can be defined as follows where h = 1:

How many swaps does Insertion Sort make for the following array? [7, 1, 2, 3, 4, 5, 6, 14, 8, 9, 10, 11, 12, 13, 0]

Shell Sort

Gap Sequence

Shell Sort groups keys whose gap is defined by a particular :

• Knuth:

• Hibbard:

• Pratt:

• Shell: , where

For the above example, by using the Hibbard sequence, it first groups keys whose gap is 7:[7, 14, 0], [1, 8], [2, 9], [3, 10], [4, 11], [5, 12], [6, 13]

It then sorts each group using Insertion Sort, which results in the following array: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

The above procedure is repeated for gaps 3 and 1; however, the array is already sorted, so no more swapping is necessary.

Implementation

Let us create an abstract class, , inheriting AbstractSort:

• L2: stores a particular gap sequence.

• L7: pre-populate the gap sequence that can handle the input size up to 10000.

Then, let us define two abstract methods, populateSequence() and getSequenceStartIndex():

• L5: populates a particular sequence for the input size n.

• L11: returns the index of the first gap to be used given the input size n.

Let us then override the sort() method:

• L4: should not re-populate the sequence unless it has to.

• L6: iterates the sequence where is the number of gaps in the sequence.

• L7: sorts the gap group by using the auxiliary method.

Knuth Sequence

Let us create the class that populates the Knuth Sequence for ShellSort:

The two abstract methods can be overridden as follows:

• L2: populates the Knuth sequence up to the gap .

• L13: returns the index of the first key .

Why should we use as the largest gap in the sequence?

Demonstration

Unit Tests & Benchmarks

The codes for unit testing and benchmarking are available in :

Contents

1. Abstraction

2. Comparison-based Sort

3. Divide & Conquer Sort

4. Distribution-based Sort

5. Quiz

6. Homework

Resources

• Main: src/main/java/edu/emory/cs/sort

• Test: src/test/java/edu/emory/cs/sort

References

• Comparison-based Algorithms

  • Selection Sort $\rightarrow$ Heap Sort

  • Insertion Sort $\rightarrow$ Shell Sort

• Divide and Conquer Algorithms

  • Merge Sort $\rightarrow$ Tim Sort

  • Quick Sort $\rightarrow$ Intro Sort

• Distribution-based Algorithms

  • Bucket Sort

  • Radix Sort

Unlike comparison-based algorithms in Sections 3.2 and 3.3, distribution-based sorting algorithms do not make comparisons between keys in the input array; instead, they distribute keys into ordered buckets and merge keys in the buckets.

Bucket Sort

Let us create an abstract class, AbstractBucketSort inheriting AbstractSort:

public abstract class BucketSort<T extends Comparable<T>> extends AbstractSort<T> {
    protected List<Deque<T>> buckets;

    /** @param numBuckets the total number of buckets. */
    public BucketSort(int numBuckets) {
        super(null);
        buckets = Stream.generate(ArrayDeque<T>::new).limit(numBuckets).collect(Collectors.toList());
    }
}

• L2: declares a list of buckets where each bucket is represented by a Deque.

• L6: does not pass any comparator to AbstractSort since no comparison is needed.

• L7: creates a pre-defined number of buckets.

What kind of input keys can work with distribution-based sorting algorithms?

We then define a helper method sort():

/**
 * @param array       the input array.
 * @param beginIndex  the index of the first key to be sorted (inclusive).
 * @param endIndex    the index of the last key to be sorted (exclusive).
 * @param bucketIndex takes a key and returns the index of the bucket that the key to be added.
 */
protected void sort(T[] array, int beginIndex, int endIndex, Function<T, Integer> bucketIndex) {
    // add each element in the input array to the corresponding bucket
    for (int i = beginIndex; i < endIndex; i++)
        buckets.get(bucketIndex.apply(array[i])).add(array[i]);

    // merge elements in all buckets to the input array
    for (Deque<T> bucket : buckets) {
        while (!bucket.isEmpty())
            array[beginIndex++] = bucket.remove();
    }
}

• L7: bucketIndex is a function that takes a comparable key and returns the appropriate bucket index of the key.

• L9-10: adds the keys within the range in the input array to the buckets.

• L13-16: puts all keys in the buckets back to the input array while keeping the order.

How many assignments are made by the sort() method in BucketSort?

Integer Bucket Sort

Let us create the IntegerBucketSort class inheriting BucketSort that sorts integers within a specific range in ascending order:

public class IntegerBucketSort extends BucketSort<Integer> {
    private final int MIN;

    /**
     * @param min the minimum integer (inclusive).
     * @param max the maximum integer (exclusive).
     */
    public IntegerBucketSort(int min, int max) {
        super(max - min);
        MIN = min;
    }
}

• L2: takes the smallest integer in the range.

• L8: passes the number of buckets, max - min, to be initialized to the super constructor.\

We then override the sort() method:

@Override
public void sort(Integer[] array, int beginIndex, int endIndex) {
    sort(array, beginIndex, endIndex, key -> key - MIN);
}

• L3: passes a lambda expression that takes key and returns key - MIN indicating the index of the bucket that key should be assigned to.

Is it possible to implement DoubleBucketSort that can handle double instead of integer keys?

Radix Sort

Let us create an abstract class, RadixSort, inheriting BucketSort<Integer>:

public abstract class RadixSort extends BucketSort<Integer> {
    public RadixSort() {
        super(10);
    }
    
    protected int getMaxBit(Integer[] array, int beginIndex, int endIndex) {
        Integer max = Arrays.stream(array, beginIndex, endIndex).reduce(Integer::max).orElse(null);
        return (max != null && max > 0) ? (int)Math.log10(max) + 1 : 0;
    }
}

• L3: creates 10 buckets to sort any range of integers.

• L6: returns the order of the most significant digit in the input array.

LSD Radix Sort

Let us create the LSDRadixSort class inheriting RadixSort that sorts the integer keys from the least significant digit (LSD) to the most significant digit (MSD):

public class LSDRadixSort extends RadixSort {
    @Override
    public void sort(Integer[] array, int beginIndex, int endIndex) {
        int maxBit = getMaxBit(array, beginIndex, endIndex);
        for (int bit = 0; bit < maxBit; bit++) {
            int div = (int)Math.pow(10, bit);
            sort(array, beginIndex, endIndex, key -> (key / div) % 10);
        }
    }
}

• L5: iterates from LSD to MSD.

• L7: the lambda expression returns the bucket index, the value in the $n$'th significant digit.

Benchmarks

The followings compare runtime speeds between advanced sorting algorithms where the input arrays consist of random integer keys:

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:

Here is the expected output given the sample input:

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 . The implementation of this strategy is provided to establish the baseline: . Your goal is to design a sorting mechanism that gives a noticeable speed-up over this baseline.

Tasks

• Create a class inheriting under the package .

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

  • 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 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 .

Results

Baseline: 20697

• Cannot run: 7

• Extremely slow: 6

• Code not found: 1

Divide & Conquer

• Divide the problem into sub-problems (recursively).

• Conquer sub-problems, which effectively solve the super problem.

Why do people ever want to use QuickSort?

Merge Sort

• Divide the input array into two sub-arrays.

• Sort each of the sub-arrays and merge them into the back.

Let us create the class inheriting AbstractSort:

• L2: holds the copy of the input array.

Let us then override the sort() method that calls the helper method:

• L4-5: increases the size of the temp array if necessary.

  • L5: unchecked type Object to T[].

What is the advantage of declaring the member field temp?

The helper method can be defined as follows:

• L11: sorts the left sub-array.

• L12: sorts the right sub-array.

• L13: merges the left and right sub-arrays.

Finally, the merge() method can be defined as follows:

• L10-11: copies the input array to the temporary array and counts the assignments.

• L14-15: no key left in the 1st half.

• L16-17: no key left in the 2nd half.

• L18-19: the 2nd key is greater than the 1st key.

• L20-21: the 1st key is greater than or equal to the 2nd key.

How many assignments are made for the number of keys by the above version of MergeSort?

Quick Sort

• Pick a pivot key in the input array.

• Exchange keys between the left and right partitions such that all keys in the left and right partitions are smaller or bigger than the pivot key, respectively.

• Repeat this procedure in each partition, recursively.

Let us create the class inheriting AbstractSort:

Let us then override the sort() method:

• L3: stops when the pointers are crossed.

• L6: sorts the left partition.

• L7: sorts the right partition.

The partition() method can be defined as follows:

• L5: finds the left pointer where endIndex > fst > pivot.

• L6: finds the right pointer where beginIndex < snd < pivot.

• L7: the left and right pointers are crossed.

• L8: swaps between keys in the left and right partitions.

• L11: swaps the keys in the beginIndex and pivot.

Intro Sort

• Although Quick Sort is the fastest on average, the worst-case complexity is .

• sorting algorithms that guarantee faster worst-case complexities than Quick Sort: Quick Sort for random cases and a different algorithm for the worst case.

How can we determine if Quick Sort is meeting the worse-case?

Let us define the IntroSoft class inheriting QuickSort:

• L2: declares a sorting algorithm to handle the worst cases.

• L14: resets the counters for both the main and auxiliary sorting algorithms.

We then override the sort() method by passing the maximum depth to the auxiliary method:

• L9: returns as the maximum depth.

Finally, the auxiliary method sort() can be defined as follows:

• L4-5: switches to the other sorting algorithm if the depth of the partitioning exceeds the max depth.

Does the max-depth need to be set to ?

Benchmarks

The following shows runtime speeds, assignment costs, and comparison costs between several sorting algorithms for the random, best, and worst cases.

Coding

Shell Sort: Hibbard

• Create the class under the package that inherits .

• Override the populateSequence() and getSequenceStartIndex() methods such that it performs Shell Sort by using the Hibbard sequence: .

• Feel free to use the code in .

Radix Sort: MSD

• Create the class under the package that inherits .

• Override the sort() method such that it performs Radix Sort from the most significant digit (MSD) to the least significant digit (LSD).

• Feel free to use the code in .