qsort - qsort
qsort je standardní knihovní funkcí jazyka C, která implementuje polymorfní třídicí algoritmus pro pole libovolných objektů podle porovnávací funkce poskytované uživatelem. Je pojmenován podle algoritmu „quicker sort“ ( varianta quicksortu díky RS Scowen), který byl původně použit k jeho implementaci do knihovny Unix C, ačkoli standard C k implementaci quicksortu nevyžaduje.
Implementace funkce qsort dosahuje polymorfismu , schopnosti třídit různé druhy dat, tím, že ukazatel funkce přejde na třícestnou srovnávací funkci, stejně jako parametr, který určuje velikost jejích jednotlivých vstupních objektů. Standard C vyžaduje funkci porovnání k implementaci celkového pořadí položek ve vstupním poli.
Dějiny
Funkci qsort implementoval Lee McMahon v roce 1972. Ve verzi 3 Unix byla zavedena jako knihovní funkce, ale tehdy šlo o podprogram assembleru .
Verze AC se zhruba rozhraním standardní verze C byla zavedena ve verzi 6 Unix . Byl přepsán v roce 1983 pro BSD . Funkce byla standardizována v ANSI C (1989).
V roce 1991 zaměstnanci společnosti Bell Labs zjistili, že verze qsortu McMahon a BSD by u některých jednoduchých vstupů spotřebovala kvadratický čas . Tak Jon Bentley a Douglas McIlroy navrhovaný nový rychlejší a robustnější implementaci.
Příklad
Následující část kódu C ukazuje, jak třídit seznam celých čísel pomocí qsort.
#include <stdlib.h>
/* Comparison function. Receives two generic (void) pointers to the items under comparison. */
int compare_ints(const void *p, const void *q) {
int x = *(const int *)p;
int y = *(const int *)q;
/* Avoid return x - y, which can cause undefined behaviour
because of signed integer overflow. */
if (x < y)
return -1; // Return -1 if you want ascending, 1 if you want descending order.
else if (x > y)
return 1; // Return 1 if you want ascending, -1 if you want descending order.
return 0;
// All the logic is often alternatively written:
return (x > y) - (x < y);
}
/* Sort an array of n integers, pointed to by a. */
void sort_ints(int *a, size_t n) {
qsort(a, n, sizeof(*a), compare_ints);
}
Rozšíření
Protože porovnávací funkce originálu qsortpřijímá pouze dva ukazatele, předávání dalších parametrů (např. Vytváření srovnávací funkce, která porovnává rozdíl mezi dvěma hodnotami s jinou hodnotou) musí být provedeno pomocí globálních proměnných . Problém byl v systémech podobných Unixům BSD a GNU vyřešen zaváděcí qsort_rfunkcí, která umožňuje předat do srovnávací funkce další parametr. Tyto dvě verze qsort_rmají různé pořadí argumentů. Příloha K C11 definuje v qsort_spodstatě identické s GNU qsort_r. MacOS a FreeBSD libcs také obsahují qsort_bvariantu, která používá bloky , analogické k uzávěrům , jako alternativní řešení stejného problému.
Reference
 |
Tento článek související se softwarovým inženýrstvím je útržek . Wikipedii můžete pomoci jejím rozšířením . |