2

クイックソートが機能しません。パーティション アルゴリズムに何を渡すか、ピボットを管理する方法について特に確信が持てません。ピボットがヘッダー ノードになる場合もあれば、最後のノードになる場合もあります。私のアプローチは、配列のソリューションに基づいています。これが私の試みです。何か案は？パーティショニング アルゴリズムは、単一リンク リスト (SLL) の一方向の性質に合わせて選択されていることに注意してください。

public static SLL quickSort(SLL list, SLLNode first, SLLNode last)
{
    if (first != null && last != null)
    {
        SLLNode p = partition(list, first, last) ;
        quickSort(list,first,p) ;
        quickSort(list,p.succ, last) ;
    }
    return list ;
}

public static SLLNode partition(SLL list, SLLNode first, SLLNode last)
{
    //last.succ = null ;
    SLLNode p = first ;
    SLLNode ptr = p.succ ;

    while (ptr!=null)
    {
        if (ptr.data.compareToIgnoreCase(p.data)<0)
        {
            String pivot = p.data ;
            p.data =  ptr.data ;
            ptr.data = p.succ.data ;
            p.succ.data = pivot ;
            p = p.succ ;
        }
        ptr = ptr.succ ;
    }
    return p ;
}

[編集]

  • これを「その場で」やりたい

  • このプロセスでヘッドとラストを管理する方法について、特に助けを求めています。

  • 私のアプローチが不可能でない限り、代替案を提案しないでください

4

4 に答える 4

1

リンクされたリストでのクイックソートの通常のアプローチは、分割ステップで 2 つ (できれば 3 つ、中央のリストはすべての要素がピボット要素に等しい) の新しいリストを作成し、最初と最後のリストを再帰的に並べ替え、それらを連結することです。 .

代わりに、コードはノード内のデータを交換します...興味深いです。次の（サブ）リストで試しました：

        first                            last
        [ 5 ]-->[ 3 ]-->[ 7 ]-->[ 9 ]-->[ 2 ]

あなたのアルゴリズムが何をするかをここで見てください：

        [ 5 ]-->[ 3 ]-->[ 7 ]-->[ 9 ]-->[ 2 ]
          p
                 ptr

3<5? (yes) {
pivot=5
        [ 3 ]-->[ 3 ]-->[ 7 ]-->[ 9 ]-->[ 2 ]
          p      ptr
        [ 3 ]-->[ 7 ]-->[ 7 ]-->[ 9 ]-->[ 2 ]
          p      ptr
        [ 3 ]-->[ 7 ]-->[ 5 ]-->[ 9 ]-->[ 2 ]
          p      ptr
        [ 3 ]-->[ 7 ]-->[ 5 ]-->[ 9 ]-->[ 2 ]
                  p
                 ptr
}
        [ 3 ]-->[ 7 ]-->[ 5 ]-->[ 9 ]-->[ 2 ]
                  p
                         ptr

これは、最初の反復後の状態です。以来ptr != null、次の繰り返しに進みますが、ここですでに問題を確認できると思います。次の反復の後、次のようになります。

        [ 3 ]-->[ 5 ]-->[ 9 ]-->[ 7 ]-->[ 2 ]
                          p
                                 ptr

次の反復では、スワップは発生しません。

        [ 3 ]-->[ 5 ]-->[ 9 ]-->[ 7 ]-->[ 2 ]
                          p
                                         ptr

そして今、NullPointerException を取得しますptr.next == null(または、これがより大きなリストのサブリストである場合は、制限の外側でスワップします)。

だから、いくつかのアイデア：

  • スワップ手順でpは、ピボット要素を含むノードを後で指していることを確認する必要があります。
  • 要素に到達したら停止し、lastその後スワップしないようにする必要があります (ただし、必要に応じて要素自体はスワップされます)。
于 2011-03-29T17:27:26.553 に答える
0

非破壊バージョンの場合は、次の擬似コードをJavaに変換します。

quickSort list
    | list.isEmpty = empty list
    | otherwise = concat (quickSort lower) (new List(pivot, quickSort upper))
    where
         pivot = list.head
         lower = list of elements from list.tail that are < pivot
         upper = list of elements from list.tail that are >= pivot
于 2011-03-29T15:43:40.583 に答える
0

「last.succ = null」という行をチェックアウトすることをお勧めします。分割しているリストセグメントの最後に達したかどうかを確認する別の方法を見つけたいと思うかもしれません。そのままでは、ヌル ポインター例外が発生するはずですが、間違っている可能性があります。

于 2011-03-29T15:30:06.117 に答える