1

再帰的なクイック ソート アルゴリズムでいくつかの問題に直面しています。要素が正しい順序で並べ替えられていません。入力データも、重複するエントリを持つ文字列です。昇順 ( 1 ) と降順 ( -1 ) の並べ替えを区別するために整数を使用しています。ピボットは中間要素です。重複するエントリが比較されるたびに (compareTo(String s) は 0 を返します)、現在のインデックスを比較し、比較されている文字列のインデックスが他のインデックスよりも大きい場合は負の数を返します。正確に何がうまくいかないのですか。以下はコードです

// Quick sort Algorithm
public void sort(int left, int right)
{
    int  i = left, j = right;
    String mid;

    mid = (String)vect.elementAt((left + right)/2);

    while (i <= j)
    {
        // Compare the elements to the left
        while ((i < right) && 
                (compare((String)vect.elementAt(i), mid) < 0))
            i++;
        // Compare the elements to the right
        while ((j > left) && (compare((String)vect.elementAt(j), mid) > 0))
            j--;

        if (i <= j)
        {
            if(i!=j)
                swap(i, j);

            i++;
            j--;

        }
    }
    // Recursively call the sort method until indices cross.
    if(left < j)
        sort(left, j);
    if(i < right)
        sort(i, right);
}

/*
 * Compare method to compare the elements.
 * type = 1, for ascending sort
 * type = -1, for descending sort
 */
public int compare(String firstObj, String secondObj)
{
    int resCompare = firstObj.compareTo(secondObj)*type;
    if(resCompare == 0)
    {
        int index_firstObj = vect.indexOf(firstObj);
        int index_secObj = vect.indexOf(secondObj);
        if(index_firstObj < index_secObj)
            return -1;
        else
            return 1;
    }
    return resCompare;
}
// Swap the elements at i and j.
public void swap(int i, int j)
{
    String tmp1 = (String)vect.elementAt(i);
    String tmp2 = (String)vect.elementAt(j);

    vect.setElementAt(tmp1, j);
            vect.setElementAt(tmp2, i);

}

例：input = {"AA","BB","zz","cc","aa","AA","PP","hh"}; 昇順ソート出力 = {"AA","AA","BB","PP","aa","cc","hh","zz"}; 降順ソート出力 = {"zz","hh","cc","BB","aa","PP","AA","AA"};

アルゴリズムの問​​題は、昇順ソートだけでなく、他の入力データでも機能しない場合があります。したがって、コード/ロジックの不具合を見つけるための助けは本当に役に立ちます.よろしくお願いします.

解決済み: index_firstObj と index_SecondObj を見つける必要はありません。resCompare がゼロの場合は何もしないでください。public int compare(String firstObj, String secondObj) { int resCompare = firstObj.compareTo(secondObj)*type; resCompare を返します。}

4

1 に答える 1

0

i または j が mid になるとどうなりますか? もう1つはまだミッドではありませんか？それも問題になりませんか？それらの1つがミッドになるかどうかを確認する必要があるかもしれません。

于 2012-09-03T08:08:56.210 に答える