qsort() je preddefinovaná štandardná funkcia v knižnici C. Túto funkciu môžeme použiť na zoradenie poľa vo vzostupnom alebo zostupnom poradí. Interne používa algoritmus rýchleho triedenia, odtiaľ názov qsort. Dokáže zoradiť pole ľubovoľného typu údajov vrátane reťazcov a štruktúr. Funguje to dobre a je efektívna implementácia. V C++ existuje funkcia sort() podobná qsort() v C. V aspektoch, ako je doba chodu, bezpečnosť a flexibilita, sort() prekonáva qsort().
Tento tutoriál vysvetľuje funkciu qsort() s príkladmi. Štandard C nešpecifikoval zložitosť funkcie, ale keďže interne nasleduje algoritmus rýchleho triedenia, jej priemerná časová zložitosť sa predbežne považuje za O(n*logn). Funkcia je definovaná v hlavičkovom súbore stdlib; preto ho musíme zahrnúť pred použitím.
#include
Syntax funkcie:
qsort(array, number, size, function)
pole : Pole, ktoré sa má zoradiť.
číslo : Počet prvkov v poli, ktoré chceme zoradiť
veľkosť : Veľkosť jednotlivého prvku poľa
funkciu : Vlastná porovnávacia funkcia, ktorú musíme napísať v určenom formáte:
Zadaný formát funkcie:
int compare( const void* a, const void* b) { } - qsort() volá funkciu Compare() pre každé dva prvky v poli.
- Argumenty a a b sú dva neplatné ukazovatele, ktoré poukazujú na dva prvky, ktoré sa majú porovnávať.
- telo funkcie Compare() musíme napísať tak, aby sa vrátilo:
- 0, ak sú dva prvky rovnaké
- -1 alebo akékoľvek iné záporné celé číslo, ak je prvý prvok menší ako druhý prvok
- 1 alebo akékoľvek iné kladné číslo, ak je prvý prvok väčší ako druhý.
- Názov porovnávacej funkcie môže byť akýkoľvek, ale názov musí byť presne daný ako argument funkcie qsort().
- const void* a znamená a je ukazovateľ void, ktorého hodnota je pevná. Pred použitím musíme pretypovať ukazovateľ neplatnosti na nejaký typ údajov.
Teraz preskúmame funkcie na triedenie polí rôznych typov údajov.
1. Triedenie celých čísel:
#include #include int compare(const void* num1, const void* num2) // comparing function { int a = *(int*) num1; int b = *(int*) num2; if(a > b) { return 1; } else if(a <b) { return -1; } 0; int main() arr[50], n, i; printf('enter the size of array to be sorted: '); scanf('%d', &n); printf('
enter elements into array: for(i="0;" i < n; i++) &arr[i]); qsort(arr, sizeof(int), compare); printf('
the sorted printf('
['); if(i="=" n-1) prevent a comma(,) after last element printf('%d', arr[i]); break; printf('%d, ', printf(']'); pre> <p> <strong>Output:</strong> </p> <pre> Enter the size of the array to be sorted: 5 Enter elements into the array: 98 34 89 0 2 The sorted array: [0, 2, 34, 89, 98] </pre> <h3>Understanding:</h3> <p>In these two lines:</p> <p> <strong>int a = *(int*) num1;</strong> </p> <p> <strong>int b = *(int*) num2;</strong> </p> <p>The input array is of type . Hence, we must typecast the void pointers into integer pointers before performing any operations to allocate the required memory. We stored the values the two pointers are pointing at in two other integer variables, a and b. Then, we compared both values using the comparison operators.</p> <p>Instead of using two more temporary variables, we can write a one-line code:</p> <pre> int compare(const void* num1, const void* num2) { return *(int*)a - *(int*)b; } </pre> <ul> <li>If a==b, 0 is returned; if a > b, a positive integer is returned; if a <b, a negative integer is returned.< li> </b,></li></ul> <h3>2. Sorting strings</h3> <pre> #include #include #include int compare(const void* num1, const void* num2) { //char **a = (char**)num1; //char **b = (char**)num2; //return strcmp(*a, *b); return strcmp(*(char**)num1, *(char**)num2); } int main() { int n, i; char* arr[50]; printf('Enter the size of the array to be sorted: '); scanf('%d', &n); printf('
Enter elements into the array: '); for(i = 0; i <n; i++) { arr[i]="malloc(100*" sizeof(char)); scanf('%s', arr[i]); } qsort(arr, n, sizeof(char*), compare); printf('
the sorted array: '); printf('
['); for(i="0;" i < n; if(i="=" n-1) printf('%s', break; printf('%s, ', printf(']'); pre> <p> <strong>Output:</strong> </p> <pre> Enter the size of the array to be sorted: 5 Enter elements into the array: hi hello how are you The sorted array: [are, hello, hi, how, you] </pre> <h3>Understanding:</h3> <ul> <li>We have an array of strings. The difference between an integer array and a string array is that: <ol class="points"> <li>An integer array is a collection of integers</li> <li>A string array is a collection of character arrays/character pointers.</li> </ol></li> <li>Hence, in the compare function, we need to typecast the void pointers to (char**)a and not (char*)a. <br> <strong>[[string 1], [string 2]?]</strong> <br> When we use char*, it points to the array, and then, to point to a string in the array, we need a double pointer.</li> <li>We used the strcmp() function here. The function is defined in the string.h header file. We need to include it first.</li> <tr><td>The function returns</td> : <ol class="points"> <li>0 if both strings are the same</li> <li>1 if the ASCII value of a character in the string is greater than the corresponding character in the second string</li> <li>-1 if the ASCII value of a character in the string is less than the corresponding character in the second string.</li> </ol> </tr></ul> <h3>3. Sorting an Array of Structure</h3> <pre> #include #include struct Structure { int num1; int num2; }s; typedef struct Structure data; int compare(const void* p, const void* q) { data *a = (data *)p; data *b = (data *)q; int first = (a -> num1)- (b -> num1); int second = (a -> num2)- (b -> num2); if(first == 0) { return second; } return first; } int main() { data array[5]; int i = 0; printf('Original array:
'); printf('[['); for(i = 0; i <5; i++) { array[i].num1="rand()%10;" array[i].num2="rand()%10;" if(i="=" 4) printf('%d, %d]]', array[i].num1, array[i].num2); break; } %d], [', qsort(array, 5, sizeof(s), compare); printf('
sorted array:
'); printf('[['); for(i="0;" i < 5; pre> <p> <strong>Output:</strong> </p> <pre> Original array: [[1, 7], [4, 0], [9, 4], [8, 8], [2, 4]] Sorted array: [[1, 7], [2, 4], [4, 0], [8, 8], [9, 4]] </pre> <h3>Understanding:</h3> <p>We declared an array of type Structure, meaning every element in the array is an array of structure elements. In the above program, the structure has two integer elements. The task is to sort the array with respect to the first Structure element, and if any two first elements are equal, we need to sort it using the second element.</p> <p> <strong>Example:</strong> </p> <p>[[1, 2], [3, 4], [1, 4]]</p> <p>Sorted array: [[1, 2], [1, 4], [3, 4]]</p> <p>We used the rand() function to generate random elements in the array. In the compare() function, we need to typecast the two pointers to type structure.</p> <img src="//techcodeview.com/img/c-tutorial/30/qsort-c.webp" alt="qsort() in C"> <p>The specialty of using qsort() is the custom compare function that we can design the way we want. We can also sort a few elements in an array and leave the rest unsorted.</p> <hr></5;></pre></n;></pre></b)> Porozumenie:
V týchto dvoch riadkoch:
int a = *(int*) cislo1;
int b = *(int*) cislo2;
Vstupné pole je typu . Preto musíme pred vykonaním akýchkoľvek operácií na pridelenie požadovanej pamäte pretypovať ukazovatele voidov na celočíselné ukazovatele. Hodnoty, na ktoré ukazujú dva ukazovatele, sme uložili do dvoch ďalších celočíselných premenných a a b. Potom sme obe hodnoty porovnali pomocou porovnávacích operátorov.
Namiesto použitia dvoch ďalších dočasných premenných môžeme napísať jednoriadkový kód:
int compare(const void* num1, const void* num2) { return *(int*)a - *(int*)b; } - Ak a==b, vráti sa 0; ak a > b, vráti sa kladné celé číslo; Ak
2. Triediace reťazce
#include #include #include int compare(const void* num1, const void* num2) { //char **a = (char**)num1; //char **b = (char**)num2; //return strcmp(*a, *b); return strcmp(*(char**)num1, *(char**)num2); } int main() { int n, i; char* arr[50]; printf('Enter the size of the array to be sorted: '); scanf('%d', &n); printf('
Enter elements into the array: '); for(i = 0; i <n; i++) { arr[i]="malloc(100*" sizeof(char)); scanf(\'%s\', arr[i]); } qsort(arr, n, sizeof(char*), compare); printf(\'
the sorted array: \'); printf(\'
[\'); for(i="0;" i < n; if(i="=" n-1) printf(\'%s\', break; printf(\'%s, \', printf(\']\'); pre> <p> <strong>Output:</strong> </p> <pre> Enter the size of the array to be sorted: 5 Enter elements into the array: hi hello how are you The sorted array: [are, hello, hi, how, you] </pre> <h3>Understanding:</h3> <ul> <li>We have an array of strings. The difference between an integer array and a string array is that: <ol class="points"> <li>An integer array is a collection of integers</li> <li>A string array is a collection of character arrays/character pointers.</li> </ol></li> <li>Hence, in the compare function, we need to typecast the void pointers to (char**)a and not (char*)a. <br> <strong>[[string 1], [string 2]?]</strong> <br> When we use char*, it points to the array, and then, to point to a string in the array, we need a double pointer.</li> <li>We used the strcmp() function here. The function is defined in the string.h header file. We need to include it first.</li> <tr><td>The function returns</td> : <ol class="points"> <li>0 if both strings are the same</li> <li>1 if the ASCII value of a character in the string is greater than the corresponding character in the second string</li> <li>-1 if the ASCII value of a character in the string is less than the corresponding character in the second string.</li> </ol> </tr></ul> <h3>3. Sorting an Array of Structure</h3> <pre> #include #include struct Structure { int num1; int num2; }s; typedef struct Structure data; int compare(const void* p, const void* q) { data *a = (data *)p; data *b = (data *)q; int first = (a -> num1)- (b -> num1); int second = (a -> num2)- (b -> num2); if(first == 0) { return second; } return first; } int main() { data array[5]; int i = 0; printf('Original array:
'); printf('[['); for(i = 0; i <5; i++) { array[i].num1="rand()%10;" array[i].num2="rand()%10;" if(i="=" 4) printf(\'%d, %d]]\', array[i].num1, array[i].num2); break; } %d], [\', qsort(array, 5, sizeof(s), compare); printf(\'
sorted array:
\'); printf(\'[[\'); for(i="0;" i < 5; pre> <p> <strong>Output:</strong> </p> <pre> Original array: [[1, 7], [4, 0], [9, 4], [8, 8], [2, 4]] Sorted array: [[1, 7], [2, 4], [4, 0], [8, 8], [9, 4]] </pre> <h3>Understanding:</h3> <p>We declared an array of type Structure, meaning every element in the array is an array of structure elements. In the above program, the structure has two integer elements. The task is to sort the array with respect to the first Structure element, and if any two first elements are equal, we need to sort it using the second element.</p> <p> <strong>Example:</strong> </p> <p>[[1, 2], [3, 4], [1, 4]]</p> <p>Sorted array: [[1, 2], [1, 4], [3, 4]]</p> <p>We used the rand() function to generate random elements in the array. In the compare() function, we need to typecast the two pointers to type structure.</p> <img src="//techcodeview.com/img/c-tutorial/30/qsort-c.webp" alt="qsort() in C"> <p>The specialty of using qsort() is the custom compare function that we can design the way we want. We can also sort a few elements in an array and leave the rest unsorted.</p> <hr></5;></pre></n;> Porozumenie:
- Máme pole reťazcov. Rozdiel medzi celočíselným poľom a reťazcovým poľom je tento:
- Celočíselné pole je kolekcia celých čísel
- Pole reťazcov je zbierka polí znakov/ukazovateľov na znaky.
- Preto v porovnávacej funkcii musíme pretypovať ukazovatele neplatnosti na (char**)a a nie (char*)a.
[[reťazec 1], [reťazec 2]?]
Keď použijeme znak char*, ukazuje na pole a potom, aby sme ukázali na reťazec v poli, potrebujeme dvojitý ukazovateľ. - Tu sme použili funkciu strcmp(). Funkcia je definovaná v hlavičkovom súbore string.h. Najprv to musíme zahrnúť.
- 0, ak sú oba reťazce rovnaké
- 1, ak je hodnota ASCII znaku v reťazci väčšia ako zodpovedajúci znak v druhom reťazci
- -1, ak je hodnota ASCII znaku v reťazci menšia ako zodpovedajúci znak v druhom reťazci.
3. Triedenie poľa štruktúr
#include #include struct Structure { int num1; int num2; }s; typedef struct Structure data; int compare(const void* p, const void* q) { data *a = (data *)p; data *b = (data *)q; int first = (a -> num1)- (b -> num1); int second = (a -> num2)- (b -> num2); if(first == 0) { return second; } return first; } int main() { data array[5]; int i = 0; printf('Original array:
'); printf('[['); for(i = 0; i <5; i++) { array[i].num1="rand()%10;" array[i].num2="rand()%10;" if(i="=" 4) printf(\'%d, %d]]\', array[i].num1, array[i].num2); break; } %d], [\', qsort(array, 5, sizeof(s), compare); printf(\'
sorted array:
\'); printf(\'[[\'); for(i="0;" i < 5; pre> <p> <strong>Output:</strong> </p> <pre> Original array: [[1, 7], [4, 0], [9, 4], [8, 8], [2, 4]] Sorted array: [[1, 7], [2, 4], [4, 0], [8, 8], [9, 4]] </pre> <h3>Understanding:</h3> <p>We declared an array of type Structure, meaning every element in the array is an array of structure elements. In the above program, the structure has two integer elements. The task is to sort the array with respect to the first Structure element, and if any two first elements are equal, we need to sort it using the second element.</p> <p> <strong>Example:</strong> </p> <p>[[1, 2], [3, 4], [1, 4]]</p> <p>Sorted array: [[1, 2], [1, 4], [3, 4]]</p> <p>We used the rand() function to generate random elements in the array. In the compare() function, we need to typecast the two pointers to type structure.</p> <img src="//techcodeview.com/img/c-tutorial/30/qsort-c.webp" alt="qsort() in C"> <p>The specialty of using qsort() is the custom compare function that we can design the way we want. We can also sort a few elements in an array and leave the rest unsorted.</p> <hr></5;> Porozumenie:
Deklarovali sme pole typu Structure, čo znamená, že každý prvok v poli je pole prvkov štruktúry. Vo vyššie uvedenom programe má štruktúra dva celočíselné prvky. Úlohou je zoradiť pole vzhľadom na prvý prvok Structure, a ak sú akékoľvek dva prvé prvky rovnaké, musíme ho zoradiť pomocou druhého prvku.
Príklad:
[[1, 2], [3, 4], [1, 4]]
Zoradené pole: [[1, 2], [1, 4], [3, 4]]
Na generovanie náhodných prvkov v poli sme použili funkciu rand(). Vo funkcii Compare() musíme pretypovať dva ukazovatele na štruktúru typu.
Špecialitou použitia qsort() je vlastná porovnávacia funkcia, ktorú môžeme navrhnúť tak, ako chceme. Môžeme tiež zoradiť niekoľko prvkov v poli a zvyšok nechať neroztriedený.