qsort() és una funció estàndard predefinida a la biblioteca C. Podem utilitzar aquesta funció per ordenar una matriu en ordre ascendent o descendent. Utilitza internament l'algorisme d'ordenació ràpida, d'aquí el nom qsort. Pot ordenar una matriu de qualsevol tipus de dades, incloses les cadenes i les estructures. Funciona bé i és eficient d'implementar. Hi ha una funció sort() en C++ similar a qsort() en C. En aspectes com el temps d'execució, la seguretat i la flexibilitat, sort() supera qsort().
Aquest tutorial explica la funció qsort() amb exemples. L'estàndard C no va especificar la complexitat de la funció, però com que internament segueix l'algorisme d'ordenació ràpida, la seva complexitat de temps mitjà es considera provisionalment O(n*logn). La funció es defineix al fitxer de capçalera stdlib; per tant, hem d'incloure-lo abans d'utilitzar-lo.
#include
Sintaxi de la funció:
qsort(array, number, size, function)
matriu : La matriu que s'ha d'ordenar.
0,0625 com a fracció
nombre : Nombre d'elements de la matriu que volem ordenar
mida : Mida d'un element individual de la matriu
funció : funció de comparació personalitzada que hem d'escriure en un format especificat:
comanda d'instal·lació npm
Format especificat de la funció:
int compare( const void* a, const void* b) { } - qsort() crida a la funció compare() per cada dos elements de la matriu.
- Els arguments a i b són dos punters buits per assenyalar els dos elements a comparar.
- hem d'escriure el cos de compare() de la manera que hauria de tornar:
- 0 si dos elements són iguals
- -1 o qualsevol altre nombre enter negatiu si el primer element és menor que el segon element
- 1 o qualsevol altre nombre positiu si el primer element és més gran que el segon.
- El nom de la funció de comparació pot ser qualsevol cosa, però el nom s'ha de donar exactament com a argument a la funció qsort().
- const void* a significa que a és un punter de buit el valor del qual és fix. Abans d'utilitzar-lo, hem de escriure un punter buit a algun tipus de dades.
Ara, explorarem les funcions per ordenar matrius de diferents tipus de dades.
1. Ordenar nombres enters:
#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)> Comprensió:
En aquestes dues línies:
int a = *(int*) num1;
comanda de retorn de java
int b = *(int*) num2;
La matriu d'entrada és de tipus . Per tant, hem de teclejar els punters buits en punters enters abans de realitzar qualsevol operació per assignar la memòria necessària. Hem emmagatzemat els valors als quals apunten els dos punters en altres dues variables senceres, a i b. A continuació, vam comparar ambdós valors mitjançant els operadors de comparació.
En lloc d'utilitzar dues variables temporals més, podem escriure un codi d'una línia:
int compare(const void* num1, const void* num2) { return *(int*)a - *(int*)b; } - Si a==b, es retorna 0; si a > b, es retorna un nombre enter positiu; si a
2. Classificació de cadenes
#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;> Comprensió:
- Tenim una matriu de cadenes. La diferència entre una matriu d'enters i una matriu de cadenes és que:
- Una matriu d'enters és una col·lecció de nombres enters
- Una matriu de cadenes és una col·lecció de matrius de caràcters/punters de caràcters.
- Per tant, a la funció de comparació, hem de tipificar els punters buits a (char**)a i no a (char*)a.
[[cadena 1], [cadena 2]?]
Quan fem servir char*, apunta a la matriu, i després, per apuntar a una cadena de la matriu, necessitem un punter doble. - Hem utilitzat la funció strcmp() aquí. La funció es defineix al fitxer de capçalera string.h. Primer l'hem d'incloure.
- 0 si les dues cadenes són iguals
- 1 si el valor ASCII d'un caràcter de la cadena és més gran que el caràcter corresponent de la segona cadena
- -1 si el valor ASCII d'un caràcter de la cadena és menor que el caràcter corresponent de la segona cadena.
3. Ordenar una matriu d'estructura
#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;> Comprensió:
Hem declarat una matriu de tipus Estructura, és a dir, cada element de la matriu és una matriu d'elements d'estructura. En el programa anterior, l'estructura té dos elements enters. La tasca és ordenar la matriu respecte al primer element d'Estructura, i si els dos primers elements són iguals, l'hem d'ordenar utilitzant el segon element.
Exemple:
r en llenguatge c
[[1, 2], [3, 4], [1, 4]]
Matriu ordenada: [[1, 2], [1, 4], [3, 4]]
Hem utilitzat la funció rand() per generar elements aleatoris a la matriu. A la funció compare(), hem de tipificar els dos punters a l'estructura de tipus.
L'especialitat d'utilitzar qsort() és la funció de comparació personalitzada que podem dissenyar de la manera que volem. També podem ordenar alguns elements en una matriu i deixar la resta sense ordenar.