الگوریتم Quick Sort

Question

سلام، میخواستم الگوریتم QuickSort رو با این فرض که میخوایم آرایه ی A رو مرتب کنیم، بنویسید همراه با مقداری توضیح لطفا. (فقط الگوریتم؛ لطفا کد ننویسید)

Answer 1

Quick sort هم الگوریتمیه که از روش Divide and conquer استفاده می کنه یعنی ما  مساله رو به صورت بازگشتی به مسایل کوچیکتر تقسیم می کنیم و وقتی که مساله به اندازه کافی کوچیک شد حل می کنیم و جواب هایی که بدست میاد رو ترکیب می کنیم تا جواب کامل رو داشته باشیم

توی Quick sort به این شکل عمل می کنیم که :

۱ـ یک عنصر به عنوان Pivot انتخاب می کنیم

۲ـ عناصری که از pivot کوچیکترن رو قبلش و عناصر بزرگتر رو بعد از اون قرار میدیم .(به این مرحله partition میگیم )

۳ـ وقتی که محل جدید pivot بدست آمد ما عملیات ۱ به بعد روبرای آرایه های سمت چپ و راست pivot  تا زمانی که اندازه آرایه های سمت چپ و راست ۱ نشدن دوباره تکرار می کنیم .

 

مثلا این آرایه رو در نظر بگیرید : 4-6-5-3-1-7-8-2

فرض می کنیم که pivot رو  همیشه به عنوان عنصر آخر در نظر بگیریم .

الگوریتم بعد از یک بار انجام مرحله partition به شکل زیر  در میاد (همون طوری که از شکل مشخصه هر بار آرایه رو به قسمت های کوچکتر تقسیم میکنیم (devide) و  روی قسمت های کوچیک تر partition انجام میشه  (conquer) .)

 

 

partition هم به این شکل کار می کنه که ما اندیس شروع با اسم p (با مقدار اولیه start )  در نظر می گیریم شروع به پیمایش آرایه می کنیم هر وقت که یک عنصر کمتر از pivot ما وجود داشت خونه ی p ام رو با  عنصری که کمتر بوده  جابه جا می کنیم و p  رو هم یک واحد اضافه می کنیم

نهایتا هم pivot رو با عنصر p ام جا به جا می کنیم  ( عکس از کتاب CLRS )

 

 

کد سی پلاس پلاس  Quick sort به این شکله :

#include <iostream>

using namespace std;

int partition(int* arr,int start,int end)
{
    int pivotLocation=start;
    int pivot=arr[end];//in ja be jaye end agar az median estefade konim behtar hast
    for(int i=start;i<end;i++)
    {
        if(arr[i]<pivot)
        {
            swap(arr[pivotLocation],arr[i]);
            pivotLocation++;
        }
    }
    swap(arr[pivotLocation],arr[end]);
    return pivotLocation;
}
void quickSort(int* arr,int start,int end)
{
    if(start >= end)
        return;
    int pivotLocation=partition(arr,start,end);
    quickSort(arr,start,pivotLocation-1);
    quickSort(arr,pivotLocation+1,end);
}

int main ()
{
    int arr[]={5,2,7,8,2,4,3,9};

    quickSort(arr,0,7);

    for(auto i:arr)
        cout<<i;

    return 0;
}

 

این الگوریتم زمانی بدترین حالتش رخ میده که تمام pivot هایی که انتخاب میشن در هر مرحله  بزرگترین یا کوچیکترین عنصر باشن   (یکی از جاهایی که رخ میده زمانی هستش که آرایه کاملا مرتب باشه )

برای بهتر انتخاب کردن pivot  و جلوگیری از بدترین حالت  از روش های آماری استفاده می کنن مثلا pivot روهر مرحله  بصورت  میانه ۳ تا عنصر از این آرایه در نظر می گیرن .

 

Comments

سلام
برای جلوگیری از بوجود اومدن بدترین حالت مگه random  عمل نمیکنن ؟

---

سلام نه .همون طوری که 2 خط آخر هم گفتم  روشی که بیشتر استفاده میشه همون گرفتن مدیان 3 عنصر اول وسط و آخر هستش (Median-of-three) یعنی از بین عنصر اول آخر و وسط  آرایه عنصر با مقدار میانی انتخاب میشه .
مثلا پیاده سازی std::sort ویژوال استودیو هم از میانه استفاده کرده .

---

متن ویکیپدیا هم که در همین مورده جالبه :
Specifically, the expected number of comparisons needed to sort n elements with random pivot selection is 1.386 n log n. Median-of-three pivoting brings this down to 1.188 n log n, at the expense of a three-percent increase in the expected number of swaps.An even stronger pivoting rule, for larger arrays, is to pick the ninther, a recursive median-of-three, defined as
ninther(a) = median(median-of-three(first ⅓ of a), median-of-three(middle ⅓ of a), median-of-three(final ⅓ of a))

Answer 2

#include <iostream>
using namespace std;

const int INPUT_SIZE = 10;

// A simple print function
void print(int *input)
{
    for ( int i = 0; i < INPUT_SIZE; i++ )
        cout << input[i] << " ";
    cout << endl;
}

// The partition function
int partition(int* input, int p, int r)
{
    int pivot = input[r];

    while ( p < r )
    {
        while ( input[p] < pivot )
            p++;

        while ( input[r] > pivot )
            r--;

        if ( input[p] == input[r] )
            p++;
        else if ( p < r )
        {
            int tmp = input[p];
            input[p] = input[r];
            input[r] = tmp;
        }
    }

    return r;
}

// The quicksort recursive function
void quicksort(int* input, int p, int r)
{
    if ( p < r )
    {
        int j = partition(input, p, r);        
        quicksort(input, p, j-1);
        quicksort(input, j+1, r);
    }
}

int main()
{
    int input[INPUT_SIZE] = {500, 700, 800, 100, 300, 200, 900, 400, 1000, 600};
    cout << "Input: ";
    print(input);
    quicksort(input, 0, 9);
    cout << "Output: ";
    print(input);
    return 0;
}

order از o(n*logn در بهترین حالت و در بدترین حالات o(n*n)

Comments

توضیح؟‌‌‌‌‌‌‌‌‌‌‌

---

کجاشو نمی فهمی؟

---

توضیح کلی (که وظیفه ی هر بخش چیه و صورت کلی الگوریتم به چه شکلی هست)