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

مرتب‌سازی سریع (Quick Sort) یک نوع مرتب‌سازی مقایسه‌ای با مرتبه زمانی $\mathcal{\Theta}(n ^ 2)$ است که امید ریاضی تعداد مقایسه‌های آن از $\mathcal{\Theta}(n \log n)$ است.

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

هر دو عضو از آرایه اصلی حداکثر یک بار با هم مقایسه می‌شوند پس تعداد مقایسه ها حداکثر $n ^ 2$ است. از طرفی اگر در هر مرحله کوچک ترین عنصر به عنوان $\mathop{pivot}$ انتخاب شود تعداد مراحل $n - 1$ می‌شود و هر دو عنصر دقیقا یک بار با هم مقایسه می‌شوند. پس الگوریتم مرتب‌سازی سریع دارای مرتبه زمانی $\mathcal{\Theta}(n ^ 2)$ در بدترین حالت است. البته با توجه به تصادفی انتخاب کردن $\mathop{pivot}$ امید ریاضی تعداد مقایسه ها از $\mathcal{\Theta}(n \log n)$ است. زیرا به ازای دو عنصر مختلف در آرایه اگر اولی مکان $i$‌ ام بعد از مرتب سازی و دومی مکان $j$ ام بعد از مرتب سازی داشته باشد آنگاه احتمال مقایسه این دو عنصر برابر $\frac{|i - j| + 1}{2}$ می‌شود که این مقدار برابر است با احتمال آنکه عنصر $i$ یا $j$ نسبت به عناصر بین آن‌ها بعد از مرتب‌سازی زود‌تر بعنوان $\mathop{pivot}$‌ انتخاب شوند. در نتیجه امید ریاضی تعداد مقایسه‌ها برابر است با $\sum_i \sum_j \frac{|i - j| + 1}{2}$ که از $\mathcal{\Theta}(n \log 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;
}

• https://en.wikipedia.org/wiki/Quicksort