Algoritmus QuickSort

v průměru O(N log N), vyjde rychleji než Heap Sort
v nejhorším případě O(N^2)

V Pascalu (z přednášky) ;)

V céčku, podle toho, co nám bylo předvedeno v Pascalu o přednášce

Deprecated: Assigning the return value of new by reference is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/highlight/java.php on line 5

#include 
#include 
#include 

/*
 * Programovani 06/12/1: Algoritmus QuickSort, tady je v cecku. Napsal jsem ho jako razeni ukazatelu s porovnavaci fci,
 * radim ukazatele na cisla a pak retezce (taky ukazatele)
 */

/* nejake poznamky z hodiny: */

/*
 * slozitost: prum: O(n log n), nejhorsi O(n^2),
 * Problem je pivot, hodil by se median hodnot (stredni hodnota), ale to trva moc dlouho.
 */

/*
 * Odstraneni rekurse:
 * - jiny algoritmus
 * - nahradit iteraci
 * - vlastni zasobnik
 *   - vkladani parametru do "seznamu ukolu" a pak je zpracovavam, dokud nejake jsou
 * - omezit
 */

int     cmpUnsignedPtr(unsigned*, unsigned*);
void    printUnsignedPtrPtr(unsigned** a, unsigned count);
void    printStrPtr(const char** a, unsigned count);

typedef int (*myqsortcmp)(const void*, const void*);
void    myqsort(
                 void** base, void** end,                   /* zacatek a konec pole beztypovych ukazatelu */
                 myqsortcmp cmp                             /* porovnavaci funkce pro beztypove ukazatele */
                 );


void     myqsort(
                 void** base, void** end,
                 int (* cmp)(const void *, const void *)
                 ){
    void*   pivot   = *((base) + (end-base) / 2);   /* ptr arithmetics doesn't permit simple sum/2 */
    void**  x       = base;
    void**  y       = end;

    do{
        /*
         * podminka cyklu ma ostrou nerovnost, abychom se vzdycky zarazili "o pivot",
         * a aby se osetrila delsi posloupnost pivotu
         */
        for(;   cmp(*x, pivot) < 0; x++ )
            ;
            
        for(;   cmp(*y, pivot) > 0; y-- )
            ;
        
        if( x <= y ){
            void* swap  = *x;
            *x          = *y;
            *y          = swap;
            x++;
            y--;
        }
    } while( x <= y ); /* until x > y,  dokud se prvky neprekrizi, abychom porovnali vse */

    if( base < y )
        myqsort(base, y, cmp);
    if( x < end )
        myqsort(x, end, cmp);
}


int     cmpUnsignedPtr(unsigned* a, unsigned* b){
    if( *a < *b )
        return -1;
    if( *a > *b )
        return 1;
    return 0;
    /* NOTE: we could simply subtract and return result, but this is more readable */
}


void    printUnsignedPtrPtr( unsigned** a, unsigned count){
    unsigned i;
    for(i=0; i" %u", *a[i]);
    printf("\n");
}

void    printStrPtr(const char** a, unsigned count){
    unsigned i;
    for(i=0; i" %s", a[i]);
    printf("\n");
}


int main (int argc, const char * argv[]) {
    unsigned    numbers[]           = {3, 2, 4, 8, 1};
    unsigned*   ptrsToNumbers[]     = {
        &numbers[0],
        &numbers[1],
        &numbers[2],
        &numbers[3],
        &numbers[4]
    };

    const char* names[]         = {
        "Ales",
        "Zdenek",
        "Alena",
        "Karel",
        "Zdislav"
    };

    myqsort(
            (void**)ptrsToNumbers, (void**)ptrsToNumbers + sizeof(ptrsToNumbers)/sizeof(*ptrsToNumbers) - 1,
            cmpUnsignedPtr
            );
    printUnsignedPtrPtr(ptrsToNumbers, sizeof(ptrsToNumbers)/sizeof(*ptrsToNumbers));
    
    myqsort(
            (void**)names, (void**)names + sizeof(names)/sizeof(*names) - 1,
            (myqsortcmp)strcmp
            );
    printStrPtr(names, sizeof(names)/sizeof(*names));
                
    return 0;
}

Matfiz: QuickSort

Algoritmus QuickSort

V Pascalu (z přednášky) ;)

V céčku, podle toho, co nám bylo předvedeno v Pascalu o přednášce