私はCormen Algorithm Textbookからクイックソートアルゴリズムをプログラムしようとしています。以下は私のコードです。
class Quicksort
{
public void qSort(int[] a, int p, int r)
{
if(p<r)
{
int q = Partition(a, p,r);
qSort(a, p, q-1);
qSort(a, q+1, r);
}
}
private int Partition(int[] a, int p, int r)
{
int x = a[r];
int i = p-1;
int temp=0;
for(int j=p; j<r-1; j++)
{
if(a[j]<=x)
{
i++;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
temp = a[i+1];
a[i+1] = a[r];
a[r] = temp;
return (i+1);
}
}
public class QuickSortTest
{
public static void main(String[] args)
{
Quicksort qsort = new Quicksort();
int[] array = {5, 4, 7, 2, 1, 9, 3, 6, 10, 8};
System.out.print("Original Array : ");
for(int i=0; i<array.length;i++)
{
System.out.print(array[i] + " ");
}
int length = array.length;
qsort.qSort(array, 0, length-1);
System.out.print("Sorted Array : ");
for(int i=0; i<array.length;i++)
{
System.out.print(array[i] + " ");
}
}
}
しかし、このコードを実行すると、間違った出力が表示されます。
Original Array : 5 4 7 2 1 9 3 6 10 8
Sorted Array : 1 4 5 2 6 7 3 8 9 10
誰が何が悪いのか説明してもらえますか？「アルゴリズムの概要」の本に記載されているとおりに、このコードを実装しました。ありがとうございました。
いいえ、あなたはそれを直接コピーしていません:)私はここにそれを持っています...
for(int j=p; j<r-1; j++)
する必要があります
for(int j=p; j<r; j++)
または
for(int j=p; j <= r-1; j++)
本は書いています：
for j = p to r - 1
含まれていますr - 1。また、本には0ではなく1から始まる配列があることを思い出してください。したがって、一般に、本のアルゴリズムは、細心の注意を払って、または1から始まる配列で「コピー」する必要があります。
編集：コメントのアルゴリズムに関する情報本のアルゴリズムは、最後の要素をピボットとして使用します。したがって、すでにソートされた配列に対しては、それはひどいアルゴリズムになります。配列は多少ソートされる傾向があるため、最終的にはO（n ^ 2）になるため、このアルゴリズムを本番環境で使用することはできません（何をしているか、何を入力しているかを理解していない限り）。Javaの組み込みアルゴリズムはより巧妙で、Javadocで読むことができます。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加