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

مرتب‌سازی سریع یک نوع مرتب‌سازی مقایسه ای با مرتبه زمانی $\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)$ است.

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;
}