0

10個のランダムな整数を作成し、クイックソートを使用してそれらをソートする配列があります..私の問題は、これを1,000,000個のランダムな整数を作成するように変更すると、それができないことです..助けてもらえますか?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RepeatAssignmentQ2
{
class Program
{
    static public int Partition(int[] myArray, int left, int right)
    {
        int pivot = myArray[left];
        while (true)
        {
            while (myArray[left] < pivot)
                left++;

            while (myArray[right] > pivot)
                right--;

            if (left < right)
            {
                int temp = myArray[right];
                myArray[right] = myArray[left];
                myArray[left] = temp;
            }
            else
            {
                return right;
            }

        }
    }

    static public void QuickSort_Recursive(int[] arr, int left, int right)
    {
        // For Recusrion
        if (left < right)
        {
            int pivot = Partition(arr, left, right);

            if (pivot > 1)
                QuickSort_Recursive(arr, left, pivot - 1);

            if (pivot + 1 < right)
                QuickSort_Recursive(arr, pivot + 1, right);
        }
    }

    static void Main(string[] args)
    {
        Random rnd = new Random();
        DateTime startTime = DateTime.Now;

        int ind = 0;
        int length = 1000000;
        int[] myArray = new int[length];

        while (ind < 1000000)
        {
            myArray[ind] = rnd.Next(1000000);
            ind++;
        }

        int lengthTwo = 10;

        Console.WriteLine("QuickSort by recursive method");

        QuickSort_Recursive(myArray,0, lengthTwo - 1 );



        for (int i = 0; i < 1000000; i++)
        {

            Console.WriteLine(myArray[i]);

        }
        Console.WriteLine("Total Time: {0}\n", DateTime.Now - startTime);
        Console.WriteLine();



    }
}
}

ありがとう

編集 - 10 個の数値を持つ配列を使用してプログラムを調整すると、それらが表示され、並べ替えられます。1,000,000 に変更してプログラムを実行すると、何も表示されません。

編集 2 - いくつかの奇妙な理由でこれを行っています。変更を表示するように上記のコードを変更しました。ランダムに生成された数字が表示されるようになりましたが、並べ替えはされていません。しかし、IT 部門が 10 個の乱数を作成するだけでよい場合は、それを並べ替えました。

4

4 に答える 4

2

1,000,000 個の要素の入力と並べ替えは、依然として非常に高速です。

Partition メソッドのアルゴリズムにエラーがあります。増減する必要leftがあるよりも小さい場合:rightleftright

if (left < right)
{
    int temp = myArray[right];
    myArray[right] = myArray[left];
    myArray[left] = temp;
    left++;
    right--;
}

myArray[left]より大きいか等しいpivot、myArray[right]より小さいか等しい 、pivotおよびleftより小さい場合にプログラムがどのように動作するかを分析しますright。while (true)2 つwhileの が無視され、またはifの値が変更されないため、無限ループが発生します。この状況は、配列に重複がある場合に発生します。たとえば、1,000,000 個の要素に 1,000 個の数字のみを入力しようとすると発生します。leftright

ところで。length1000000 ごとに変数に置き換えて、 に置き換えると、コードが改善lengthTwoされlengthます。なんで？このような状況で、より大きな配列のプログラムの動作を確認したい場合。5 つの数値よりも 1 つの変数の値を変更する方が簡単です。

お役に立てば幸いです。

于 2013-08-22T19:34:39.200 に答える
0

私は今これに出くわしました、エラーはここにあります

QuickSort_Recursive(myArray,0, lengthTwo - 1);

に変更します

QuickSort_Recursive(myArray,0, length - 1 );

あなたのパーティショニングについては、hoareのアルゴリズムを認識しています（代替よりも高速です）https://cs.stackexchange.com/questions/11458/quicksort-partitioning-hoare-vs-lomuto両方の疑似コードを次に示します（iが表示されます開始時に =p+1 および j=p-1 それ以外の場合は問題ありません)

于 2013-12-28T20:15:30.077 に答える
0

すみませんが、どのくらい待ちましたか？Next メソッドを 1,000,000 回呼び出しているため、1mil 整数の配列を設定する while ループに非常に時間がかかっているのではないかと思います。次の出力が表示されていますか: 「再帰的方法によるクイックソート」?

于 2013-08-22T18:41:49.530 に答える