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