-2

これはちょっと変わった質問だと思いますが、クイックソート アルゴリズム用の次の Java コードを見つけました。

private static void quickSort (ArrayList <String> list, int first, int last){

        int g = first; 
        int h = last;

        int midIndex = (first + last) / 2;
        String dividingValue = list.get(midIndex);

        do{
            while (list.get(g).compareTo(dividingValue) < 0) g++;
            while (list.get(h).compareTo(dividingValue) > 0) h--;
            if (g <= h)
            {
                swap(list,g,h);
                g++;
                h--;
            }
        }

        while (g < h);

        if (h > first) quickSort (list,first,h);
        if (g < last) quickSort (list,g,last);      
    }

    private static void swap (ArrayList <String> list, int first, int h)
    {
        String temp = list.get(first);
        list.set(first, list.get(h));
        list.set(h, temp);
    }

私は働いていますが、それは私には本当に意味がありません。誰かがこのコードの説明を何とかしてもらえますか? または、可能であればクイックソートのより単純なコードを教えてください。

4

1 に答える 1

3

クイックソートがどのように機能するかを知っていて、この特定の実装について疑問に思っていると仮定します。また、コードが正しいと仮定しています。作業している範囲を定義し、ピボットを選択することから始めます。

private static void quickSort (ArrayList <String> list, int first, int last) {

    int g = first; 
    int h = last;

    int midIndex = (first + last) / 2;
    String dividingValue = list.get(midIndex);

次に、範囲の両端から開始し、内側に向かって作業します。ピボットの左側のすべてを小さくし、右側のすべてを大きくします。したがって、これをすでに満たしている要素はすべてスキップします。

    do {
        while (list.get(g).compareTo(dividingValue) < 0) g++;
        while (list.get(h).compareTo(dividingValue) > 0) h--;

どちらもプロパティに違反する 2 つの要素に到達すると、それらを交換して正しい側に配置し、内側に移動します。スワップ後に（ループのように値をチェックするのではなく）やみくもにif (g <= h)適用するため、チェックが必要です。スワップする反対の要素を持たないハンドルにピボットをスワップするようです。これは間違いなく、正確性を保証するためにテストする必要があります。g++h--while

        if (g <= h)
        {
            swap(list, g, h);
            g++;
            h--;
        }

ピボットに到達するまでこれを続けます (ピボットは交換できるため、わずかに暗示的です)。

    } while (g < h);

リスト全体がソートされるように、リストのサブセクションにこのプロパティを再帰的に適用します。

    if (h > first) 
        quickSort(list, first, h);
    if (g < last) 
        quickSort(list, g, last);      
}

private static void swap (ArrayList <String> list, int first, int h)
{
    String temp = list.get(first);
    list.set(first, list.get(h));
    list.set(h, temp);
}
于 2013-06-15T19:53:16.490 に答える