فرز سريع لا يصنف بشكل صحيح

Question

تحاول أن تتعلم من تنفيذ فرز سريع, لا أستطيع معرفة السبب في أنه لم يصنف بشكل صحيح.

باستخدام هذا التسلسل:

6, 7, 12, 5, 9, 8, 65, 3

يعود هذا:

3, 5, 7, 8, 9, 65, 12, 6

يبدو أن النوع إلى حد ما, ولكن ليس كل شيء.ماذا فاتني ؟

هنا هو بلدي رمز:

 static void Main(string[] args)
        {
            QuickSort qs = new QuickSort();

           int[] arr = new int[] { 6, 7, 12, 5, 9, 8, 65, 3 };

            foreach (int l in arr)
            {
                Console.Write(l + ", ");
            }

            int left = 0;
            int right = arr.Count() - 1;

            int[] arrr = qs.DoQuickSort(ref arr, left, right);
            Console.WriteLine("Sorted List: ");
            foreach (int i in arrr)
            {
                Console.Write(i + " ");
            }



            Console.ReadLine();
        }

   public int Partition(int[] array, int left, int right, int PivotIndex)
    {
    int pivValue = array[PivotIndex];

    array = Swap(ref array, PivotIndex, right);

    int storeIndex = left;

    for (int i = PivotIndex; i < right-1; i++)
    {
        if (array[i] <= pivValue)
        {
            array = Swap(ref array, i, storeIndex);
            storeIndex = storeIndex + 1;
        }
    }

    array = Swap(ref array, storeIndex, right);

    return storeIndex;
}

public int[] Swap(ref int[] arr, int first, int second)
{
    int temp = arr[first];
    arr[first] = arr[second];
    arr[second] = temp;

    return arr;
}

public int[] DoQuickSort(ref int[] array, int left, int right)
{
    if (right > left)
    {
        int PivIndex = (left + right) / 2;
        int newPivIndex = Partition(array, left, right, PivIndex);
        DoQuickSort(ref array, left, newPivIndex - 1);
        DoQuickSort(ref array, newPivIndex + 1, right);
    }

    return array;
}

Answer 1

بالإضافة إلى تعليقي على السؤال نفسه ، أردت أن أشير إلى أن Swap() و DoQuickSort() لا تحتاج الأساليب إلى إرجاع الصفيف (حسب ملاحظتي في التعليق الذي يوضح أن الصفيف هو مرجع نفسه). تحقيقًا لهذه الغاية ، يجب أن يبدو الرمز الخاص بك القيام بالمهمة كما يلي:

public int Partition(int[] array, int left, int right, int pivotIndex)
{
    int pivValue = array[pivotIndex];

    Swap(array, pivotIndex, right);

    int storeIndex = left;

    for (int i = left; i < right; i++)
    {
        if (array[i] <= pivValue)
        {
            Swap(array, i, storeIndex);
            storeIndex = storeIndex + 1;
        }
    }

    Swap(array, storeIndex, right);

    return storeIndex;
}

public void Swap(int[] arr, int first, int second)
{
    int temp = arr[first];
    arr[first] = arr[second];
    arr[second] = temp;
}

public void DoQuickSort(int[] array, int left, int right)
{
    if (right > left)
    {
        int pivIndex = (left + right) / 2;
        int newPivIndex = Partition(array, left, right, pivIndex);
        DoQuickSort(array, left, newPivIndex - 1);
        DoQuickSort(array, newPivIndex + 1, right);
    }
}

Answer 2

هل تطلب أن يكون تسليم الأسماك ، أو أن تدرس كيفية السمك ؟

تعلم كيفية تصحيح البرامج الخاصة بك, بدلا من الاعتماد على الآخرين للقيام بذلك بالنسبة لك هو مهارة التي سوف تخدم لك جيدا في المستقبل.

عندما تواجه هذه المشكلة أول شيء أود القيام به هو وضع علامة رمز مع تعليقات مما يدل على الدلالي والغرض من كل قسم من التعليمات البرمجية:

// Choose a pivot halfway along the portion of the list I am searching.
int PivIndex = (left + right) / 2; 
// Partition the array so that everything to the left of the pivot
// index is less than or equal to the pivot, and everything to
// the right of the pivot is greater than or equal to the pivot.
int newPivIndex = Partition(array, left, right, PivIndex); 
// Recursively sort each half.
DoQuickSort(ref array, left, newPivIndex - 1); 
DoQuickSort(ref array, newPivIndex + 1, right); 

حسنا الآن ، في مكان ما هنا يوجد الخلل. أين ؟ البدء في سرد الحقائق التي يعتقد أن يكون صحيحا ، والكتابة التأكيد على كل الواقع.تكتب لنفسك مساعد أساليب مثل AllLessThan ، والتي التحقق من تأكيدات بالنسبة لك.

// Choose a pivot halfway along the portion of the list I am searching.
int PivIndex = (left + right) / 2;

int pivotValue = array[PivIndex];
// Partition the array so that everything to the left of the pivot
// index is less than or equal to the pivot, and everything to
// the right of the pivot is greater than or equal to the pivot.
int newPivIndex = Partition(array, left, right, PivIndex); 
Debug.Assert(array[newPivIndex] == pivotValue);
Debug.Assert(AllLessThanOrEqual(array, left, newPivIndex, pivotValue));
Debug.Assert(AllGreaterThanOrEqual(array, newPivIndex, right, pivotValue));
// Recursively sort each half.
DoQuickSort(ref array, left, newPivIndex - 1); 
Debug.Assert(IsSorted(array, left, newPivIndex));
DoQuickSort(ref array, newPivIndex + 1, right); 
Debug.Assert(IsSorted(array, left, right));

الآن عند تشغيل هذا البرنامج مرة أخرى, لحظة واحدة من التأكيدات الخاصة بك ينتهك, سوف تحصل على المربع الذي يظهر أن أقول لك ما طبيعة الخلل.استمر في فعل ذلك ، توثيق الشروط المسبقة و postconditions مع تأكيدات حتى تجد علة.

Answer 3

في الخاص بك Partition الطريقة لديك نطاق حلقة خاطئ:

for (int i = PivotIndex; i < right-1; i++)

ينبغي أن تصبح:

for (int i = left; i < right; i++)

تفحص ال مقالة ويكيبيديا ذات الصلة الذي يقول:

function partition(array, left, right, pivotIndex)
     pivotValue := array[pivotIndex]
     swap array[pivotIndex] and array[right] // Move pivot to end
     storeIndex := left
     for i  from  left to right - 1 // left ≤ i < right  
         if array[i] ≤ pivotValue 
             swap array[i] and array[storeIndex]
             storeIndex := storeIndex + 1
     swap array[storeIndex] and array[right] // Move pivot to its final place
     return storeIndex

تنويه: left ≤ i < right