[ANSI C] Qsort z stdlib.h

Witam,
mam takie pytanie, qsort z biblioteki <stdlib.h> wg jakiego punktu podzialu sortuje ?

-pivot losowy;
-pivot srodkowy;

? a moze wg innego ?

Pozdro !

TUTAJ

hmm nie znalazlem tam odpowiedzi na swoje pytanie :(

Nierekurencyjna wersja + mediana z trzech + inne optymalizacje.

..co oznacza, że jest to zależne od implementacji.

qsort z glibc:
http://sources.redhat.com/cgi-bin/cvsweb.cgi/libc/stdlib/qsort.c?rev=1.12&content-type=text/x-cvsweb-markup&cvsroot=glibc

(...)
Order size using quicksort. This implementation incorporates
four optimizations discussed in Sedgewick:

1. Non-recursive, using an explicit stack of pointer that store the
   next array partition to sort. To save time, this maximum amount
   of space required to store an array of SIZE_MAX is allocated on the
   stack. Assuming a 32-bit (64 bit) integer for size_t, this needs
   only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
   Pretty cheap, actually.

2. Chose the pivot element using a median-of-three decision tree.
   This reduces the probability of selecting a bad pivot value and
   eliminates certain extraneous comparisons.

3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
   insertion sort to order the MAX_THRESH items within each partition.
   This is a big win, since insertion sort is faster for small, mostly
   sorted array segments.

4. The larger of the two sub-partitions is always pushed onto the
   stack first, with the algorithm then concentrating on the
   smaller partition. This guarantees no more than log (total_elems)
   stack size is needed (actually O(1) in this case)! */
   (...)

Trza szukać :-P

jesli mediana z trzech i iteracja to nie dobrze :/

rozumie, ze w dev-cpp (chyba korzysta z gcc) jest taka sama implementacja jak w glibc ?

W BCB 5 jest rekurencyjna wersja, w bcb 6 pewnie też.
Ciekawe o ile szybciej działa wersja nierekurencyjna, a może wolniej? :|

Gather napisał(a)

jesli mediana z trzech i iteracja to nie dobrze :/

rozumie, ze w dev-cpp (chyba korzysta z gcc) jest taka sama implementacja jak w glibc ?

Nie. MinGW-GCC korzysta z MSVCRT (i zapewne masz Dev-C++ z MinGW...).
Natomiast Cygwin - który też może być pod Dev-C++ - nie wiem...