● Quicksort, partition-exchange sort

در این نوع از مرتب سازی، یک خانه از آرایه ی دریافتی را به عنوان محور انتخاب می کنیم و تمام اعداد کوچکتر از آنرا به سمت چپ آن و تمام اعداد بزرگتر از آنرا به سمت راست آن می بریم. حال دو بخش جدید "چپ" و "راست" را به روش مقایسه ای از خانه ی 0 تا Size-1 در کنار یکدیگر می گذاریم.

برای آشنایی بیشتر با این الگوریتم، به فصل "الگوریتم های مرتب سازی" از کتاب Introduction to Algorithms مراجعه کنید.

input

5
1376 -7 7 10506 999

output

-7 7 999 1376 10506

ورودی:

خط اوّل، شامل عدد طبیعی n نشان دهنده ی تعداد اعدادی که باید مرتب شوند است.

و n عدد بعدی، به صورت یک آرایه از اعداد صحیح به اسم a از ورودی دریافت می شود. a_i ها در ابتدا ترتیب خاصی ندارند.

خروجی:

به عنوان خروجی، آرایه ی داده شده را به روش Quicksort مرتب کرده، و چاپ کنید.

// A Drop of the Programming Sea - adops.blog.ir

#include <iostream>
using namespace std;

int* sort(int*, int);

int main()
{
    int size;
    cin >> size;
    int* a = new int [size];
    for(int i = 0; i<size; i++)
        cin >> a[i];
    a = sort(a, size);
    for(int i=0; i<size; i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

int* sort(int* array, int size)
{
    if(size < 2)
        return array;
    int tedad1 = 0, tedad2=0,mehvar = array[0];
    for(int i =1 ; i<size; i++)
    {
        if(array[i] < mehvar)
            tedad1++;
        else
            tedad2++;
    }
    int* aval =  new int[tedad1];
    int* dovom = new int[tedad2];
    int a=0,b=0;
    for(int i=1 ; i<size ; i++ )
    {
        if(array[i] < mehvar)
        {
            aval[a] = array[i];
            a++;
        }
        else
        {
            dovom[b] = array[i];
            b++;
        }
    }
    aval = sort(aval,tedad1);
    dovom = sort(dovom,tedad2);
    int i=0;
    for(; i<tedad1; i++)
        array[i]=aval[i];
    array[i]=mehvar;
    i++;
    for(; i<size; i++)
        array[i]=dovom[i-(tedad1+1)];
    return array;
}