====== مرتب‌سازی سریع ======


===== تعریف =====

مرتب‌سازی سریع یک نوع مرتب‌سازی مقایسه ای با مرتبه زمانی $\theta(n ^ 2)$ است که امید ریاضی تعداد مقایسه های آن از $\theta(n lg n)$ است.


===== الگوریتم =====

در این روش مرتب سازی در هر مرحله اگر سایز آرایه یک بود که خود آرایه مرتب است. در غیر اینصورت یک عنصر از آرایه را تصادفی انتخاب کرده و آن را $pivot$ می نامیم. سپس با $n$ مقایسه بقیه عناصر آرایه را به دو دسته ۱- عناصر کوچک‌تر مساوی $pivot$  ۲- عناصر بزرگ‌تر از $pivot$ تقسیم می کنیم. حال دو دسته جدید را به همین صورت مرتب می کنیم.

===== پیچیدگی‌ الگوریتم =====

هر دو عضو از آرایه اصلی حداکثر یکبار با هم مقایسه می شوند پس تعداد مقایسه ها حداکثر $n ^ 2$ است. از طرفی اگر در هر مرحله کوچک ترین عنصر به عنوان $pivot$ انتخاب شود تعداد مراحل $n-1$ می شود و هر دو عنصر دقیقا یکبار با هم مقایسه می شوند. پس الگوریتم مرتب‌سازی سریع دارای مرتبه زمانی $\theta(n ^ 2)$ است. البته با توجه به تصادفی انتخاب کردن $pivot$ امیدریاضی تعداد مقایسه ها از $\theta(n lg n)$ است. زیرا به ازای دو عنصر مختلف در آرایه اگر اولی مکان $i$‌ ام بعد از مرتب سازی و دومی مکان $j$ ام بعد از مرتب سازی داشته باشد آنگاه احتمال مقایسه این دو عنصر برابر $ 2 ÷ (|i-j|+1)$ می شود که این مقدار برابر است با احتمال آنکه عنصر $i$ یا $j$ نسبت به عناصر بین آن ها بعد از مرتب سازی زود‌تر به‌عنوان $pivot$‌ انتخاب شوند. در نتیجه امیدریاضی تعداد مقایسه ها برابر است با $\Sigma \Sigma (2 ÷ (|i-j|+1)$ که از $\theta(n lg n)$ است.

===== پیاده‌سازی =====

<code c++ Qsort.cpp>
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;

const int maxn=1e5;
int n, a[maxn], b[maxn];

void Qsort(int l,int r)
{
    if(r-l <= 1) return;

    copy(a+l, a+r, b);
    int pivot = b[rand() % (r - l)];
    int cnt = 0;
    for(int i=0;i<r-l;i++)
    {
        if(b[i] <= pivot)
            a[l+(cnt++)] = b[i];
        else
            a[r-(i-cnt+1)] = b[i];
    }

    for(int i=l;i<r;i++)
        if(a[i] == pivot)
         swap(a[i], a[l+cnt-1]);
    Qsort(l, l+cnt-1);
    Qsort(l+cnt, r);
}

int main()
{
    srand (time(NULL));
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    Qsort(0, n);

    for(int i=0;i<n;i++)
        cout<<a[i]<<' ';
    cout<<endl;
}
</code>