qsort() е предварително дефинирана стандартна функция в C библиотеката. Можем да използваме тази функция, за да сортираме масив във възходящ или низходящ ред. Той вътрешно използва алгоритъма за бързо сортиране, оттук и името qsort. Може да сортира масив от всякакъв тип данни, включително низове и структури. Работи добре и е ефективен за изпълнение. Има функция sort() в C++, подобна на qsort() в C. В аспекти като време на работа, безопасност и гъвкавост sort() превъзхожда qsort().
Този урок обяснява функцията qsort() с примери. Стандартът C не уточнява сложността на функцията, но тъй като вътрешно тя следва алгоритъма за бързо сортиране, нейната средна времева сложност условно се приема за O(n*logn). Функцията е дефинирана в заглавния файл stdlib; следователно трябва да го включим, преди да го използваме.
#include
Синтаксис на функцията:
qsort(array, number, size, function)
масив : Масивът за сортиране.
номер : Броят на елементите в масива, които искаме да сортираме
размер : Размер на отделен елемент от масива
java програми
функция : Персонализирана функция за сравнение, която трябва да напишем в определен формат:
Посочен формат на функцията:
int compare( const void* a, const void* b) { } - qsort() извиква функцията compare() за всеки два елемента в масива.
- Аргументите a и b са два празни указателя, които сочат към двата елемента, които трябва да бъдат сравнени.
- трябва да напишем тялото на compare() по начина, по който трябва да върне:
- 0, ако два елемента са равни
- -1 или всяко друго отрицателно цяло число, ако първият елемент е по-малък от втория елемент
- 1 или всяко друго положително число, ако първият елемент е по-голям от втория.
- Името на сравняващата функция може да бъде произволно, но името трябва да бъде дадено точно като аргумент на функцията qsort().
- const void* a означава, че a е празен указател, чиято стойност е фиксирана. Преди да използваме, трябва да преобразуваме празен указател към някакъв тип данни.
Сега ще разгледаме функциите за сортиране на масиви от различни типове данни.
1. Сортиране на цели числа:
#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)> разбиране:
В тези два реда:
int a = *(int*) num1;
int b = *(int*) num2;
Входният масив е от тип. Следователно трябва да преобразуваме празните указатели в целочислени указатели, преди да извършим каквито и да било операции за разпределяне на необходимата памет. Съхранихме стойностите, към които сочат двата указателя, в две други целочислени променливи, a и b. След това сравнихме двете стойности с помощта на операторите за сравнение.
Вместо да използваме още две временни променливи, можем да напишем код от един ред:
int compare(const void* num1, const void* num2) { return *(int*)a - *(int*)b; } - Ако a==b, връща се 0; ако a > b, връща се положително цяло число; ако
2. Сортиране на низове
#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;> разбиране:
- Имаме масив от низове. Разликата между целочислен масив и низов масив е, че:
- Масивът с цели числа е колекция от цели числа
- Низовият масив е колекция от масиви от символи/знакови указатели.
- Следователно във функцията за сравнение трябва да преобразуваме празните указатели към (char**)a, а не към (char*)a.
[[низ 1], [низ 2]?]
Когато използваме char*, той сочи към масива и след това, за да сочим към низ в масива, се нуждаем от двоен указател. - Тук използвахме функцията strcmp(). Функцията е дефинирана в заглавния файл string.h. Първо трябва да го включим.
- 0, ако и двата низа са еднакви
- 1, ако ASCII стойността на знак в низа е по-голяма от съответния знак във втория низ
- -1, ако ASCII стойността на знак в низа е по-малка от съответния знак във втория низ.
3. Сортиране на масив от структура
#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;> разбиране:
Декларирахме масив от тип Structure, което означава, че всеки елемент в масива е масив от структурни елементи. В горната програма структурата има два целочислени елемента. Задачата е да сортираме масива по отношение на първия елемент на структурата и ако всеки два първи елемента са равни, трябва да го сортираме с помощта на втория елемент.
Пример:
[[1, 2], [3, 4], [1, 4]]
Сортиран масив: [[1, 2], [1, 4], [3, 4]]
Използвахме функцията rand(), за да генерираме произволни елементи в масива. Във функцията compare() трябва да преобразуваме двата указателя към структурата на типа.
Специалността на използването на qsort() е персонализираната функция за сравнение, която можем да проектираме по начина, по който искаме. Можем също да сортираме няколко елемента в масив и да оставим останалите несортирани.