qsort() je předdefinovaná standardní funkce v knihovně C. Tuto funkci můžeme použít k seřazení pole ve vzestupném nebo sestupném pořadí. Interně používá algoritmus rychlého řazení, odtud název qsort. Dokáže seřadit pole libovolného datového typu, včetně řetězců a struktur. Funguje dobře a je efektivní při implementaci. V C++ existuje funkce sort() podobná qsort() v C. V aspektech, jako je doba běhu, bezpečnost a flexibilita, sort() překonává qsort().
Tento tutoriál vysvětluje funkci qsort() na příkladech. Standard C nespecifikoval složitost funkce, ale protože se vnitřně řídí algoritmem rychlého třídění, její průměrná časová složitost se předběžně považuje za O(n*logn). Funkce je definována v hlavičkovém souboru stdlib; proto jej musíme před použitím zahrnout.
#include
Syntaxe funkce:
qsort(array, number, size, function)
pole : Pole, které se má seřadit.
číslo : Počet prvků v poli, které chceme seřadit
velikost : Velikost jednotlivého prvku pole
funkce : Vlastní porovnávací funkci, kterou potřebujeme napsat v určeném formátu:
mylive kriket
Zadaný formát funkce:
int compare( const void* a, const void* b) { } - qsort() volá funkci Compare() pro každé dva prvky v poli.
- Argumenty aab jsou dva prázdné ukazatele, které ukazují na dva prvky, které mají být porovnávány.
- musíme napsat tělo Compare() tak, jak by mělo vracet:
- 0, pokud jsou dva prvky stejné
- -1 nebo jakékoli jiné záporné celé číslo, pokud je první prvek menší než druhý prvek
- 1 nebo jakékoli jiné kladné číslo, pokud je první prvek větší než druhý.
- Název porovnávací funkce může být jakýkoli, ale název musí být přesně zadán jako argument funkce qsort().
- const void* a znamená a je ukazatel void, jehož hodnota je pevná. Před použitím musíme přetypovat void ukazatel na nějaký datový typ.
Nyní prozkoumáme funkce pro řazení polí různých datových typů.
1. Řazení 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)> Porozumění:
V těchto dvou řádcích:
jak otevřít skryté aplikace na android
int a = *(int*) num1;
int b = *(int*) num2;
Vstupní pole je typu . Proto musíme ukazatele prázdnoty přetypovat na celočíselné ukazatele před provedením jakékoli operace k alokaci požadované paměti. Hodnoty, na které dva ukazatele ukazují, jsme uložili do dvou dalších celočíselných proměnných a a b. Poté jsme obě hodnoty porovnali pomocí porovnávacích operátorů.
Místo použití dvou dalších dočasných proměnných můžeme napsat jednořádkový kód:
int compare(const void* num1, const void* num2) { return *(int*)a - *(int*)b; } - Pokud a==b, vrátí se 0; pokud a > b, je vráceno kladné celé číslo; Pokud
2. Třídicí řetězce
#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;> Porozumění:
- Máme pole řetězců. Rozdíl mezi celočíselným polem a polem řetězců je tento:
- Celočíselné pole je sbírka celých čísel
- Pole řetězců je sbírka polí znaků/ukazatelů na znaky.
- Proto ve funkci porovnání musíme přetypovat ukazatele void na (char**)a a ne (char*)a.
[[řetězec 1], [řetězec 2]?]
Když použijeme char*, ukazuje to na pole a pak, abychom ukázali na řetězec v poli, potřebujeme dvojitý ukazatel. - Použili jsme zde funkci strcmp(). Funkce je definována v hlavičkovém souboru string.h. Nejprve to musíme zahrnout.
- 0, pokud jsou oba řetězce stejné
- 1, pokud je hodnota ASCII znaku v řetězci větší než odpovídající znak v druhém řetězci
- -1, pokud je hodnota ASCII znaku v řetězci menší než odpovídající znak v druhém řetězci.
3. Třídění pole struktur
#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;> Porozumění:
Deklarovali jsme pole typu Structure, což znamená, že každý prvek v poli je polem prvků struktury. Ve výše uvedeném programu má struktura dva celočíselné prvky. Úkolem je seřadit pole s ohledem na první prvek Structure, a pokud jsou jakékoli dva první prvky stejné, musíme je seřadit pomocí druhého prvku.
Příklad:
[[1, 2], [3, 4], [1, 4]]
Seřazené pole: [[1, 2], [1, 4], [3, 4]]
Ke generování náhodných prvků v poli jsme použili funkci rand(). Ve funkci Compare() musíme přetypovat dva ukazatele na strukturu typu.
latex velikosti textu
Specialitou použití qsort() je vlastní porovnávací funkce, kterou můžeme navrhnout tak, jak chceme. Můžeme také seřadit několik prvků v poli a zbytek nechat neseřazený.