1

クイックソートを設定しようとしていますが、分数の配列をソートしたいと思っています。
現在、等しい値（たとえば、1/2と2/4）を持つ分数は適切にソートさ
れません。1/2は2/4の前にある必要がありますが、完全にランダムになります。

私が使用しているコードは次のとおりです。 

   public static void quicksort(Fraction[] f, int p, int r)
    {
        if (p < r)
        {
            int q = partition(f, p, r);
            quicksort(f, p, q - 1);
            quicksort(f, q + 1, r);
        }
    }

    public static int partition(Fraction[] f, int p, int r)
    {
        Fraction pivot = f[r];
        int i = p - 1;
        for (int j = p; j < r; j++)
        {
            if (f[j].Value < pivot.Value)
            {
                i++;
                Fraction wissel = f[i];
                f[i] = f[j];
                f[j] = wissel;
            }
            else
                if (f[j].Value < pivot.Value && f[j].Teller < pivot.Teller)
                {
                    i++;
                    Fraction wissel = f[i];
                    f[i] = f[j];
                    f[j] = wissel;
                }
        }
        Fraction wisselt = f[i + 1];
        f[i + 1] = f[r];
        f[r] = wisselt;
        return i + 1;

    }

誰かがこれを行う方法に光を当てることができますか？

編集：デビッドアーチャーの提案はそれを修正しました、みんなありがとう。

4

4 に答える 4

1

使用している分数クラスはわかりませんが、1/2と2/4（厳密な数学用語では等しい）を区別する必要がある場合は、独自の比較メソッドを作成し、代わりにそれらを使用することをお勧めします。組み込みの大なり小数演算子。

bool IsLessThan(Fraction a, Fraction b)
{
    // Your code here that results in 1/2 being less than 2/4
}

bool IsGreaterThan(Fraction a, Fraction b)
{
    // Your code here that results in 2/4 being greater than 1/2
}
于 2012-08-12T15:50:56.313 に答える
1

使ってみませんList<T>.Sort()か？クイックソートの実装です。実装がある場合は、IComparable<Fraction>を呼び出すことができますSort()。または、特定のメソッドを渡したい場合は、デリゲートを取得するオーバーライドを使用できます。

たとえば、Fractionクラスが次のような場合：

    public class Fraction : IComparable<Fraction>
    {
     public int CompareTo(Fraction other)
     {
       // if other equals this, return 0
       // if other is greater than this, return -1
       // if other is less than this, return 1
     }
//...
    }

次に、List変数を使用して、Sortメソッドを呼び出すことができます。

myList.Sort();
于 2012-08-12T16:01:15.993 に答える
1

私はあなたが望む比較はこのようなものだと思います：

static int CompareFractions(Fraction a, Fraction b)
{
    // compare the value of the fractions
    int c = (a.numerator * b.denominator).CompareTo(a.denominator * b.numerator);
    if (c == 0)
        // break ties with "lowest numerator first"
        c = a.numerator.CompareTo(b.numerator);
    return c;
}

これを通常のSortメソッドへのソートデリゲートとして使用することもできます。

于 2012-08-12T16:11:24.847 に答える
1

あなたの問題は、<比較のために依存するようにクイックソートを設計していることです。

< 1/2を2/4未満に再定義することですぐに解決できますが<、分数として使用された他のすべてのケースが台無しになります。

ソートを通常の.NETの方法で定義する必要があります。ここでは、System.Comparisonデリゲートを受け取るフォーム、System.IComparerそれらを使用しないオーバーロード、およびこれらによって実装されるオーバーロードがあります。

internal class DelegateComparer<T> : IComparer<T>
{
  private Comparison _del;
  public DelegateComparer(Comparison del)
  {
    _del = del;
  }
  public int Compare(T x, T y)
  {
    return _del(x, y);
  }
}
public static void Quicksort(Fraction[] f, int p, int r, IComparer<Fraction> cmp)
{
  /* This is the only method with the real implementation */
}
public static void Quicksort(Fraction[] f, int p, int r)
{
  QuickSort(f, p, r, Comparer<Fraction>.Default);
}
public static void Quicksort(Fraction[] f, int p, int r, Comparison<Fraction> cmp)
{
  QuickSort(f, p, r, new DelegateComparer(cmp));
}
public static void QuickSort(Fraction[] f)
{
  QuickSort(f, 0, f.Length, Comparer<Fraction>.Default);
}

これで、2/4の前に1/2を置くという奇妙なケースに対して行う必要があるのは、これを行うカスタム比較ツールだけです。Fractionクラスが次のようなものであると仮定しましょう。

public class Fraction
{
  public int Denominator{get;set;}
  public int Numerator{get;set;}
  public double Value
  {
    return (double) Numerator / (double) Denominator;
  }
}

次に、トリックを実行するIComparer<Fraction>またはをすばやく作成できます。Comparison<Fraction>2番目のオプションを取りましょう：

private static int CompareSepDenom(Fraction x, Fraction y)
{
  int cmp = x.Value.CompareTo(y.Value);//normal comparison first
  if(cmp == 0)//same value;
    return x.Numerator.CompareTo(y.Numerator);//put lower numerator (also lower denum) first
  return cmp;
}

これが実験ではなく実際のコードである場合は、クイックソートを実装する必要はありません。とにかくクイックソートArray.Sortを使用するからです。List<T>.Sortだから私たちはただすることができます：

Array.Sort(arrayOfFractions, CompareSepDenom);

または、CompareSepDenomを再利用せず、ラムダからの匿名のデリゲートが必要な場合は、次を使用できます。

Array.Sort(arrayOfFractions, (x, y) =>
    {
      int cmp = x.Value.CompareTo(y.Value);//normal comparison first
      if(cmp == 0)//same value;
        return x.Numerator.CompareTo(y.Numerator);//put lower numerator (also lower denum) first
      return cmp;
    });

一方、クイックソートを実験として書いている場合、またはコードから学ぶ場合は、依存しているという事実は、定義さICmparer<Fraction>れている特定のタイプを受け入れるようにメソッドをコーディングすることに制限されなくなったことを意味することに注意してください<。

これは、次のようなメソッドを記述できることを意味します。

public static void QuickSort<T>(T[] arr, int p, int r, IComparer<T> cmp)

これはすべてのタイプで機能します。

それが済んだら、ライブラリに組み込まれているバージョンと比較します。

編集：

ちなみに、まだやっていない場合に備えて。Fractionクラスは、（.NET1.0との下位互換性のために）を実装する必要がIComparable<Fraction>ありますIComparable。これにより、独自の比較デリゲートまたはクラスを作成したくない人は、分数（1/2および2/4）の通常の並べ替えを取得できます。同等です）。最初の実装が完了したら：

CompareTo(Fraction other)
{
  if(other == null)//take out this of Fraction is a struct
    return 1;
  return Value.CompareTo(other.Value)
}
CompareTo(object obj)
{
  if(other == null)
    return 1;
  Fraction fract = other as Fract;
  if(fract == null)
    throw new ArgumentException("Can only compare with other factions", "obj");
  return CompareTo(fract);
}

次にこれを使用するためComparer<Fraction>.Default、他の方法での順序付けに依存する他のコードと同様に、比較子を使用しないバージョンのsortメソッドが機能します。実際、「通常の順序付け方法」が理にかなっているクラス、または、、などを定義するクラスには、<それら>が<=必要です。また、これらの演算子のオーバーロードをすべてルーティングすることもできCompareToます（実際にはインライン化されるため、パフォーマンスの低下はありません`）。つまり、ほぼすべてのクラスで同じコードが機能します。

于 2012-08-12T16:13:10.417 に答える