qsort() on ennalta määritetty vakiofunktio C-kirjastossa. Voimme käyttää tätä toimintoa lajitellaksesi taulukon nousevaan tai laskevaan järjestykseen. Se käyttää sisäisesti pikalajittelualgoritmia, mistä johtuu nimi qsort. Se voi lajitella minkä tahansa tietotyypin joukon, mukaan lukien merkkijonot ja rakenteet. Se toimii hyvin ja on tehokas toteuttaa. C++:ssa on funktio sort(), joka on samanlainen kuin qsort() C:ssä. Ajoajan, turvallisuuden ja joustavuuden kaltaisissa näkökohdissa sort() päihittää qsort():n.
Tämä opetusohjelma selittää funktion qsort() esimerkein. C-standardi ei määritellyt funktion monimutkaisuutta, mutta koska se noudattaa sisäisesti pikalajittelualgoritmia, sen keskimääräiseksi aikakompleksisuudeksi otetaan alustavasti O(n*logn). Funktio määritellään stdlib-otsikkotiedostossa; siksi meidän on sisällytettävä se ennen sen käyttöä.
#include
Funktion syntaksi:
qsort(array, number, size, function)
joukko : Lajiteltava taulukko.
int merkkijonossa
määrä : Niiden taulukon elementtien lukumäärä, jotka haluamme lajitella
koko : taulukon yksittäisen elementin koko
toiminto : Mukautettu vertailufunktio, joka meidän on kirjoitettava määritetyssä muodossa:
suorita komentosarjan kuori
Toiminnon määritetty muoto:
int compare( const void* a, const void* b) { } - qsort() kutsuu vertailu()-funktiota jokaiselle kahdelle taulukon elementille.
- Argumentit a ja b ovat kaksi tyhjää osoitinta, jotka osoittavat kahteen verrattavaan elementtiin.
- meidän on kirjoitettava vertailu() -kappale tavalla, jolla sen pitäisi palauttaa:
- 0, jos kaksi alkiota ovat yhtä suuret
- -1 tai mikä tahansa muu negatiivinen kokonaisluku, jos ensimmäinen alkio on pienempi kuin toinen alkio
- 1 tai mikä tahansa muu positiivinen luku, jos ensimmäinen alkio on suurempi kuin toinen.
- Vertailufunktion nimi voi olla mikä tahansa, mutta nimi on annettava tarkasti argumenttina qsort()-funktiolle.
- const void* a tarkoittaa, että a on tyhjä osoitin, jonka arvo on kiinteä. Ennen käyttöä meidän on kirjoitettava tyhjä osoitin johonkin tietotyyppiin.
Nyt tutkimme eri tietotyyppien taulukoiden lajittelutoimintoja.
1. Kokonaislukujen lajittelu:
#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)> Ymmärtäminen:
Näillä kahdella rivillä:
int a = *(int*) numero1;
ohjelmistojen testaus ja tyypit
int b = *(int*) numero2;
Syöttötaulukko on tyyppiä . Tästä syystä meidän on kirjoitettava tyhjät osoittimet kokonaislukuosoittimiin ennen kuin suoritamme toimenpiteitä vaaditun muistin varaamiseksi. Tallensimme arvot, joihin kaksi osoitinta osoittavat kahteen muuhun kokonaislukumuuttujaan, a ja b. Sitten vertailimme molempia arvoja käyttämällä vertailuoperaattoreita.
Kahden väliaikaisen muuttujan käyttämisen sijaan voimme kirjoittaa yksirivisen koodin:
int compare(const void* num1, const void* num2) { return *(int*)a - *(int*)b; } - Jos a==b, palautetaan 0; jos a > b, palautetaan positiivinen kokonaisluku; jos
2. Merkkijonojen lajittelu
#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;> Ymmärtäminen:
- Meillä on joukko merkkijonoja. Ero kokonaislukutaulukon ja merkkijonotaulukon välillä on seuraava:
- Kokonaislukutaulukko on kokoelma kokonaislukuja
- Merkkijonotaulukko on kokoelma merkkitaulukoita/merkkiosoittimia.
- Siksi vertailufunktiossa meidän on kirjoitettava tyhjät osoittimet kohtaan (char**)a eikä (char*)a.
[[merkkijono 1], [merkkijono 2]?]
Kun käytämme merkkiä char*, se osoittaa taulukkoon, ja sitten taulukon merkkijonoon osoittamiseksi tarvitsemme kaksoisosoittimen. - Käytimme tässä strcmp()-funktiota. Funktio määritellään string.h-otsikkotiedostossa. Meidän on sisällytettävä se ensin.
- 0, jos molemmat merkkijonot ovat samat
- 1, jos merkkijonon ASCII-arvo on suurempi kuin vastaava merkki toisessa merkkijonossa
- -1, jos merkkijonon ASCII-arvo on pienempi kuin vastaava merkki toisessa merkkijonossa.
3. Rakennetaulukon lajittelu
#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;> Ymmärtäminen:
Ilmoitimme Structure-tyypin taulukon, mikä tarkoittaa, että jokainen taulukon elementti on joukko rakenneelementtejä. Yllä olevassa ohjelmassa rakenteessa on kaksi kokonaislukuelementtiä. Tehtävänä on lajitella taulukko ensimmäisen rakenne-elementin suhteen, ja jos kaksi ensimmäistä elementtiä ovat yhtä suuret, meidän on lajiteltava se käyttämällä toista elementtiä.
Esimerkki:
nykyinen päivämäärä javassa
[[1, 2], [3, 4], [1, 4]]
Lajiteltu taulukko: [[1, 2], [1, 4], [3, 4]]
Käytimme rand()-funktiota satunnaisten elementtien luomiseen taulukossa. Vertaa()-funktiossa meidän täytyy kirjoittaa kaksi osoitinta tyyppirakenteeseen.
Qsort()-käytön erikoisuus on mukautettu vertailutoiminto, jonka voimme suunnitella haluamallamme tavalla. Voimme myös lajitella muutamia elementtejä taulukossa ja jättää loput lajittelematta.