qsort() to predefiniowana funkcja standardowa w bibliotece C. Możemy użyć tej funkcji do sortowania tablicy w kolejności rosnącej lub malejącej. Wewnętrznie używa algorytmu szybkiego sortowania, stąd nazwa qsort. Może sortować tablicę dowolnego typu danych, w tym ciągi i struktury. Działa dobrze i jest skuteczny w realizacji. W C++ istnieje funkcja sort() podobna do qsort() w C. Pod względem czasu działania, bezpieczeństwa i elastyczności sort() przewyższa qsort().
W tym samouczku wyjaśniono funkcję qsort() na przykładach. Standard C nie określił złożoności funkcji, ale ponieważ wewnętrznie jest zgodny z algorytmem szybkiego sortowania, wstępnie przyjmuje się, że jej średnia złożoność czasowa wynosi O(n*logn). Funkcja jest zdefiniowana w pliku nagłówkowym stdlib; dlatego musimy go uwzględnić przed użyciem.
#include
Składnia funkcji:
qsort(array, number, size, function)
szyk : Tablica, która ma zostać posortowana.
numer : Liczba elementów tablicy, które chcemy posortować
rozmiar : Rozmiar pojedynczego elementu tablicy
funkcjonować : Niestandardowa funkcja porównania, którą musimy zapisać w określonym formacie:
Określony format funkcji:
int compare( const void* a, const void* b) { } - qsort() wywołuje funkcję Compare() dla każdych dwóch elementów tablicy.
- Argumenty a i b to dwa puste wskaźniki wskazujące na dwa elementy, które mają zostać porównane.
- musimy napisać treść funkcji Compare() w taki sposób, aby zwracała:
- 0, jeśli dwa elementy są równe
- -1 lub dowolna inna ujemna liczba całkowita, jeśli pierwszy element jest mniejszy niż drugi element
- 1 lub inna liczba dodatnia, jeśli pierwszy element jest większy od drugiego.
- Nazwa funkcji porównującej może być dowolna, ale musi być dokładnie podana jako argument funkcji qsort().
- const void* a oznacza, że a jest wskaźnikiem void, którego wartość jest stała. Przed użyciem musimy rzutować wskaźnik void na jakiś typ danych.
Teraz przyjrzymy się funkcjom sortowania tablic różnych typów danych.
1. Sortowanie liczb całkowitych:
#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)> Zrozumienie:
W tych dwóch wierszach:
int a = *(int*) liczba1;
int b = *(int*) liczba2;
Tablica wejściowa jest typu . Dlatego przed wykonaniem jakichkolwiek operacji w celu przydzielenia wymaganej pamięci musimy wpisać wskaźniki void na wskaźniki całkowite. Wartości, na które wskazują dwa wskaźniki, zapisaliśmy w dwóch innych zmiennych całkowitych, a i b. Następnie porównaliśmy obie wartości za pomocą operatorów porównania.
Zamiast używać dwóch kolejnych zmiennych tymczasowych, możemy napisać jednowierszowy kod:
int compare(const void* num1, const void* num2) { return *(int*)a - *(int*)b; } - Jeśli a==b, zwracane jest 0; jeśli a > b, zwracana jest dodatnia liczba całkowita; Jeśli
2. Sortowanie ciągów
#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;> Zrozumienie:
- Mamy tablicę ciągów. Różnica między tablicą liczb całkowitych a tablicą łańcuchów polega na tym, że:
- Tablica liczb całkowitych jest zbiorem liczb całkowitych
- Tablica ciągów to zbiór tablic znakowych/wskaźników znakowych.
- Dlatego w funkcji porównania musimy wpisać wskaźniki void na (char**)a, a nie (char*)a.
[[ciąg 1], [ciąg 2]?]
Kiedy używamy char*, wskazuje on tablicę, a następnie, aby wskazać ciąg w tablicy, potrzebujemy podwójnego wskaźnika. - Użyliśmy tutaj funkcji strcmp(). Funkcja jest zdefiniowana w pliku nagłówkowym string.h. Najpierw musimy to uwzględnić.
- 0, jeśli oba ciągi są takie same
- 1, jeśli wartość ASCII znaku w ciągu jest większa niż odpowiadający mu znak w drugim ciągu
- -1, jeśli wartość ASCII znaku w ciągu jest mniejsza niż odpowiadający mu znak w drugim ciągu.
3. Sortowanie tablicy o strukturze
#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;> Zrozumienie:
Zadeklarowaliśmy tablicę typu Structure, co oznacza, że każdy element tablicy jest tablicą elementów struktury. W powyższym programie struktura posiada dwa elementy całkowite. Zadanie polega na posortowaniu tablicy względem pierwszego elementu Structure i jeśli dowolne dwa pierwsze elementy są równe, musimy ją posortować za pomocą drugiego elementu.
Przykład:
[[1, 2], [3, 4], [1, 4]]
Posortowana tablica: [[1, 2], [1, 4], [3, 4]]
Użyliśmy funkcji Rand() do wygenerowania losowych elementów w tablicy. W funkcji Compare() musimy rzutować na maszynę dwa wskaźniki, aby wpisać strukturę.
Specjalnością funkcji qsort() jest niestandardowa funkcja porównywania, którą możemy zaprojektować tak, jak chcemy. Możemy także posortować kilka elementów tablicy, a resztę pozostawić nieposortowaną.