A qsort() egy előre definiált szabványos függvény a C könyvtárban. Ezzel a funkcióval egy tömböt növekvő vagy csökkenő sorrendbe rendezhetünk. Belsőleg a gyors rendezési algoritmust használja, innen a qsort elnevezés. Bármilyen adattípus tömbjét képes rendezni, beleértve a karakterláncokat és struktúrákat is. Jól működik és hatékonyan kivitelezhető. A C++-ban van egy sort() függvény, amely hasonló a qsort()-hoz a C-ben. A futási idő, a biztonság és a rugalmasság szempontjából a sort() felülmúlja a qsort() függvényt.
Ez az oktatóanyag példákkal magyarázza el a qsort() függvényt. A C szabvány nem határozta meg a függvény bonyolultságát, de mivel belsőleg a gyorsrendezési algoritmust követi, az átlagos időbonyolultságát feltételesen O(n*logn)-nak vesszük. A függvény az stdlib fejlécfájlban van definiálva; ezért használat előtt bele kell foglalnunk.
#include
A függvény szintaxisa:
qsort(array, number, size, function)
sor : A rendezendő tömb.
szám : A rendezni kívánt elemek száma a tömbben
méret : A tömb egyedi elemének mérete
funkció : Egyéni összehasonlító függvény, amelyet meghatározott formátumban kell írnunk:
A függvény meghatározott formátuma:
mi az a java verem
int compare( const void* a, const void* b) { } - A qsort() a tömb minden két eleméhez meghívja az összehasonlítás() függvényt.
- Az a és b argumentum két üres mutató, amelyek az összehasonlítandó két elemre mutatnak.
- meg kell írnunk az összehasonlítás() törzsét úgy, ahogyan vissza kell térnie:
- 0, ha két elem egyenlő
- -1 vagy bármely más negatív egész szám, ha az első elem kisebb, mint a második elem
- 1 vagy bármely más pozitív szám, ha az első elem nagyobb, mint a második.
- Az összehasonlító függvény neve bármi lehet, de a nevet pontosan meg kell adni a qsort() függvény argumentumaként.
- const void* a azt jelenti, hogy a egy üres mutató, amelynek értéke rögzített. Használat előtt üres mutatót kell írnunk valamilyen adattípusra.
Most megvizsgáljuk a különböző adattípusú tömbök rendezésének funkcióit.
1. Egész számok rendezése:
#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)> Megértés:
Ebben a két sorban:
int a = *(int*) szám1;
int b = *(int*) szám2;
A bemeneti tömb típusa . Ezért az üres mutatókat egész mutatókra kell gépelnünk, mielőtt bármilyen műveletet végrehajtanánk a szükséges memória lefoglalására. A két mutató által mutatott értékeket két másik egész változóban tároltuk, az a és b. Ezután mindkét értéket összehasonlítottuk az összehasonlító operátorok segítségével.
Ahelyett, hogy további két ideiglenes változót használnánk, írhatunk egy egysoros kódot:
int compare(const void* num1, const void* num2) { return *(int*)a - *(int*)b; } - Ha a==b, akkor 0 kerül vissza; ha a > b, akkor pozitív egész szám kerül visszaadásra; Ha egy
2. A karakterláncok rendezése
#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;> Megértés:
- Van egy sor karakterláncunk. Az egész szám tömb és a karakterlánc tömb közötti különbség a következő:
- Az egész tömb egész számok gyűjteménye
- A string tömb karaktertömbök/karaktermutatók gyűjteménye.
- Ezért az összehasonlító függvényben a void mutatókat (char**)a-ra kell írnunk, nem pedig (char*)a-ra.
[[karakterlánc 1], [karakterlánc 2]?]
Amikor a char*-ot használjuk, az a tömbre mutat, majd a tömbben lévő karakterláncra mutatáshoz dupla mutatóra van szükségünk. - Itt az strcmp() függvényt használtuk. A függvény a string.h fejlécfájlban van definiálva. Először is bele kell foglalnunk.
- 0, ha mindkét karakterlánc azonos
- 1, ha a karakterláncban lévő karakter ASCII értéke nagyobb, mint a második karakterlánc megfelelő karaktere
- -1, ha a karakterláncban lévő karakter ASCII értéke kisebb, mint a második karakterlánc megfelelő karaktere.
3. Szerkezettömb rendezése
#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;> Megértés:
Deklaráltunk egy Structure típusú tömböt, ami azt jelenti, hogy a tömb minden eleme szerkezeti elemek tömbje. A fenti programban a szerkezetnek két egész eleme van. A feladat az, hogy rendezzük a tömböt az első Struktúra elemhez képest, és ha bármely két első elem egyenlő, akkor a második elem segítségével kell rendeznünk.
Példa:
mi az a linux fájlrendszer
[[1, 2], [3, 4], [1, 4]]
Rendezett tömb: [[1, 2], [1, 4], [3, 4]]
A rand() függvény segítségével véletlenszerű elemeket generáltunk a tömbben. Az összehasonlítás() függvényben a két mutatót be kell írnunk a típusszerkezetre.
A qsort() használatának különlegessége az egyéni összehasonlító függvény, amelyet úgy alakíthatunk ki, ahogyan szeretnénk. Néhány elemet rendezhetünk egy tömbben is, a többit pedig rendezetlenül hagyhatjuk.