1

基本的に、リンクされたリストの最初のアイテムを取得し、最初のアイテムより大きいか等しいアイテムを持つリストと、最初のアイテムより小さいアイテムを持つリストの 2 つの別々のリストにソートするピボット ソート アルゴリズムを作成する必要があります。すでにソートされているサイズ 1 のリンクされたリストに到達するまで、それらを再帰的に並べ替えます。次に、より小さいリストとより大きいリストをマージして、ソートされたリストを形成します。

私のアルゴリズムは無限ループの最後の項目でスタックし続けており、約 23 時間睡眠をとっていないため、間違いを犯した場所を見つけるために新鮮な目が必要です。もしあなたが助けてくれたら、私はとても助かります。

Linked list クラスは単純で、2 つの項目があります。1 つ目は単なる正の整数で、2 つ目はもちろんリスト内の次の項目です。コードは、最後のアイテムにヒットしたときに Sort() 関数に引っ掛かり、最後のアイテムを一緒に追加しません。

public class PivotSort {
   public static void main(String[] args) {
      try {
         intList x = intList.CreateFromUserInput(); // just makes a linked list
                                                    // from numbers I type in
         x = Sort(x);
         x.PrintList();
      } catch (Exception e) {
         System.out.println(e);
      }
   }

   public static intList Sort(intList list) {
      if (list == null || list.item == null)
         return list;
      return Append(Sort(Part_Less(list.item, list)),
            Sort(Part_Greater(list.item, list)));
   }

   public static intList Part_Less(int N, intList L1) {
      if (L1 == null)
         return null;
      if (L1.item < N)
         return new intList(L1.item, Part_Less(N, L1.next));
      else
         return Part_Less(N, L1.next);
   }

   public static intList Part_Greater(int N, intList L1) {
      if (L1 == null)
         return null;
      if (L1.item >= N)
         return new intList(L1.item, Part_Greater(N, L1.next));
      else
         return Part_Greater(N, L1.next);
   }

   public static intList Append(intList L1, intList L2) {
      try {
         if (L1 == null)
            return L2;
         if (L2 == null)
            return L1;
         for (intList curr = L1; curr != null; curr = curr.next) {
            if (curr.next == null) {
               curr.next = L2;
               break;
            }
         }
         return L1;
      } catch (Exception e) {
         System.out.println(e);
         return null;
      }
   }
}
4

1 に答える 1

2

問題は、2 番目の呼び出しで基本ケースにSort到達できないことです。

Sort(Part_Greater(list.item, list))

関数は最初に、最初のPart_Greater()アイテムより大きいか等しいすべてのアイテムを含むリストを作成します。これがあなたの元のリストだとしましょう：

10 5 7 11 15 7 16 20

Part_Greater()を含むリストを作成します10 11 15 16 20。それを に渡すと、そのリストが再びSort呼び出さPart_Greater()れ、そのリストだけが返されます。

を最初に呼び出した後は要素が削除されないためPart_Greater()、無限再帰に入ります。

必要なことは、ピボット要素をリストから削除することです。これにより、すべての再帰ステップで、数値のリストが少なくとも 1 つ短くなり、リストが空のときに最終的に基本ケースに到達することが保証されます。

return Append(
    Sort(Part_less(list.item, list.next)),
    new intList(list.item, Sort(Part_Greater(list.item, list.next)))
);
于 2012-11-03T22:39:04.707 に答える