qsort() este o funcție standard predefinită în biblioteca C. Putem folosi această funcție pentru a sorta o matrice în ordine crescătoare sau descrescătoare. Utilizează intern algoritmul de sortare rapidă, de unde și numele qsort. Poate sorta o matrice de orice tip de date, inclusiv șiruri și structuri. Funcționează bine și este eficient de implementat. Există o funcție sort() în C++ similară cu qsort() în C. În aspecte precum timpul de rulare, siguranță și flexibilitate, sort() depășește qsort().
Acest tutorial explică funcția qsort() cu exemple. Standardul C nu a specificat complexitatea funcției, dar deoarece în interior urmează algoritmul de sortare rapidă, complexitatea sa medie a timpului este considerată provizoriu ca fiind O(n*logn). Funcția este definită în fișierul antet stdlib; prin urmare, trebuie să-l includem înainte de a-l folosi.
#include
Sintaxa funcției:
qsort(array, number, size, function)
matrice : Matricea de sortat.
număr : Numărul de elemente din matrice pe care dorim să le sortăm
mărimea : Dimensiunea unui element individual al matricei
funcţie : Funcția de comparare personalizată pe care trebuie să o scriem într-un format specificat:
Formatul specificat al funcției:
int compare( const void* a, const void* b) { } - qsort() apelează funcția compare() pentru fiecare două elemente din matrice.
- Argumentele a și b sunt doi indicatori de gol pentru a indica cele două elemente de comparat.
- trebuie să scriem corpul lui compare() în felul în care ar trebui să returneze:
- 0 dacă două elemente sunt egale
- -1 sau orice alt număr întreg negativ dacă primul element este mai mic decât al doilea element
- 1 sau orice alt număr pozitiv dacă primul element este mai mare decât al doilea.
- Numele funcției de comparare poate fi orice, dar numele trebuie să fie dat exact ca argument pentru funcția qsort().
- const void* a înseamnă că a este un pointer void a cărui valoare este fixă. Înainte de utilizare, trebuie să introducem un pointer void către un anumit tip de date.
Acum, vom explora funcțiile pentru sortarea matricelor de diferite tipuri de date.
1. Sortarea numerelor întregi:
#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)> Înţelegere:
În aceste două rânduri:
int a = *(int*) num1;
int b = *(int*) num2;
Matricea de intrare este de tip . Prin urmare, trebuie să tipărim pointerii void în pointeri întregi înainte de a efectua orice operații pentru a aloca memoria necesară. Am stocat valorile către care indică cei doi pointeri în alte două variabile întregi, a și b. Apoi, am comparat ambele valori folosind operatorii de comparare.
În loc să folosim încă două variabile temporare, putem scrie un cod de o linie:
int compare(const void* num1, const void* num2) { return *(int*)a - *(int*)b; } - Dacă a==b, se returnează 0; dacă a > b, se returnează un număr întreg pozitiv; în cazul în care o
2. Sortarea șirurilor
#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;> Înţelegere:
- Avem o serie de șiruri. Diferența dintre o matrice de întregi și o matrice de șiruri este aceea că:
- Un tablou întreg este o colecție de numere întregi
- O matrice de șiruri este o colecție de matrice de caractere/indicatori de caractere.
- Prin urmare, în funcția de comparare, trebuie să tipărim pointerii void către (char**)a și nu (char*)a.
[[șirul 1], [șirul 2]?]
Când folosim char*, indică către matrice și apoi, pentru a indica un șir din matrice, avem nevoie de un indicator dublu. - Am folosit funcția strcmp() aici. Funcția este definită în fișierul antet string.h. Trebuie să-l includem mai întâi.
- 0 dacă ambele șiruri sunt aceleași
- 1 dacă valoarea ASCII a unui caracter din șir este mai mare decât caracterul corespunzător din al doilea șir
- -1 dacă valoarea ASCII a unui caracter din șir este mai mică decât caracterul corespunzător din al doilea șir.
3. Sortarea unui tablou de structură
#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;> Înţelegere:
Am declarat o matrice de tip Structure, adică fiecare element din matrice este o matrice de elemente de structură. În programul de mai sus, structura are două elemente întregi. Sarcina este de a sorta matricea în raport cu primul element Structure, iar dacă oricare două prime elemente sunt egale, trebuie să o sortăm folosind al doilea element.
Exemplu:
[[1, 2], [3, 4], [1, 4]]
Matrice sortată: [[1, 2], [1, 4], [3, 4]]
Am folosit funcția rand() pentru a genera elemente aleatorii în matrice. În funcția compare(), trebuie să tipărim cei doi pointeri către structura de tip.
Specialitatea utilizării qsort() este funcția de comparare personalizată pe care o putem proiecta așa cum ne dorim. De asemenea, putem sorta câteva elemente dintr-o matrice și să lăsăm restul nesortat.