qsort () yra iš anksto nustatyta standartinė funkcija C bibliotekoje. Šią funkciją galime naudoti norėdami rūšiuoti masyvą didėjančia arba mažėjančia tvarka. Jis viduje naudoja greito rūšiavimo algoritmą, todėl pavadinimas qsort. Jis gali rūšiuoti bet kokio tipo duomenų masyvą, įskaitant eilutes ir struktūras. Jis veikia gerai ir yra efektyviai įgyvendinamas. C++ kalboje yra funkcija sort(), panaši į qsort() C kalboje. Kalbant apie veikimo laiką, saugą ir lankstumą, sort() pranoksta qsort().
Ši pamoka paaiškina funkciją qsort() su pavyzdžiais. C standartas nenurodė funkcijos sudėtingumo, tačiau, kadangi viduje ji vadovaujasi greito rūšiavimo algoritmu, jos vidutinis laiko sudėtingumas preliminariai laikomas O(n*logn). Funkcija apibrėžta stdlib antraštės faile; todėl prieš naudodami turime jį įtraukti.
#include
Funkcijos sintaksė:
qsort(array, number, size, function)
masyvas : masyvas, kurį reikia rūšiuoti.
java kitaip, jei
numerį : masyvo elementų, kuriuos norime rūšiuoti, skaičius
dydis : atskiro masyvo elemento dydis
funkcija : Pasirinktinė palyginimo funkcija, kurią turime parašyti nurodytu formatu:
Nurodytas funkcijos formatas:
int compare( const void* a, const void* b) { }
- qsort() iškviečia palyginimo () funkciją kiekvienam dviems masyvo elementams.
- Argumentai a ir b yra du tušti rodyklės, rodančios du lyginamuosius elementus.
- turime parašyti palyginimo () kūną taip, kaip jis turėtų grįžti:
- 0, jei du elementai yra lygūs
- -1 arba bet kuris kitas neigiamas sveikasis skaičius, jei pirmasis elementas yra mažesnis už antrąjį elementą
- 1 arba bet kuris kitas teigiamas skaičius, jei pirmasis elementas yra didesnis už antrąjį.
- Lyginimo funkcijos pavadinimas gali būti bet koks, tačiau pavadinimas turi būti tiksliai pateiktas kaip funkcijos qsort() argumentas.
- const void* a reiškia, kad a yra tuščioji rodyklė, kurios reikšmė yra fiksuota. Prieš naudodami, turime įvesti tuščią rodyklę į tam tikrą duomenų tipą.
Dabar išnagrinėsime skirtingų duomenų tipų masyvų rūšiavimo funkcijas.
1. Sveikųjų skaičių rūšiavimas:
#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)>
Supratimas:
Šiose dviejose eilutėse:
java pertraukai
int a = *(int*) skaičius1;
int b = *(int*) skaičius2;
Įvesties masyvas yra tipo . Taigi, prieš atlikdami bet kokias operacijas, kad paskirstytume reikiamą atmintį, tuščiąsias rodykles turime įvesti į sveikųjų skaičių rodykles. Vertes, į kurias nukreipia dvi rodyklės, išsaugojome dviejuose kituose sveikųjų skaičių kintamuosiuose a ir b. Tada palyginome abi reikšmes naudodami palyginimo operatorius.
Užuot naudoję dar du laikinuosius kintamuosius, galime parašyti vienos eilutės kodą:
int compare(const void* num1, const void* num2) { return *(int*)a - *(int*)b; }
- Jei a==b, grąžinamas 0; jei a > b, grąžinamas teigiamas sveikasis skaičius; jeigu
2. Eilučių rūšiavimas
#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;>
Supratimas:
- Mes turime daugybę stygų. Skirtumas tarp sveikųjų skaičių masyvo ir eilučių masyvo yra toks:
- Sveikųjų skaičių masyvas yra sveikųjų skaičių rinkinys
- Eilučių masyvas yra simbolių masyvų / simbolių rodyklių rinkinys.
- Taigi, palyginimo funkcijoje turime įvesti tuščiąsias nuorodas į (char**)a, o ne į (char*)a.
[[1 eilutė], [2 eilutė]?]
Kai naudojame char*, jis nurodo masyvą, o tada, norėdami nurodyti eilutę masyve, mums reikia dvigubo žymeklio. - Čia panaudojome strcmp() funkciją. Funkcija apibrėžta string.h antraštės faile. Pirmiausia turime jį įtraukti.
- 0, jei abi eilutės yra vienodos
- 1, jei eilutės simbolio ASCII reikšmė yra didesnė už atitinkamą antrosios eilutės simbolį
- -1, jei eilutės simbolio ASCII reikšmė yra mažesnė už atitinkamą antrosios eilutės simbolį.
3. Struktūros masyvo rūšiavimas
#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;>
Supratimas:
Mes paskelbėme Structure tipo masyvą, o tai reiškia, kad kiekvienas masyvo elementas yra struktūros elementų masyvas. Aukščiau pateiktoje programoje struktūra turi du sveikųjų skaičių elementus. Užduotis yra surūšiuoti masyvą pirmojo struktūros elemento atžvilgiu ir, jei bet kurie du pirmieji elementai yra lygūs, turime jį surūšiuoti naudodami antrąjį elementą.
Pavyzdys:
[[1, 2], [3, 4], [1, 4]]
Surūšiuotas masyvas: [[1, 2], [1, 4], [3, 4]]
Atsitiktiniams masyvo elementams generuoti naudojome funkciją rand(). Funkcijoje „palyginti ()“ turime įvesti dvi rodykles į tipo struktūrą.
CSV failo skaitymas java
qsort() naudojimo ypatumas yra tinkinta palyginimo funkcija, kurią galime sukurti taip, kaip norime. Taip pat galime surūšiuoti kelis elementus masyve, o likusius palikti nerūšiuotus.
5;>