-1

クイックソートを実装する方法を学ぼうとしています。私は基本的なアルゴリズムを読み、最初に独自のコードを実装しようとしました (アルゴリズムの理解に基づいて)。

簡単にするために、ピボットを最初の要素としています。できれば無視してください。コードは実行されますが、正しい結果が返されず、その理由がわかりません。どんな助けでも大歓迎です。

public class QuickSortMain 
{
public static void displayArray(int[] arr)
{
    for(int i = 0; i < arr.length; i++)
        System.out.print(arr[i] + "  ");
}

public static void quickSort(int[] arr)
{
    quickSort(arr, 0, arr.length - 1);
}

private static void quickSort(int[] arr, int lo, int hi)
{
    if(lo >= hi) return;

    int j = lo;
    int left = lo;
    int right = hi;

    while(arr[left] <= arr[j])
        left++;

    while(arr[right] >= arr[j])
        right--;

    if (left >= right) return;

    swap(arr, left, right);
    swap(arr, j, left);

    quickSort(arr, lo, j-1);
    quickSort(arr, j+1, hi);
}

private static void swap(int[] arr, int i1, int i2)
{
    int temp = arr[i1];
    arr[i1] = arr[i2];
    arr[i2] = temp;
}

public static void main(String[] args)
{

    int[] myArray = {14, 79, 11, 42, 3, 27, 192, 44, 26, 742, 129};
    System.out.println(myArray.length);
    System.out.println("Original Array:");
    displayArray(myArray);

    quickSort(myArray);
    System.out.println("");
    System.out.println("Sorted Array:");
    displayArray(myArray);

}
}

11 元の配列: 14 79 11 42 3 27 192 44 26 742 129
並べ替えられた配列: 3 14 11 42 79 27 192 44 26 742 129

ありがとう！

4

1 に答える 1

0

ピボットより小さいすべての値が一方にあり、より大きいすべての値が反対側にあることを確認する必要があります。パーティション方式で十分なスワップを行っていませんでした。

このような状況を解決するには、アルゴリズムが機能していない領域を強調するテスト ケースを作成することをお勧めします。また、デバッガーを使用すると役立ちます。

private static void quickSort(int[] arr, int lo, int hi)
{
    if(lo >= hi) return;

    int j = lo;
    int left = lo;
    int right = hi;

    while (left < right){
        left++;
        while(arr[left] < arr[j] && (left < right))
            left++;

        while(arr[right] > arr[j] && (left < right))
            right--;

        if (left < right){
            swap(arr, left, right);
        }
    }

    if(arr[left] < arr[j]){
        swap(arr, j, left);
    }

    quickSort(arr, lo, left-1);
    quickSort(arr, left, hi);
}
于 2013-10-13T21:39:56.943 に答える