Cod sursa(job #2760182)

Utilizator dey44andIoja Andrei-Iosif dey44and Data 23 iunie 2021 15:16:20
Problema Sortare prin comparare Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <ctime>
#include <cstdlib>

using namespace std;

ifstream cin("algsort.in");
ofstream cout("algsort.out");

int a[500005], N;

int Lomuto_Part(int L, int R)
{
    int p = L + rand() % (R - L);
    swap(a[L], a[p]);
    int st = L, dr = R, x = a[st];
    while(st < dr)
    {
        while(st < dr && a[dr] >= x) dr--;
        a[st] = a[dr];
        while(st < dr && a[st] <= x) st++;
        a[dr] = a[st];
    }
    a[st] = x;
    return st;
}

int Hoare_Part(int L, int R)
{
    int p = L + rand() % (R - L);
    swap(a[L], a[p]);
    int st = L - 1, dr = R + 1, x = a[L];
    while(true)
    {
        do
        {
            st++;
        }while(a[st] < x);
        do
        {
            dr--;
        }while(a[dr] > x);
        if(st >= dr) return dr;
        swap(a[st], a[dr]);
    }
}

void QuickSort(int L, int R)
{
    if(L < R)
    {
        int M = Hoare_Part(L, R);
        QuickSort(L, M);
        QuickSort(M + 1, R);
    }
}

int main()
{
    srand(time(NULL));
    cin >> N;
    for(int i = 1; i <= N; i++)
        cin >> a[i];
    QuickSort(1, N);
    for(int i = 1; i <= N; i++)
        cout << a[i] << " ";
    return 0;
}