qsort () ir iepriekš definēta standarta funkcija C bibliotēkā. Mēs varam izmantot šo funkciju, lai kārtotu masīvu augošā vai dilstošā secībā. Tas iekšēji izmanto ātrās kārtošanas algoritmu, līdz ar to nosaukumu qsort. Tas var kārtot jebkura veida datu masīvu, tostarp virknes un struktūras. Tas darbojas labi un ir efektīvi īstenojams. C++ valodā ir funkcija sort(), kas ir līdzīga qsort() valodā C. Tādos aspektos kā darbības laiks, drošība un elastība, sort() pārspēj qsort().
Šajā apmācībā ir izskaidrota funkcija qsort() ar piemēriem. C standarts nenorādīja funkcijas sarežģītību, bet, tā kā iekšēji tas seko ātrās kārtošanas algoritmam, tā vidējā laika sarežģītība provizoriski tiek uzskatīta par O(n*logn). Funkcija ir definēta stdlib galvenes failā; tāpēc mums tas ir jāiekļauj pirms lietošanas.
binārā meklēšanas koks
#include
Funkcijas sintakse:
qsort(array, number, size, function)
masīvs : kārtojamais masīvs.
numuru : elementu skaits masīvā, ko vēlamies kārtot
Izmērs : atsevišķa masīva elementa lielums
funkciju : pielāgota salīdzināšanas funkcija, kas mums jāieraksta noteiktā formātā:
npm instalēšanas komanda
Norādītais funkcijas formāts:
int compare( const void* a, const void* b) { } - qsort() izsauc salīdzināšanas () funkciju katram diviem masīva elementiem.
- Argumenti a un b ir divi tukši rādītāji, kas norāda uz diviem salīdzināmajiem elementiem.
- mums ir jāuzraksta salīdzinājuma () pamatteksts tādā veidā, kā tam jāatgriežas:
- 0, ja divi elementi ir vienādi
- -1 vai jebkurš cits negatīvs vesels skaitlis, ja pirmais elements ir mazāks par otro elementu
- 1 vai jebkurš cits pozitīvs skaitlis, ja pirmais elements ir lielāks par otro.
- Salīdzināšanas funkcijas nosaukums var būt jebkas, taču nosaukums ir precīzi jānorāda kā arguments funkcijai qsort().
- const void* nozīmē a ir tukšuma rādītājs, kura vērtība ir fiksēta. Pirms lietošanas mums ir jāievada tukšs rādītājs uz kādu datu tipu.
Tagad mēs izpētīsim dažādu datu tipu masīvu šķirošanas funkcijas.
1. Veselo skaitļu kārtošana:
#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)> Saprašana:
Šajās divās rindās:
int a = *(int*) num1;
apakšvirknes virkne java
int b = *(int*) num2;
Ievades masīvs ir tipa . Tāpēc pirms jebkādu darbību veikšanas, lai piešķirtu nepieciešamo atmiņu, tukšās norādes ir jāievada veselu skaitļu rādītājos. Mēs saglabājām vērtības, uz kurām norāda divi rādītāji, divos citos veselos skaitļu mainīgajos a un b. Pēc tam mēs salīdzinājām abas vērtības, izmantojot salīdzināšanas operatorus.
Tā vietā, lai izmantotu vēl divus pagaidu mainīgos, mēs varam uzrakstīt vienas rindas kodu:
int compare(const void* num1, const void* num2) { return *(int*)a - *(int*)b; } - Ja a==b, tiek atgriezts 0; ja a > b, tiek atgriezts pozitīvs vesels skaitlis; ja
2. Virkņu šķirošana
#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;> Saprašana:
- Mums ir virkņu masīvs. Atšķirība starp veselu skaitļu masīvu un virkņu masīvu ir šāda:
- Veselu skaitļu masīvs ir veselu skaitļu kolekcija
- Virkņu masīvs ir rakstzīmju masīvu/rakstzīmju norādes kolekcija.
- Tādējādi salīdzināšanas funkcijā mums ir jāievada tukšās norādes uz (char**)a, nevis (char*)a.
[[virkne 1], [virkne 2]?]
Kad mēs izmantojam char*, tas norāda uz masīvu, un tad, lai norādītu uz virkni masīvā, mums ir nepieciešams dubultrādītājs. - Šeit mēs izmantojām funkciju strcmp (). Funkcija ir definēta galvenes failā string.h. Vispirms mums tas ir jāiekļauj.
- 0, ja abas virknes ir vienādas
- 1, ja rakstzīmes ASCII vērtība virknē ir lielāka par atbilstošo rakstzīmi otrajā virknē
- -1, ja rakstzīmes ASCII vērtība virknē ir mazāka par atbilstošo rakstzīmi otrajā virknē.
3. Struktūras masīva kārtošana
#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;> Saprašana:
Mēs deklarējām struktūras tipa masīvu, kas nozīmē, ka katrs masīva elements ir struktūras elementu masīvs. Iepriekš minētajā programmā struktūrai ir divi veseli skaitļu elementi. Uzdevums ir sakārtot masīvu attiecībā pret pirmo struktūras elementu, un, ja kādi divi pirmie elementi ir vienādi, mums tas jākārto, izmantojot otro elementu.
Piemērs:
prime bez koda java
[[1, 2], [3, 4], [1, 4]]
Sakārtots masīvs: [[1, 2], [1, 4], [3, 4]]
Mēs izmantojām funkciju rand (), lai masīvā ģenerētu nejaušus elementus. Funkcijā salīdzināt () mums ir jāievada divi norādes, lai ierakstītu struktūru.
Qsort() izmantošanas īpatnība ir pielāgota salīdzināšanas funkcija, kuru mēs varam izveidot tā, kā mēs vēlamies. Mēs varam arī sakārtot dažus elementus masīvā un atstāt pārējos nešķirotus.