QuickSort request

[•HexString]

Poate sa imi dea si mie cineva, QuickSort-ul ?

[•devilkind]

http://frankeman.sitesfree.com/licenta/sortarea_rapida.html

il ai aici explicat in romana, numai bun de inteles.

[•HexString]

Este cel mai eficient algoritm de sortare? Am inteles ca s-a dat anu trecut la OJI cls a7a sau ceva de genul ceva prob, unde era cva modificare pe quicksort care il facea mai eficient, ceva cu mijloc... , nu mai tin bine minte.

[•wefgef]

Este unul dintre cei mai eficienti algoritmi de sortare pe loc pe cazul mediu.

[•HexString]

Multumesc, am gasit ce am cautat, era vb de qs, doar ca isi lua pivotul de pe mijloc, nu de pe prima pozitie, si scapa de cateva parcurgeri.

[•rEbyTer]

Dacă funcţia înlocuieşte este definită inline atunci quicksortul este un pic mai performat ? (in cazul in care sunt multe elemente)

Cod:

void inlocuieste(int *a, int *b)
{

      int c = *a;
      *a = *b;
      *b = c;

}

[•fireatmyself]

mai bine nu o faci functie separata. atunci sigur va fi mai rapid. nu stiu care e treaba cu 'inline'. pe unele evaluatoare mi-a mers mai repede, pe altele nu. 

[•amadaeus]

De obicei compilatoarele expandeaza inline functiile simple (de genul swap) in etapa de optimizare. De asta s-ar putea ca in unele cazuri sa nu faca diferenta daca specifici in mod explicit acest lucru. In general poti lasa compilatorul sa decida care functii vor fi expandate si care nu, se descurca destul de bine

Ca tot veni vorba de swap, ca sa schimbi valorile a doua int-uri poti scrie (in C)

Cod:

a^=b^=a^=b;

Incearca si vezi de ce functioneaza (a^=b inseamna a = a xor b, iar expresia de mai sus este parsata de la dreapta spre stanga)

[•wefgef]

Puteti citi mai multe despre inline-uri aici.

[•mordred]

am si eu o intrebare, poate putin off-topic: quicksortu' asta e mai putin performant? ca eu prefer varianta asta fata de cea de pe wikipedia

Cod:

void quicksort(int start, int end){
if(end-start<1) return;
int pivot = x[start], i = start, k = end;
while(k>i)
    {
    while(x[i]<=pivot && i<=end && k > i)
        ++i;
    while(x[k]>pivot && k>=start && k>=i)
        --k;
    if(k>i){
        aux = x[i];
        x[i] = x[k];
        x[k] = aux;
        }
    }
aux = x[start];
x[start] = x[k];
x[k] = aux;
quicksort(start,k-1);
quicksort(k+1,end);
}

[•wefgef]

In general e bine sa alegi pivotul random. In rest, implementarea ta seamana cu cea pe care o foloseam si eu.

[•mordred]

am inteles, mersi