تعديل هذا الفرز السريع لاستخدام العنصر الأخير دائمًا كمحور

Question

لدي ما يلي فرز سريع الذي يختار دائمًا العنصر الأول من التسلسل كمحور له:

void qqsort(int array[], int start, int end) {
    int i = start; // index of left-to-right scan
    int k = end; // index of right-to-left scan

    if (end - start >= 1) { // check that there are at least two elements to sort 
        int pivot = array[start]; // set the pivot as the first element in the partition
        while (k > i) { // while the scan indices from left and right have not met, 
            while (array[i] <= pivot && i <= end && k > i)  // from the left, look for the first element greater than the pivot
                i++;
            while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first element not greater than the pivot
                k--;
            if (k > i) // if the left seekindex is still smaller than the right index, swap the corresponding elements
                swap(array, i, k);              
        }
        swap(array, start, k); // after the indices have crossed, swap the last element in the left partition with the pivot 
        qqsort(array, start, k - 1); // quicksort the left partition
        qqsort(array, k + 1, end); // quicksort the right partition
    } else { // if there is only one element in the partition, do not do any sorting 
        return;
    }
}

الآن كما ترون، تأخذ هذه الخوارزمية دائمًا العنصر الأول ليكون المحور: int pivot = array[start];

أريد تعديل هذه الخوارزمية لجعلها تستخدم دائمًا العنصر الأخير بدلاً من العنصر الأول في التسلسل اللاحق، لأنني أريد تحليل أوقات التشغيل الفعلية لكلا التطبيقين.

حاولت تغيير الخط int pivot = array[start]; ل int pivot = array[end]; لكن الخوارزمية أخرجت بعد ذلك تسلسلاً غير مصنف:

//Changes: int pivot = array[end]; 
unsorted: {5 4 3 2 1}
*sorted*: {1 2 5 4 3}

لاختبار محور آخر، حاولت أيضًا استخدام العنصر المركزي للتسلسل اللاحق ولكن الخوارزمية ما زالت فاشلة:

//Changes: int pivot = array[(start + end) / 2]; 
unsorted: {5 3 4 2 1}
*sorted*: {3 2 4 1 5}

---

هل يمكن لأي شخص أن يساعدني في فهم هذه الخوارزمية بشكل صحيح ويخبرني ما هي التغييرات التي يجب علي إجراؤها لكي ينجح هذا التنفيذ دائمًا في اختيار العنصر الأخير من التسلسل باعتباره المحور؟

Answer 1

سبب المشكلة

المشكلة هي أنك تستخدم int k = end;. كان من الجيد الاستخدام int i = start; عندما كان لديك العنصر المحوري كعنصر أول في الصفيف لأن الشيكات الخاصة بك في الحلقة سوف تتخطىها (array[i] <= pivot). ومع ذلك ، عند استخدام العنصر الأخير كحور ، يتوقف K في فهرس النهاية ويحول المحور إلى موضع في النصف الأيسر من القسم. أنت بالفعل في ورطة لأن محورك سيكون على الأرجح في مكان ما داخل القسم الأيسر وليس على الحدود.

الحل

لإصلاح هذا ، تحتاج إلى ضبط int k = end - 1; عند استخدام العنصر أقصى اليمين مثل المحور. ستحتاج أيضًا إلى تغيير خطوط تبديل المحور على الحدود بين الأقسام اليسرى واليمنى:

swap(array, i, end);
qqsort(array, start, i - 1);
qqsort(array, i + 1, end);

يجب عليك استخدام هذا لأنني سأنتهي في أقصى اليسار من القسم الأيمن (والذي يمكن بعد ذلك تبديله مع وجود المحور في أقصى اليمين وسيحافظ على الترتيب). أخيرًا ، سترغب في التغيير k >= i إلى k > i في الوقت الذي يقلل من k أو هناك تغيير بسيط في خطأ فهرسة الصفيف [-1]. لم يكن هذا ممكنًا من قبل لأنني كنت دائمًا على الأقل مساوياً لـ I+1 بهذا النقطة.

يجب أن تفعل ذلك.

ملاحظة جانبية:

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

Answer 2

لم أختبرها ، لكن تحقق من ذلك على أي حال:

هذه

// after the indices have crossed,
// swap the last element in the left partition with the pivot
swap(array, start, k);

ربما ينبغي أن يكون

swap(array, end, i);

أو شيء مشابه ، إذا اخترنا end كما المحور.

يحرر: هذه خوارزمية تقسيم مثيرة للاهتمام ، لكنها ليست اساسي واحد.

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

الطريقة الوحيدة التي أحسب بها استخدام محور مختلف ، دون تغيير الخوارزمية ، هي:

...
if (end - start >= 1) {
    // Swap the 1st element (Head) with the pivot
    swap(array, start, pivot_index);
    int pivot = array[start];
...

Answer 3

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

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

التلميح الثالث:تم التعليق على الكود الذي قدمته بشكل مفرط.يجب أن تكون قادرًا على فهم هذا التنفيذ فعليًا.

Answer 4

ضع واحدة

swap(array, start, end)

قبل تهيئة المحور

int pivot = array[start]

Answer 5

#include <time.h>
#include <stdlib.h>
#include<iostream>
#include<fstream>
using namespace std;

int counter=0;
void disp(int *a,int n)
{
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}

void swap(int a[],int p,int q)
{

int temp;
temp=a[p];
a[p]=a[q];
a[q]=temp;

}

int partition(int a[], int p, int start, int end)
{
swap(a,p,start);// to swap the pivot with the first element of the partition
counter+=end-start;  // instead of (end-start+1)
int i=start+1;
for(int j=start+1 ; j<=end ; j++)
{
    if(a[j]<a[start])
    {
        swap(a,j,i);
        i++;

    }


}
swap(a,start,i-1);  // not swap(a,p,i-1) because p and start were already swaped.....    this was the earlier mistake comitted
return i-1; // returning the adress of pivot
}

void quicksort(int a[],int start,int end)
{
if(start>=end)
    return;


int p=end; // here we are choosing last element of the sub array as pivot
// here p is the index of the array where pivot is chosen randomly

int index=partition(a,p,start,end);

quicksort(a,start,index-1);
quicksort(a,index+1,end);

}

int main()
{

ifstream fin("data.txt");
int count=0;

int array[100000];

while(fin>>array[count])
{
    count++;
}
quicksort(array,0,count-1);
/*
int a[]={32,56,34,45,23,54,78};
int n=sizeof(a)/sizeof(int);
disp(a,n);

quicksort(a,0,n-1);
disp(a,n);*/
cout<<endl<<counter;
return 0;

}

Answer 6

إذا بدأت في مراقبة كل عنصر من العنصر الأول من المصفوفة إلى الأخير - 1 ، مع الحفاظ على العنصر الأخير كمحور في كل عودية ، فستحصل على الإجابة بشكل دقيق س (Nlogn) زمن.

#include<stdio.h>
void quicksort(int [], int, int);
int main()
{
int n, i = 0, a[20];
scanf("%d", &n);
while(i < n)
scanf("%d", &a[i++]);

quicksort(a, 0, n - 1);
i = 0;
while(i < n)
printf("%d", a[i++]);

}
void quicksort(int a[], int p, int r)
{
int i, j, x, temp;
if(p < r)
{
    i = p;
    x = a[r];
    for(j = p; j < r; j++)
    {
        if(a[j] <= x)
        {
            if(a[j] <a[i])
            {
                temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
            i++;
        }

        else
        {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    if(x != i)
    {
        temp = a[r];
        a[r] = a[i];
        a[i] = temp;
    }

    quicksort(a, p, i - 1);
    quicksort(a, i + 1, r);
}
}