实施 Quicksort 以对列表进行 restricted/no 访问其内容的排序

Question

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

我运行使用运行domly 生成的列表进行了一些 JUnit 测试 ~~其中几乎所有的列表都得到了排序~~（更新：经过运行几次测试，我发现了更多算法失败的情况）。但是，（其中一种情况）当我尝试 partition 一个 4 元素子数组时，我的算法失败了，其中的键 ar运行按以下顺序排列：[最小，最大，大，小]

这是传递列表的 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 class 使用：

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

附加代码：

如评论区要求-

超级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();
}

和执行 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();
    }
}

更新： 实施@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，这意味着您没有对其进行单元测试，即使它是您拥有的最复杂的代码片段之一。
- 您可以通过将其设为包私有（一些 API，例如 Guava，提供一个特殊的 @VisibleForTesting 注释，您可以使用它来明确您这样做的原因）或通过将其分解为 QuickSorter 委托给自己的 class。
您的算法假定 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 对调试器的热爱。您的调试输出向您显示了错误，但您没有看到；使用调试器可能会得到相同的结果。（如果有的话，调试器可能会让人更难看到全局。）也就是说，我确实认为您应该尝试一下调试器；许多人确实发现它们很有用，并且在您的武器库中拥有另一种武器永远不会有坏处。当问题是您根本没有注意到问题时，谁知道以两种不同的方式（在调试输出和调试器中）看到同一件事可能会增加您注意到它一次的机会？

Answer 2

除了@ruakh 指出的内容之外，我还观察到在调用 partition() 之后 pivot 可以留在数组的任何部分。但是，由于枢轴索引处的元素是肯定排序的，它甚至可以位于 list; 的最末端。有条件地调用 quicksort() 应该可以解决您的问题。另外，请记住@ruakh 的回答中已经突出显示的边缘情况，以下代码应该可以解决您的所有问题。我已经为任何破坏案例无限地测试了这个例程，到目前为止找不到。

快速排序方法：

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);
                if (firstIndex < p - 1)
                    quicksort(firstIndex, p - 1);
                if (p < lastIndex)
                    quicksort(p, 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++;
                }
                while(list.compare(j, pivotIndex, comparator) > 0) {
                    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;
        }

请注意，我没有更改您代码的其他部分，这些部分被注释掉或任何其他方法

测试员class:

package test;

import java.util.Comparator;
import java.util.Random;

public class Test
{

    private static final Comparator<Integer> INTEGER_COMPARATOR = new IntegerComparator();

    public static void main(String args[]) {
        SwapList<Integer> customList;
        AbstractSorter<Integer> customSorter;
        do {
            Random r = new Random();
            int length = r.nextInt(10);
            Integer[] test = new Integer[length];
            for(int j = 0; j < length; j++)
                test[j] = r.nextInt(10);
            customList = new ArrayBasedSwapList<Integer>(test);
            customSorter = new QuickSorter<Integer>(customList,
                    INTEGER_COMPARATOR);
            SwapList<Integer> result = customSorter.sort();
            if(!result.isSorted(INTEGER_COMPARATOR)) {
              System.out.println("Result: " + result.toString());
              System.out.println(result.isSorted(INTEGER_COMPARATOR));
            }
        } while(true);
    }

}

欢迎评论任何失败的测试用例，我会尽力修复它。

实施 Quicksort 以对列表进行 restricted/no 访问其内容的排序

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

java

sorting

algorithm

quicksort

data-structures