خوارزمية التقسيم Quicksort

Question

أحاول برمجة خوارزمية Quicksort من كتاب Cormen خوارزمية. أدناه هو الكود الخاص بي.

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 

هل يمكن لأي شخص أن يشرح ما هو الخطأ. لقد قمت بتطبيق هذا الرمز تمامًا كما هو موضح في كتاب "مقدمة إلى الخوارزميات". شكرًا لك.

Answer 1

لا ، لم تقم بنسخه مباشرة :) لدي هنا ...

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. وتذكر أن الكتاب يحتوي على صفائف تبدأ من 1 وليس 0. لذا يجب "نسخ" الخوارزميات في الكتاب عمومًا بعناية فائقة أو مع صفائف تمر من 1.

تحرير: معلومات حول الخوارزمية للتعليقتأخذ الخوارزمية في الكتاب العنصر الأخير كمحور. وبالتالي فإنه سيجعلها خوارزمية رهيبة للصفائف التي تم فرزها بالفعل. سينتهي الأمر في O (n^2) لذلك لا ينبغي لأحد أن يستخدم هذه الخوارزمية في الإنتاج (إلا إذا كنت تعرف ما تفعله وما هي مدخلاتك) لأن المصفوفات تميل إلى أن يتم فرزها إلى حد ما. خوارزمية بناء Java أكثر ذكاءً ويمكنك أن تقرأ عنها في Javadoc

Answer 2

إذا كنت تريد بعض المرجع حول كيفية تنفيذ الفرز السريع ، فيمكنك محاولة التحقق من رمز المصدر الفعلي للصفائف. ((http://www.oracle.com/technetwork/java/javase/downloads/index.html للتنزيل إذا لم يكن لديك بالفعل src.zip في تثبيت JDK الخاص بك).

Answer 3

توفير تطبيق آخر في Java. ويستند أيضًا إلى نفس الخوارزمية ويعتني بالعناصر المكررة في الصفيف أيضًا.

    public void sort( int[] inputArray, int lo, int high){
          int pivotIndex = partition(inputArray,lo,high);
         System. out .println("Got PivotIndex as " + pivotIndex);
          if (lo < pivotIndex -1)
                sort(inputArray,lo,pivotIndex - 1);
          if (pivotIndex+1 < high)
                sort(inputArray,pivotIndex+1,high);
          return ;
    }

    private int partition( int[] inputArray, int leftPtr,int rightPtr)
   {
         printArray(inputArray);
          int pivot = inputArray[leftPtr];
          while (leftPtr<rightPtr){
                 while (inputArray[leftPtr]<pivot)
                       leftPtr++;
                 while (inputArray[rightPtr]>pivot)
                       rightPtr--;
                 if (leftPtr<rightPtr)
                {
                       exchange(inputArray,leftPtr,rightPtr);

                          //Cases which have repeated numbers...
                        if (inputArray[leftPtr] == inputArray[rightPtr])
                             leftPtr++;
                }
         }
          return leftPtr;//return any one
   }