0

クイックソートの例を理解しようとしています。9 つの数字をランダムに生成し、リストに配置します。プログラムはランダムなピボットを選択します。ピボットに基づいて、リスト内の他の値が左側のリストまたは右側のリストに配置されます。次に、左のリストと右のリストを使用してメソッドを再度呼び出します。これは私が混乱するところです。9 つの数字を完全に並べ替えるわけではありません。私は何を間違っていますか？

これが私の更新されたコードです。ここで、ピボット番号がリスト内の別の番号と同じ場合、ソートされたリストには含まれません。たとえば、ソートされていない 487878146、ソートされた 14678 です。ピボット) 続行;)

public static List<int> QuickSort(List<int> arr)
    {
        Random random = new Random();
        int i, pivot;

        List<int> leftList = new List<int>();
        List<int> rightList = new List<int>();

        if (arr.Count > 1)
        {
            //pivot = random.Next(arr[0],arr[arr.Count - 1]);
            pivot = arr[random.Next(0, arr.Count - 1)];
                foreach(int j in arr)
                {
                    if (j == pivot) continue;
                    if (j <= pivot)
                        leftList.Add(j);
                    else
                        rightList.Add(j);
                }

            List<int> sortedLeft = QuickSort(leftList);
            List<int> sortedRight = QuickSort(rightList);

            List<int> tempList = new List<int>();
            tempList.AddRange(sortedLeft);
            tempList.Add(pivot);
            tempList.AddRange(sortedRight);

            //for (i = 1; i <= leftList.Count; i++)
            //    tempList.Add(leftList[i - 1]);
            //tempList.Add(pivot);
            //for (i = 1; i <= rightList.Count; i++)
            //    tempList.Add(rightList[i - 1]);


            return tempList;
        }
        return arr;
    }
4

2 に答える 2

2

クイックソートはソートされたリストを返すため、ソートされていない入力の代わりにマージする必要があります。

List<int> sortedLeft = QuickSort(leftList);
List<int> sortedRight QuickSort(rightList);

List<int> tempList = new List<int>();
tempList.AddRange(sortedLeft);
tempList.Add(pivot);
tempList.AddRange(sortedRight);
于 2012-10-08T18:08:29.200 に答える
0

Leeの回答に加えて、配列にある必要のない乱数を使用しているため、ピボットの選択を変更してからリストに挿入する必要があります。たとえば、次のようなものを試すことができます。

pivot = arr[random.Next(0,arr.Length - 1)];
于 2012-10-08T18:30:14.420 に答える