QuickSort مع التقسيم 3 اتجاه

Question

ما هو QuickStort مع قسم 3 في الاتجاه؟

Answer 1

صورة صفيف:

3, 5, 2, 7, 6, 4, 2, 8, 8, 9, 0

أ قسمين فرز سريع من شأنه اختيار قيمة، ويقول 4، ووضع كل عنصر أكبر من 4 على جانب واحد من الصفيف وكل عنصر أقل من 4 على الجانب الآخر. مثل ذلك:

3, 2, 0, 2, 4, | 8, 7, 8, 9, 6, 5

أ ثلاثة قسم فرز سريع سوف تختار قيمتين لتقسيم وتقسيم مجموعة تصل إلى هذه الطريقة. يتيح اختيار 4 و 7:

3, 2, 0, 2, | 4, 6, 5, 7, | 8, 8, 9

إنه مجرد تباين بسيط على الفرز السريع العادي.

يمكنك الاستمرار في تقسيم كل قسم حتى يتم فرز الصفيف. وقت التشغيل هو nlog من الناحية الفنية₃(ن) والتي تختلف قليلا قليلا من NLOG العادي QuickSort₂(ن).

Answer 2

http://www.sorting-algorithms.com/static/quicksortisoptimal.pdf.

أنظر أيضا:

http://www.sorting-algorithms.com/quick-sort-3-way.

اعتقدت أن نسخة سؤال المقابلة مثيرة للاهتمام أيضا. يسأل، هل هناك أربعة إصدارات التقسيم من QuickSort...

Answer 3

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

Answer 4

أعتقد أن القسم ذو الاتجاهين هو djstrka.

فكر في صفيف مع العناصر { 3, 9, 4, 1, 2, 3, 15, 17, 25, 17 }.

أساسا قمت بإعداد 3 أقسام: أقل من، يساوي، وأكبر من محور معين. لا يحتاج التقسيم المساوي إلى مزيد من الفرز لأن جميع عناصرها متساوية بالفعل.

---

على سبيل المثال، إذا اخترنا الأول 3 كما المحور، ثم قسم 3 اتساع باستخدام dijkstra من شأنه أن يرتب الصفيف الأصلي وإرجاع مؤشرين m1 و m2 بحيث تكون جميع العناصر التي مؤشرها أقل من m1 سيكون أقل من 3, ، جميع العناصر التي مؤشرها أكبر من أو يساوي m1 وأقل من أو يساوي m2 سيكون مساويا 3, وجميع العناصر التي مؤشرها أكبر من m2 سيكون أكبر من 3.

في هذه الحالة بالذات، يمكن أن يكون الصفيف الناتج { 1, 2, 3, 3, 9, 4, 15, 17, 25, 17 }, والقيم m1 و m2 سيكون m1 = 2 و m2 = 3.

لاحظ أن الصفيف الناتج يمكن أن يتغير اعتمادا على الاستراتيجية المستخدمة في التقسيم، ولكن الأرقام m1 و m2 سيكون هو نفسه.

Answer 5

أعتقد أنه يرتبط طريقة تقسيم Dijkstra حيث يكون القسم من العناوين الأصغر، على قدم المساواة، وأكبر من المحور. فقط الأقسام الأصغر والأكبر يجب أن يتم فرزها بشكل متكرر. يمكنك رؤية التصور التفاعلي واللعب معها في الجوز. وبعد الألوان التي استخدمتها هناك حمراء / أبيض / أزرق لأن طريقة التقسيم تسمى عادة "مشكلة العلم الهولندي"

Answer 6

3 طريقة الفرز السريع أساسا أقسام الصفيف في 3 أجزاء. الجزء الأول أقل من المحور، الجزء الثاني يساوي المحور والجزء الثالث أكبر من pivot.it خوارزمية التقسيم الخطي. يشبه هذا القسم مشكلة العلم الوطني الهولندي.

Answer 7

  //code to implement Dijkstra 3-way partitioning

  package Sorting;

  public class QuickSortUsing3WayPartitioning {

private int[]original;
private int length;
private int lt;
private int gt;

public QuickSortUsing3WayPartitioning(int len){
    length = len;
    //original = new int[length];

    original = {0,7,8,1,8,9,3,8,8,8,0,7,8,1,8,9,3,8,8,8};

}

public void swap(int a, int b){ //here indexes are passed
    int temp = original[a];
    original[a] = original[b];
    original[b] = temp;
}

public int random(int start,int end){
    return (start + (int)(Math.random()*(end-start+1)));
}

public void partition(int pivot, int start, int end){
    swap(pivot,start);  // swapping pivot and starting element in that subarray

    int pivot_value = original[start];
    lt = start;
    gt = end;

    int i = start;
    while(i <= gt) {

        if(original[i] < pivot_value) {
            swap(lt, i);
            lt++;
            i++;
        }

        if(original[i] > pivot_value) {
            swap(gt, i);
            gt--;
        }
        if(original[i] == pivot_value)
            i++;
    }
}

public void Sort(int start, int end){
    if(start < end) {

        int pivot = random(start,end); // choose the index for pivot randomly
        partition(pivot, start, end); // about index the array is partitioned

        Sort(start, lt-1);
        Sort(gt+1, end);

    }
}

public void Sort(){
    Sort(0,length-1);
}

public void disp(){
    for(int i=0; i<length;++i){
        System.out.print(original[i]+" ");
    }
    System.out.println();
}

public static void main(String[] args) {

    QuickSortUsing3WayPartitioning qs = new QuickSortUsing3WayPartitioning(20);
    qs.disp();

    qs.Sort();
    qs.disp();

}

}