Imprimă pagina - QuickSort request

Titlul: QuickSort request
Scris de: Maritanu Codrut Catalin din Aprilie 08, 2008, 11:33:15

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

Titlul: RÄƒspuns: QuickSort request
Scris de: Savin Tiberiu din Aprilie 08, 2008, 11:45:10

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

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

Titlul: RÄƒspuns: QuickSort request
Scris de: Maritanu Codrut Catalin din Aprilie 08, 2008, 11:52:52

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.

Titlul: RÄƒspuns: QuickSort request
Scris de: Andrei Grigorean din Aprilie 08, 2008, 14:18:01

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

Titlul: RÄƒspuns: QuickSort request
Scris de: Maritanu Codrut Catalin din Aprilie 08, 2008, 17:11:28

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.

Titlul: RÄƒspuns: QuickSort request
Scris de: Herpesius din Aprilie 08, 2008, 17:36:32

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;

}

Titlul: RÄƒspuns: QuickSort request
Scris de: Bogdan-Alexandru Stoica din Aprilie 08, 2008, 21:55:08

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. :-s

Titlul: RÄƒspuns: QuickSort request
Scris de: Lucian Boca din Aprilie 23, 2008, 23:17:50

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 :P

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)

Titlul: RÄƒspuns: QuickSort request
Scris de: Andrei Grigorean din Aprilie 24, 2008, 00:24:23

Puteti citi mai multe despre inline-uri aici (http://en.wikipedia.org/wiki/Inline_function).

Titlul: RÄƒspuns: QuickSort request
Scris de: Simionescu Andrei din August 20, 2008, 14:38:22

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 (http://en.wikipedia.org/wiki/Quicksort#Algorithm)

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);
}

Titlul: RÄƒspuns: QuickSort request
Scris de: Andrei Grigorean din August 20, 2008, 16:13:58

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

Titlul: RÄƒspuns: QuickSort request
Scris de: Simionescu Andrei din August 21, 2008, 23:02:51

am inteles, mersi :thumbup:

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Maritanu Codrut Catalin din Aprilie 08, 2008, 11:33:15