Tento návod ilustruje triedenie polí pomocou qsort() funkciu v C a tiež vám pomôže pochopiť ju pomocou príkladov kódov C.
qsort() v C
C štandardná knižnica nám uľahčuje qsort() funkcia, ktorá sa jednoducho používa na triedenie polí. Ide o mimoriadne optimalizovanú a rýchlu funkciu, ktorá dokáže pracovať s akýmkoľvek dátovým typom poľa.
Hlavička-súbor pomocou qsort() v C
The qsort() metóda je definovaná vo vnútri stdlib.h hlavičkový súbor, ktorý musí byť definovaný pred implementáciou qsort() v programe C.
#include
Vyhlásenie qsort()
Vyhlásenie o qsort() funkcia je nasledovná:
neplatné qsort ( neplatné * základňu , počet_prvkov , veľkosť_prvku , porovnávacia_funkcia )
Parametre funkcie qsort().
Parametre qsort() funkcie sú:
základňa: Ukazovateľ na prvý prvok poľa, ktoré sa má zoradiť.
počet_prvkov: Počet prvkov v poli, ktoré sa majú zoradiť.
veľkosť_prvku: Veľkosť každého prvku v poli v bajtoch.
porovnávacia_funkcia: Ukazovateľ na porovnávaciu funkciu, ktorá definuje poradie prvkov.
Čo je porovnávacia funkcia v qsort()
Porovnávacia funkcia má dva parametre, oba typu const void*, ktoré poukazujú na porovnávané prvky. Funkcia by mala vrátiť celé číslo menšie, rovné alebo väčšie ako 0, v závislosti od toho, či by mal byť prvý prvok zoradený pred, na rovnakej pozícii alebo za druhým prvkom.
Ako funguje qsort v C
The qsort() funkcia funguje nasledovným spôsobom:
Poznámka: Tu uvažujeme o a int arr[] = {5, 2, 8, 3, 1, 9};
1: Na začiatku sa zavolá funkcia qsort s nasledujúcimi parametrami:
qsort ( arr , 6 , veľkosť ( int ) , porovnávacia_funkcia ) ;kde arr je ukazovateľ na pole, 6 je počet prvkov v poli, sizeof(int) je veľkosť každého prvku v poli a Compare_function je funkcia, ktorá určuje poradie, v ktorom sú prvky zoradené.
2: Funkcia qsort vyberie prvok pivot. Povedzme, že vyberá 3 ako pivot.
3: Funkcia qsort rozdelí pole na dve podpolia: {2, 1} a {5, 8, 9}. Prvé podpole obsahuje prvky, ktoré sú menšie alebo rovnaké ako pivot, a druhé podpole obsahuje prvky, ktoré sú väčšie ako pivot.
4: Funkcia qsort sa rekurzívne volá na každom z podpolí.
5: Funkcia qsort vyberá pivoty pre každé z podpolí. Povedzme, že vyberie 1 a 8 ako pivoty.
6: Funkcia qsort rozdeľuje každé podpole na dve ďalšie podpole a rekurzívne sa volá na každé z týchto podpolí.
7: Funkcia qsort kombinuje zoradené podpolia späť do jedného zoradeného poľa: {1, 2} a {5, 8, 9} sa stanú {1, 2, 5, 8, 9}.
8: Vráti sa celé zoradené pole.
Implementácia qsort v programovaní C
Nasledujúci kód ukazuje implementáciu qsort funkcie v programovaní C.
#include#include
int porovnať ( konšt neplatné * a1 , konšt neplatné * b1 )
{
vrátiť ( * ( int * ) a1 - * ( int * ) b1 ) ;
}
int Hlavná ( )
{
int i = 0 , na jeden = 6 ;
int pole [ ] = { 5 , 2 , 8 , 3 , 1 , 9 } ;
qsort ( pole , na jeden , veľkosť ( int ) , porovnať ) ;
printf ( 'Zoradené prvky poľa pomocou qsort() sú: ' ) ;
pre ( i = 0 ; i < na jeden ; i ++ ) {
printf ( '%d' , pole [ i ] ) ; }
vrátiť 0 ;
}
Vo vyššie uvedenom kóde sa najprv vytvorí porovnávacia funkcia s dvoma parametrami a1 a b1 . Potom vykonávanie začne od main(). V podstate inicializujeme dve celočíselné premenné ako i=0 a num=6. Potom deklarujeme pole so šiestimi prvkami ako {5, 2, 8, 3, 1, 9} . Po tomto qsort() majú tri parametre typu poľa, parameter num udáva celkový počet prvkov poľa, sizeof(int) označuje celkovú veľkosť poľa a porovnať sa používa na porovnanie prvkov poľa jeden po druhom. Potom vytlačte zoradené pole pomocou printf() funkcia v C.
Výkon
Záver
qsort je výkonná funkcia v programovaní C na triedenie polí akéhokoľvek typu. Používa algoritmus rýchleho triedenia na triedenie prvkov vo vzostupnom alebo zostupnom poradí na základe porovnávacej funkcie. Vyššie uvedená príručka vám ukazuje jednoduchý spôsob, ako implementovať qsort v programovaní C pomocou krok za krokom qsort algoritmu.