2
我想實現快速排序算法來對不直接允許訪問其元素的列表進行排序。我應該僅使用兩種方法對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;
}
}
附加代碼：
正如在評論部分請求 -
的超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;
}
使用調試器。 – Amit
請將完整的代碼添加到您的問題 – JavaHopper
我建議閱讀[Eric Lippert的「如何調試小程序」]（https://ericlippert.com/2014/03/05/how-to-debug-small-programs/）。你可以通過自己調試來發現錯誤，而不是通過在互聯網上找到陌生人來發現錯誤並告訴你。 – ruakh