Cod sursa(job #1215534)

Utilizator flore77Simion Florentin flore77 Data 1 august 2014 12:28:06
Problema Sortare prin comparare Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
using namespace std;

void swap (int &a, int &b)
{
    int aux = a;
    a = b;
    b = aux;
}

int partition (int v[], int st, int dr)
{
    int i = 0, j = 1;
    while (st < dr)
    {
        if (v[st] > v[dr])
        {
            swap(v[st], v[dr]);
            swap(i,j);
        }
        st += i;
        dr -= j;
    }
    return st;
}

void qsort (int *v, int st, int dr)
{
    if (dr - st > 1)
    {
        int p = partition(v, st, dr);
        qsort(v, st, p - 1);
        qsort(v, p + 1, dr);
    }
    else
    {
        if (v[st] > v[dr])
            swap(v[st], v[dr]);
    }
}

int main()
{
    ifstream in("algsort.in");
    int n, *v, i;
    in >> n;
    v = new int[n];
    for (i = 0; i < n; i++)
        in >> v[i];
    in.close();
    qsort(v, 0, n - 1);
    ofstream out("algsort.out");
    for (i = 0; i < n; i++)
        out << v[i] << " ";
    return 0;
}