Jakiego algorytmu sortowania używa qsort?

Question

Nie mogę znaleźć żadnych informacji dotyczących algorytmu sortowania, którego używa funkcja C qsort.

Czy to quicksort? Nie jest to wspomniane w człowieku.

Answer 1

Implementacja qsort nie została określona: implementacja może wykorzystywać dowolny algorytm sortowania. Co ciekawe, sortowanie nie musi być stabilne i nie ma wymogu złożoności.

Cały określenie qsort (C11 §7.22.5.2) jest następująca:

The qsort funkcja

Synoptyka

#include <stdlib.h> 
void qsort(void *base, size_t nmemb, size_t size, 
    int (*compar)(const void *, const void *)); 

Opis

Funkcja qsort sortuje tablicę obiektów nmemb, której początkowy element to wskazany przez base. Rozmiar każdego obiektu jest określony przez size.

Zawartość tablicy posortowana jest w kolejności rosnącej zgodnie z funkcją porównania wskazywaną przez compar, która jest wywoływana dwoma argumentami, które wskazują porównywane obiekty. Funkcja zwraca liczbę całkowitą mniejszą od, równą lub większą od zera, jeśli pierwszy argument jest uważany za mniejszy, równy lub większy od drugiego.

Jeśli dwa elementy są porównywane jako równe, ich kolejność w wynikowej posortowanej tablicy jest nieokreślona.

Zwraca

qsort Funkcja zwraca żadnej wartości.

Answer 2

Teoretycznie qsort określa się tylko do punktu zwróconych wartości i wartości wywoławcze qsort i bsort. Here są standardowymi referencjami ISO.

W praktyce zwykle korzysta z quicksort.

Answer 3

W uzupełnieniu cytat Jamesa McNellis za standardu Warto zauważyć, że GNU’s libc documentation mówi, że

Funkcja qsort wywodzi swoją nazwę z faktu, że pierwotnie była realizowana za pomocą „szybkiego sortowania” algorytmu.

i że zdecydował się użyć alternative algorithm, najwyraźniej sortowania scalonego.