My Quick Sort

Required Skills Inventory

• Implement a quicksort algorithm
• Implement a recursive algorithm

You are not allowed to use any of the standard Java collection types for this assignment. Do not import any Java standard library features from java.util.

Problem Description and Given Info

For this assignment you are given the following Java source code files:

• IList.java (This file is complete - make no changes to this file)
• MyArrayList.java (This file is complete - make no changes to this file)
• MySorts.java (You must complete this file)
• Main.java (You may use this file to write code to test your quicksort code)

You must complete the public class named MySorts.java with methods as defined below.

Note that your quicksort algorithm must be implemented to operate on IList objects, as defined in the given files iList.java and MyArrayList.java.

Structure of the MySorts Fields

Your quicksort algorithm should require no static (or instance) fields in your MySorts class.

Structure of the MySorts quicksort Methods

Your MySorts class must implement the following methods:

• a public static method named quicksort that takes an object of type IList< Integer > as an argument and returns nothing
• a private static method named quicksortHelper that takes an object of type IList< Integer > ant two int arguments and returns nothing
• a private static method named partition that takes an object of type IList< Integer > and two int arguments and returns an int
• a private static method named swap that takes an object of type IList< Integer > and two int arguments and returns nothing

You may implement any additional methods that you may need.

Additional Information

MySorts quicksort algorithm

1. the quicksort method will take a reference to an IList< Integer > object as its only argument. This method will call the quicksortHelper method to do the actual work of sorting the list. This is the method that one would call to apply the quicksort algorithm to a list of values. By the time this method returns, the values in the argument IList should be sorted.

2. the quicksortHelper method is a recursive method that will implement the actual quicksort algorithm. The first argument is a reference to the list of values that is to be sorted. The second and third int arguments are the index values representing the current partition of the list to be sorted. For example, given an IList (named list) of 20 values, quicksortHelper(list, 5, 15) would quicksort the partition of the list staring at index 5 and ending at index 15.

3. the partition method will take as its first argument, a reference to the list of values that is to be partitioned. The second and third int arguments are the index values representing the current section of the list to be partitioned.

• For example, given an IList (named list) of 20 values, partition(list, 5, 15) would partition the section of the list staring at index 5 and ending at index 15. This method must return the index at which the pivot value was finally placed at the end of this partition operation.
• For this assignment, you should always use the last int argument value as the initial pivot index for the partition operation. For example, given an IList (named list) of 20 values, partition(list, 5, 15) would use the high index value 15 as the index of the pivot value for this partition operation.

4. the swap method will take as its first argument, a reference to an IList object. The second and third int arguments are the indexes of the two items in the list to have their locations swapped. For example, given an IList (named list) of these 5 values {4, 2, 5, 1, 3}, swap(list, 0, 3) would swap the values currently stored at indexes 0 and 3, and the list would now look like this {1, 2, 5, 4, 3}.

Starter Codes

IList.java

public interface IList< T extends Comparable< T > > {
/**
Adds an element at the end of the list.
*/
public void add(T item);
/**
Stores a new item at a specified index
Throws NoSuchElementException if index is out of bounds.
*/
public void set(int index, T item);
/**
Inserts an element at the specified index
Throws NoSuchElementException if index is out of bounds.
*/
public void insert(int index, T item);
/**
Removes the element at the specified index
Throws NoSuchElementException if index is out of bounds.
*/
public void remove(int index);

/**
Returns the element at the specified index
Throws NoSuchElementException if index is out of bounds.
*/
public T get(int index);

/**
Returns the size of the list.
@return the number of elements in the list
*/
public int size();
}

MyArrayList.java

import java.util.ArrayList;

public class MyArrayList< T extends Comparable< T > > implements IList< T > {
private ArrayList< T > list = new ArrayList< T >();

@Override
public void add(T item) {
list.add(item);
}

@Override
public int size() {
return list.size();
}

@Override
public T get(int index) {
return list.get(index);
}

@Override
public void set(int index, T item) {
list.set(index, item);
}

@Override
public void insert(int index, T item) {
list.add(index, item);
}

@Override
public void remove(int index) {
list.remove(index);
}
}