qsort() — це попередньо визначена стандартна функція в бібліотеці C. Ми можемо використовувати цю функцію для сортування масиву в порядку зростання або спадання. Він внутрішньо використовує алгоритм швидкого сортування, звідси й назва qsort. Він може сортувати масив даних будь-якого типу, включаючи рядки та структури. Він добре працює та ефективний у реалізації. Існує функція sort() у C++, подібна до qsort() у C. У таких аспектах, як час роботи, безпека та гнучкість, sort() перевершує qsort().

У цьому посібнику пояснюється функція qsort() із прикладами. У стандарті C не визначено складність функції, але оскільки внутрішньо вона дотримується алгоритму швидкого сортування, її середня часова складність умовно дорівнює O(n*logn). Функція визначена у файлі заголовка stdlib; тому нам потрібно включити його перед використанням.

 #include 

Синтаксис функції:

 qsort(array, number, size, function) 

масив : Масив для сортування.

номер : кількість елементів у масиві, які ми хочемо відсортувати

розмір : Розмір окремого елемента масиву

функція : Настроювана функція порівняння, яку нам потрібно написати у вказаному форматі:

Зазначений формат функції:

 int compare( const void* a, const void* b) { } 

• qsort() викликає функцію compare() для кожних двох елементів у масиві.
• Аргументи a і b є двома пустими покажчиками, які вказують на два елементи для порівняння.
• ми повинні написати тіло compare() так, як воно має повертати:
  1. 0, якщо два елементи рівні
  2. -1 або будь-яке інше від’ємне ціле число, якщо перший елемент менший за другий
  3. 1 або будь-яке інше додатне число, якщо перший елемент більший за другий.
• Ім’я функції порівняння може бути будь-яким, але це ім’я має бути точно вказано як аргумент функції qsort().
• const void* a означає, що a є покажчиком void, значення якого є фіксованим. Перед використанням нам потрібно привести покажчик void до певного типу даних.

Тепер ми розглянемо функції для сортування масивів різних типів даних.

1. Сортування цілих чисел:

 #include #include int compare(const void* num1, const void* num2) // comparing function { int a = *(int*) num1; int b = *(int*) num2; if(a &gt; 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 &gt; 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(&apos;Enter the size of the array to be sorted: &apos;); scanf(&apos;%d&apos;, &amp;n); printf(&apos;
Enter elements into the array: &apos;); 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 -&gt; num1)- (b -&gt; num1); int second = (a -&gt; num2)- (b -&gt; num2); if(first == 0) { return second; } return first; } int main() { data array[5]; int i = 0; printf(&apos;Original array: 
&apos;); printf(&apos;[[&apos;); 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;

Вхідний масив має тип. Отже, перед виконанням будь-яких операцій для виділення необхідної пам’яті ми повинні привести покажчики void до цілочисельних покажчиків. Ми зберегли значення, на які вказують два покажчики, у двох інших цілих змінних, a і b. Потім ми порівняли обидва значення за допомогою операторів порівняння.

підготуватися до тесту mockito

Замість використання ще двох тимчасових змінних ми можемо написати однорядковий код:

 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: &apos;); 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 -&gt; num1)- (b -&gt; num1); int second = (a -&gt; num2)- (b -&gt; num2); if(first == 0) { return second; } return first; } int main() { data array[5]; int i = 0; printf(&apos;Original array: 
&apos;); printf(&apos;[[&apos;); 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;>

Розуміння:

• У нас є масив рядків. Різниця між масивом цілих чисел і масивом рядків полягає в тому, що:
  1. Масив цілих чисел — це набір цілих чисел
  2. Масив рядків — це набір масивів символів/покажчиків на символи.
• Отже, у функції порівняння нам потрібно привести покажчики void до (char**)a, а не (char*)a.
  [[рядок 1], [рядок 2]?]
  Коли ми використовуємо char*, він вказує на масив, а потім, щоб вказати на рядок у масиві, нам потрібен подвійний вказівник.
• Тут ми використали функцію strcmp(). Функція визначена у файлі заголовка string.h. Нам потрібно включити його спочатку.
Функція повертається:
1. 0, якщо обидва рядки однакові
2. 1, якщо значення ASCII символу в рядку більше, ніж відповідний символ у другому рядку
3. -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: 
&apos;); printf(&apos;[[&apos;); 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, тобто кожен елемент у масиві є масивом елементів структури. У наведеній вище програмі структура має два цілі елементи. Завдання полягає в тому, щоб відсортувати масив відносно першого елемента Structure, і якщо будь-які два перші елементи рівні, нам потрібно відсортувати його за другим елементом.

приклад:

[[1, 2], [3, 4], [1, 4]]

Відсортований масив: [[1, 2], [1, 4], [3, 4]]

Ми використовували функцію rand(), щоб генерувати випадкові елементи в масиві. У функції compare() нам потрібно привести два покажчики до структури типу.

Особливістю використання qsort() є спеціальна функція порівняння, яку ми можемо створити так, як хочемо. Ми також можемо відсортувати кілька елементів у масиві й залишити решту без сортування.