Quicksort لا يعمل

Question

هذا هو كل الكود الخاص بي لطريقة Quicksort الخاصة بي ، فهو يعمل على مجموعة من 21 رقمًا ، ولكن ليس على مجموعة البيانات الحقيقية الخاصة بي ، أي حوالي 100000. مستحق قريبا! أي مساعدة سيكون موضع ترحيب كبير

public static void hybridQuicksort( int[] a, int start, int end )
{
    final int MIN = 13;
    if ( end - start >= MIN )
    {
        int pivot = findPivot( a, start, end );
        pivot = partition ( a, start, end, pivot );
        hybridQuicksort( a, start, pivot - 1 );
        hybridQuicksort( a, pivot + 1, end);
    }
    else
    {
        insertionSort( a, start, end );
    }
}

//partitions the array based on the pivot
public static int partition( int[] a, int start, int end, int pivot )
{
    int up = start + 1;
    int down = end;

    while ( up <= down )
    {

        while ( a[up] <= pivot)
            up++;

        while ( a[down] > pivot)
            down--;

        if ( up <= down )
            swap( a, up, down );
    }

    swap( a, start, down );

    return up;
}

//finds the first, middle, middle of first and middle, middle of middle and last
//and last numbers and sets their median as the pivot
public static int findPivot( int[] a, int start, int end )
{
    //swap the 4 numbers to the start of the array, leaving the first as is
    swap( a, start + 1, end - 1 );
    swap( a, start + 2, (start + end) / 2);
    swap( a, start + 3, end / 4);
    swap( a, start + 4, (end / 2) + (end / 4) );

    //sort the 5 numbers
    insertionSort( a, 0, 5 );

    //swap the median to the front, that's the pivot
    swap( a, start, start + 2 );
    //return the pivot
    return a[start];
}

Answer 1

افتراض:

• يحمل 10،000 عينة ،
• البداية هي 500

• نهاية 1000

  //swap the 4 numbers to the start of the array, leaving the first as is
  swap( a, start + 1, end - 1 );
  swap( a, start + 2, end / 2);
  swap( a, start + 3, end / 4);
  swap( a, start + 4, (end / 2) + (end / 4) );
  

نهاية/4 هو 250

.. أنت تبديل القيم من خارج مجموعة الفرز.

Answer 2

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

هذا هو هواة في العمل. ما يحتاجه ليس مجرد إجابة. إنه يحتاج إلى مقاربة لحل المشكلات الصعبة. Quicksort هو مجرد وسيلة لهذا التعليم.

هذا هو نهج بلدي.

الحيلة هي كتابة Quicksort كما Quicksort ، والوصول إليها ، ثم القلق بشأن الحيل الخاصة الهوى. اقتل الضوضاء حول الإدراج في فرز فترات صغيرة. فقط افترض أن أي فاصل زمني من الصفر أو واحد يتم فرزه بالفعل (وهو حالتك الأساسية) ثم العمل على جعل رمز التقسيم الخاص بك يعمل باستخدام الطرف الأيسر من الفاصل الزمني مثل المحور (كما في Quicksort الأصلي الكلاسيكي) ، ويمكنك أن تكون فكر في طباعة نتائج بياناتك بعد تمرير تقسيم واحد كوسيلة لإظهار نفسك أنها تعمل. سوف تقوم بتطوير مهارات الاختبار بهذه الطريقة. على أي حال ، بمجرد حصولك على Quicksort ، يمكنك القيام بأشياء مثل التحديد المحوري المنفصل في وظيفة واللعب مع التنفيذ.

حظا سعيدا ، واستمتع بمشروعك. لا تنسى ، رغم ذلك: نريد توقيتات ، وخاصة المقارنات الزمنية مع روتين الفرز في المكتبة القياسية!