ByteMan2021 ByteMan2021 - 4 months ago 5
Java Question

Implementing Quicksort to sort a list with restricted/no access to its contents

I'm trying to implement the Quicksort algorithm to sort a list which does not directly allow access to its elements. I'm supposed to sort the

list
using only two methods:
swap
and
compare
, without using the
toString
method provided only for debugging purposes. I have chosen the middle element of the sub-array as the pivot. Comparisons are made using the
Comparator
object passed during the function call.

I ran a few JUnit tests with randomly generated lists out of which almost all are getting sorted (Update: After running a few more tests, I found many more cases where the algorithm failed). However, (one of the cases where) my algorithm fails when I try to
partition
a 4 element sub-array with the keys arranged in this order: [smallest, biggest, big, small]

Here's the JUnitTest passing the list - [0, 3, 2 ,1]:

private static final Comparator<Integer> INTEGER_COMPARATOR = new IntegerComparator();
@Test
public void customTest() {
SwapList<Integer> customList;
AbstractSorter<Integer> customSorter;
customList = new ArrayBasedSwapList<Integer>(new Integer[] { 0, 3, 2, 1 });
customSorter = new QuickSorter<Integer>(customList,
INTEGER_COMPARATOR);
SwapList<Integer> result = customSorter.sort();
System.out.println("Result: " + result.toString());
assertTrue(result.isSorted(INTEGER_COMPARATOR));
}


and the
IntegerComparator
class used:

package comparators;

import java.util.Comparator;

/**
* Comparator on two Integers in the usual order.
*
* @author liberato
*
*/
public class IntegerComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
}
}


I put some println statements and added an
indent
variable in the code for debugging purposes. Here's the output after running the test:

quicksort(0, 3)
Inside partition(0, 3)
pivotIndex = 1
Initially: [0, 3, 2, 1]
i = 1, pivotIndex = 1, j = 3
After 1st swap: [0, 1, 2, 3]
Pivot was swapped
i = 2, pivotIndex = 3, j = 2
After 2nd swap: [0, 1, 3, 2]
i = 2, pivotIndex = 3, j = 2
p = 2
quicksort(0, 1)
Inside partition(0, 1)
pivotIndex = 0
Initially: [0, 1, 3, 2]
i = 0, pivotIndex = 0, j = 0
After 2nd swap: [0, 1, 3, 2]
i = 0, pivotIndex = 0, j = 0
p = 0
quicksort(0, -1)
quicksort(1, 1)
quicksort(3, 3)


Result: [0, 1, 3, 2]

The problem is inside
partition(0, 3)
where the second swap statement reverses the effect of the first swap. Can someone help with correcting my quick sort algorithm? I should perhaps add an
if
statement so that the second swap occurs only if element at index
i
> element at
pivotIndex
?

Here's the code:

package sorters;

import java.util.Comparator;

import structures.SwapList;

public class QuickSorter<T> extends AbstractSorter<T> {
//String indent = "";
public QuickSorter(SwapList<T> list, Comparator<T> comparator) {
super(list, comparator);
}

@Override
public SwapList<T> sort() {
quicksort(0, list.size() - 1);
return list;
}

private void quicksort(int firstIndex, int lastIndex) {
//System.out.println(indent + "quicksort(" + firstIndex + ", " + lastIndex + ")");
//indent+=" ";
if(firstIndex < lastIndex) {
int p = partition(firstIndex, lastIndex);
//System.out.println(indent + "p = " + p);
quicksort(firstIndex, p - 1);
quicksort(p + 1, lastIndex);
}
//indent = indent.substring(2);
}

private int partition(int firstIndex, int lastIndex) {
//System.out.println(indent + "Inside partition(" + firstIndex + ", " + lastIndex + ")");
int pivotIndex = (firstIndex + lastIndex) / 2;
//System.out.println(indent + "pivotIndex = " + pivotIndex);
int i = firstIndex;
int j = lastIndex;
while (i < j) {
while(list.compare(i, pivotIndex, comparator) < 0 && i < j) {
i++;
}
while(list.compare(j, pivotIndex, comparator) >= 0 && i < j) {
j--;
}
//System.out.println(indent + "Initially: " + list.toString());
//System.out.println(indent + "i = " + i +", pivotIndex = " + pivotIndex + ", j = " + j);
if(i < j) {
list.swap(i, j);
//System.out.println(indent + "After 1st swap: " + list.toString());
if(i == pivotIndex) {
pivotIndex = j;
//System.out.println(indent + "Pivot was swapped");
}
else if(j == pivotIndex) {
pivotIndex = i;
//System.out.println(indent + "Pivot was swapped");
}
i++;
j--;
//System.out.println(indent + "i = " + i +", pivotIndex = " + pivotIndex + ", j = " + j);
}
}
list.swap(pivotIndex, i);
//System.out.println(indent + "After 2nd swap: " + list.toString());
//System.out.println(indent + "i = " + i +", pivotIndex = " + pivotIndex + ", j = " + j);
return i;
}
}


Additional Code:

As requested in the comments section -

The superclass
AbstractSorter<T>
:

package sorters;

import java.util.Comparator;

import structures.SwapList;

/**
* An abstraction over the idea of a sorter. Concrete subclasses should sort the
* list into ascending (smallest-first) order, using the provided Comparator.
*
*
* @param <T>
*/
public abstract class AbstractSorter<T> {
/**
* the list to be sorted
*/
protected final SwapList<T> list;

/**
* the comparator to be used
*/
protected final Comparator<T> comparator;

/**
* Constructs a new sorter, using the given list and comparator.
* @param list the list to be sorted
* @param comparator the comparator to use when sorting
* @throw IllegalStateException if the list has already been manipulated by a sorter
*/
public AbstractSorter(SwapList<T> list, Comparator<T> comparator) {
if ((list == null) || (comparator == null)) {
throw new NullPointerException();
}
if (list.getComparisons() > 0 || list.getSwaps() > 0) {
throw new IllegalStateException();
}

this.list = list;
this.comparator = comparator;
}

/**
* Sorts the associated list in-place, and returns a reference to it.
*
* @return a reference to the sorted list.
*/
public abstract SwapList<T> sort();
}


The interface
SwapList<T>
:

package structures;

import java.util.Comparator;

/**
* A list which supports the minimal operations necessary for most in-place
* comparison-based sorts, along with two observers.
*
* Notably, it does not (directly) allow access to specific elements, though
* though a toString() method is included in ArrayBasedSwapList for fans of caveman
* debugging.
*
*
* @param <T>
*/
public interface SwapList<T> {
/**
* Return the result of comparator.compare() on the two elements of the list
* at the given indices.
*
* @param index1
* @param index2
* @param comparator
* @return the result of comparator.compare() on the values at the indices
*/
public int compare(int index1, int index2, Comparator<T> comparator);

/**
* Swaps the values contained in the indices of the list.
* @param index1
* @param index2
*/
public void swap(int index1, int index2);

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

/**
*
* @param comparator
* @return true iff the list is sorted according to the given comparator
*/
public boolean isSorted(Comparator<T> comparator);

/**
*
* @return the number of times swap() has been called on this list
*/
public int getSwaps();

/**
*
* @return the number of times compare() has been called on this list
*/
public int getComparisons();
}


And the implementing class
ArrayBasedSwapList<T>
:

package structures;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;

public class ArrayBasedSwapList<T> implements SwapList<T> {
private final ArrayList<T> arrayList;
private int swaps = 0;
private int comparisons = 0;

public ArrayBasedSwapList(T[] array) {
arrayList = new ArrayList<T>(Arrays.asList(array));
}

public ArrayBasedSwapList(Collection<T> coll) {
arrayList = new ArrayList<T>(coll);
}

@Override
public int compare(int index1, int index2, Comparator<T> comparator) {
comparisons++;
return comparator.compare(arrayList.get(index1), arrayList.get(index2));
}

@Override
public void swap(int index1, int index2) {
swaps++;
T temp = arrayList.get(index1);
arrayList.set(index1, arrayList.get(index2));
arrayList.set(index2, temp);
}

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

@Override
public boolean isSorted(Comparator<T> comparator) {
for (int i = 0; i < arrayList.size() - 1; i++) {
if (comparator.compare(arrayList.get(i), arrayList.get(i + 1)) > 0) {
return false;
}
}
return true;
}

public int getSwaps() {
return swaps;
}

public int getComparisons() {
return comparisons;
}

@Override
public String toString() {
return arrayList.toString();
}
}


Update:
Implementing the suggestions in @ruakh's answer, I was able to debug and identify the problem. The fault was in the
partition
method. Here's the corrected algorithm:

int partition(int firstIndex, int lastIndex) {
int pivotIndex = (firstIndex + lastIndex) / 2;
int i = firstIndex;
int j = lastIndex;
while (i < j) {
while(i < lastIndex && list.compare(i, pivotIndex, comparator) <= 0 && i <= pivotIndex) {
i++;
}
if(i < pivotIndex) {
list.swap(i, pivotIndex);
pivotIndex = i;
}

while(firstIndex < j && list.compare(j, pivotIndex, comparator) >= 0 && pivotIndex <= j) {
j--;
}

if(j > pivotIndex) {
list.swap(j, pivotIndex);
pivotIndex = j;
}
}
return pivotIndex;
}

Answer

I see three mistakes or arguable mistakes in the partition method:

  • The method is private, which means that you're not unit-testing it, even though it's one of the most complex pieces of code you've got.
    • You can address this either by making it package-private (some APIs, such as Guava, offer a special @VisibleForTesting annotation that you can use to make clear why you've done this), or by factoring it out into its own class that QuickSorter delegates to.
  • Your algorithm assumes that i <= pivotIndex && pivotIndex <= j at all times (since otherwise list.swap(i, j) accomplishes nothing), but it only ensures that i <= j.
    • I determined this by code inspection, but once I saw the bug, I checked your debugging output, and in fact this issue did show up there: i = 2, pivotIndex = 3, j = 2. Unfortunately, this is a limitation of all approaches to debugging: you can be looking right at the problem, but if you don't know what you're looking for, you may not see it. A good strategy is to take a break and come back later with fresh eyes. (Well, assuming you've given yourself enough time for that to be feasible.)
    • Actually this is really two mistakes, not just one: there are at least two completely separate ways that i <= pivotIndex && pivotIndex <= j can become false. And I think you really do need that assumption to remain true. (That is, the problem isn't that you're making the assumption, it's that you're not satisfying it.)
    • In addition to fixing this issue, you might consider making use of assertions and validations so that your code blows up as soon as it gets into a bad state. (That said, it can be hard to think of useful assertions to include in the middle of a complex unit of code. Figuring out the right assertions is not much easier than simply noticing the bug to begin with. So, dunno.)
  • The list.swap(pivotIndex, i) near the end is not well-motivated. Rather, it looks like that was tacked on to try to patch over a bug? If so, then — you should always root-cause bugs in order to fix them, rather than try to work around them without understanding what happened. Otherwise you can never be sure that your workaround fully solves the problem (and in my experience, you can generally be sure that it doesn't).

I think you can see, by the way, why I don't share Amit's love of debuggers. Your debugging output showed you the bug, but you didn't see it; you would probably have gotten the same result with a debugger. (If anything, a debugger would likely have made it even harder to see the big picture.) That said, I do think you should give debuggers a try; many people do find them useful, and it never hurts to have another weapon in your arsenal. And when the problem is that you simply aren't noticing an issue, who knows but that seeing the same thing in two different ways (in debugging output and in a debugger) may increase the chances that you'll notice it once?