java - 实现快速排序以对列表进行排序，限制/无法访问其内容

Question

我正在尝试实现快速排序算法来对不允许直接访问其元素的列表进行排序。我应该对 list 进行排序仅使用两种方法:swap和compare ，不使用toString提供的方法仅用于调试目的。我选择了子数组的中间元素作为枢轴。使用 Comparator 进行比较函数调用期间传递的对象。

我使用随机生成的列表运行了一些 JUnit 测试其中几乎所有列表都已排序(更新:运行更多测试后，我发现了更多情况算法失败的地方)。但是，(其中一种情况)当我尝试 partition 时，我的算法失败了一个 4 元素子数组，其键按以下顺序排列:[最小、最大、大、小]

这是传递列表的 JUnitTest - [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));
}

和IntegerComparator使用的类:

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);
    }
}

我添加了一些 println 语句并添加了 indent代码中的变量用于调试目的。这是运行测试后的输出:

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)  

结果:[0,1,3,2]

问题出在 partition(0, 3) 里面其中第二个交换语句反转第一个交换的效果。有人可以帮助纠正我的快速排序算法吗？我也许应该添加一个 if语句，以便仅当元素位于索引 i 时才会发生第二次交换> 元素位于 pivotIndex ？

代码如下:

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;
    }
}

附加代码:

按照评论部分的要求 -

父类(super class) 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();
}

界面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();
}

以及实现类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();
    }
}

更新: 实现@ruakh 答案中的建议，我能够调试并识别问题。故障出在 partition方法。这是修正后的算法:

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 1

我在 partition 中看到三个错误或有争议的错误方法:

• 方法是private ，这意味着您不对它进行单元测试，即使它是您拥有的最复杂的代码片段之一。
  • 您可以通过将其设置为包私有(private)(某些 API，例如 Guava，提供特殊的 @VisibleForTesting 注释，您可以使用它来明确为什么这样做)来解决这个问题，或者将其分解为它自己的类 QuickSorter代表们。
• 您的算法假设 i <= pivotIndex && pivotIndex <= j在任何时候(因为否则list.swap(i, j)什么也做不了)，但它只确保i <= j 。
  • 我通过代码检查确定了这一点，但是当我看到错误后，我检查了您的调试输出，事实上这个问题确实出现在那里:i = 2, pivotIndex = 3, j = 2 。不幸的是，这是所有调试方法的限制:您可以直接查看问题，但如果您不知道自己在寻找什么，则可能看不到它。一个好的策略是休息一下，然后以新的眼光回来。 (好吧，假设您已经给自己足够的时间来实现这一点。)
  • 实际上，这确实是两个错误，而不仅仅是一个:至少有两种完全不同的方式i <= pivotIndex && pivotIndex <= j可能会变成假的。我认为你确实需要这个假设才能保持正确。 (也就是说，问题不在于你做出了假设，而在于你没有满足它。)
  • 除了解决此问题之外，您还可以考虑使用断言和验证，以便您的代码一旦进入不良状态就会崩溃。 (也就是说，很难想到在复杂的代码单元中包含有用的断言。找出正确的断言并不比简单地从一开始就注意到错误容易得多。所以，不知道。)<
• list.swap(pivotIndex, i)临近尾声，动力不强。相反，它看起来像是为了尝试修补错误而添加的？如果是这样，那么您应该始终找出错误的根本原因以便修复它们，而不是在不了解发生了什么的情况下尝试解决它们。否则，您永远无法确定您的解决方法是否完全解决了问题(根据我的经验，您通常可以确定它没有)。

顺便说一下，我想你应该明白为什么我不像 Amit 那样热爱调试器了。您的调试输出向您显示了错误，但您没有看到它；使用调试器可能会得到相同的结果。 (如果有的话，调试器可能会让你更难看到全局。)也就是说，我确实认为你应该尝试一下调试器；许多人确实发现它们很有用，而且在你的武器库中拥有另一种武器总没有坏处。当问题是您根本没有注意到问题时，谁知道以两种不同的方式(在调试输出和调试器中)看到同一件事可能会增加您一次注意到它的机会？ p>