Qsort - Qsort

qsort je C standardní knihovna funkce, která implementuje a polymorfní třídicí algoritmus pro pole libovolných objektů podle porovnávací funkce poskytnuté uživatelem. Je pojmenován podle algoritmu „rychlejšího řazení“ (a quicksort varianta kvůli R. S. Scowenovi), která byla původně použita k jejímu provedení v Unix Knihovna C, i když standard C nevyžaduje implementaci quicksortu.^[1]

Implementace funkce qsort dosahuje polymorfismus, schopnost třídit různé druhy dat, a ukazatel funkce do a třícestné srovnání funkce, stejně jako parametr, který určuje velikost jeho jednotlivých vstupních objektů. The C standard vyžaduje funkci porovnání k implementaci a celková objednávka na položkách ve vstupním poli.^[2]

Dějiny

Funkce qsort byla implementována Lee McMahon v roce 1972.^[3][1] Bylo to na místě v Verze 3 Unix jako funkce knihovny, ale pak byl assembler podprogram.^[3]

Verze C, která měla zhruba rozhraní standardní verze C, byla na místě Verze 6 Unix.^[4]To bylo přepsáno v roce 1983 pro BSD.^[1]Funkce byla standardizována v ANSI C. (1989).

V roce 1991 zaměstnanci Bell Labs zjistili, že verze qsort, které McMahon a BSD spotřebují, spotřebují kvadratický čas pro některé jednoduché vstupy. Tím pádem Jon Bentley a Douglas McIlroy vytvořila novou rychlejší a robustnější implementaci.^[1]

Příklad

Následující část kódu C ukazuje, jak seřadit seznam celých čísel pomocí qsort.

#zahrnout <stdlib.h>/ * Srovnávací funkce. Přijímá dva obecné (neplatné) ukazatele na porovnávané položky. * /int porovnat_body(konst prázdnota *p, konst prázdnota *q) {    int X = *(konst int *)p;    int y = *(konst int *)q;    / * Vyhněte se návratu x - y, což může způsobit nedefinované chování       kvůli přetečení celého čísla se znaménkem. * /    -li (X < y)        vrátit se -1;  // Vrací -1, pokud chcete vzestupně, 1, pokud chcete sestupně.     jiný -li (X > y)        vrátit se 1;   // Vraťte 1, pokud chcete vzestupně, -1, pokud chcete sestupně.     vrátit se 0;    // Celá logika je často alternativně napsána:    vrátit se (X > y) - (X < y);}/ * Seřadit pole n celých čísel, na které ukazuje a. * /prázdnota sort_ints(int *A, size_t n) {    qsort(A, n, velikost(*A), porovnat_body);}

Reference

Tento softwarové inženýrství související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.