qsort() ist eine vordefinierte Standardfunktion in der C-Bibliothek. Mit dieser Funktion können wir ein Array in aufsteigender oder absteigender Reihenfolge sortieren. Es verwendet intern den Schnellsortierungsalgorithmus, daher der Name qsort. Es kann ein Array jedes Datentyps sortieren, einschließlich Zeichenfolgen und Strukturen. Es funktioniert gut und ist effizient umzusetzen. Es gibt eine Funktion sort() in C++, die qsort() in C ähnelt. In Aspekten wie Laufzeit, Sicherheit und Flexibilität übertrifft sort() qsort().
Dieses Tutorial erklärt die Funktion qsort() anhand von Beispielen. Der C-Standard hat die Komplexität der Funktion nicht spezifiziert, aber da sie intern dem Schnellsortierungsalgorithmus folgt, wird ihre durchschnittliche Zeitkomplexität vorläufig mit O(n*logn) angenommen. Die Funktion ist in der stdlib-Headerdatei definiert; Daher müssen wir es einschließen, bevor wir es verwenden.
#include
Syntax der Funktion:
qsort(array, number, size, function)
Array : Das zu sortierende Array.
Nummer : Anzahl der Elemente im Array, die wir sortieren möchten
Java-Array
Größe : Größe eines einzelnen Elements des Arrays
Funktion : Benutzerdefinierte Vergleichsfunktion, die wir in einem bestimmten Format schreiben müssen:
Angegebenes Format der Funktion:
int compare( const void* a, const void* b) { } - qsort() ruft die Funktion Compare() für jeweils zwei Elemente im Array auf.
- Die Argumente a und b sind zwei leere Zeiger, die auf die beiden zu vergleichenden Elemente zeigen.
- Wir müssen den Hauptteil von Compare() so schreiben, wie er zurückkommen soll:
- 0, wenn zwei Elemente gleich sind
- -1 oder eine andere negative Ganzzahl, wenn das erste Element kleiner als das zweite Element ist
- 1 oder eine andere positive Zahl, wenn das erste Element größer als das zweite ist.
- Der Name der Vergleichsfunktion kann beliebig sein, der Name muss jedoch genau als Argument für die Funktion qsort() angegeben werden.
- const void* a bedeutet, dass a ein leerer Zeiger ist, dessen Wert festgelegt ist. Vor der Verwendung müssen wir einen void-Zeiger auf einen Datentyp umwandeln.
Jetzt werden wir die Funktionen zum Sortieren von Arrays verschiedener Datentypen untersuchen.
1. Ganzzahlen sortieren:
#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)> Verständnis:
In diesen beiden Zeilen:
int a = *(int*) num1;
int b = *(int*) num2;
Das Eingabearray ist vom Typ . Daher müssen wir die leeren Zeiger in ganzzahlige Zeiger umwandeln, bevor wir irgendwelche Operationen zur Zuweisung des erforderlichen Speichers durchführen. Wir haben die Werte, auf die die beiden Zeiger zeigen, in zwei anderen ganzzahligen Variablen gespeichert, a und b. Anschließend haben wir beide Werte mit den Vergleichsoperatoren verglichen.
Anstatt zwei weitere temporäre Variablen zu verwenden, können wir einen einzeiligen Code schreiben:
int compare(const void* num1, const void* num2) { return *(int*)a - *(int*)b; } - Wenn a==b, wird 0 zurückgegeben; wenn a > b, wird eine positive ganze Zahl zurückgegeben; wenn ein
2. Strings sortieren
#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;> Verständnis:
- Wir haben ein Array von Strings. Der Unterschied zwischen einem Integer-Array und einem String-Array besteht darin:
- Ein Ganzzahl-Array ist eine Sammlung von Ganzzahlen
- Ein String-Array ist eine Sammlung von Zeichen-Arrays/Zeichenzeigern.
- Daher müssen wir in der Vergleichsfunktion die leeren Zeiger auf (char**)a und nicht auf (char*)a umwandeln.
[[Zeichenfolge 1], [Zeichenfolge 2]?]
Wenn wir char* verwenden, zeigt es auf das Array, und um dann auf eine Zeichenfolge im Array zu zeigen, benötigen wir einen Doppelzeiger. - Wir haben hier die Funktion strcmp() verwendet. Die Funktion ist in der Header-Datei string.h definiert. Wir müssen es zuerst einbeziehen.
- 0, wenn beide Zeichenfolgen gleich sind
- 1, wenn der ASCII-Wert eines Zeichens in der Zeichenfolge größer ist als das entsprechende Zeichen in der zweiten Zeichenfolge
- -1, wenn der ASCII-Wert eines Zeichens in der Zeichenfolge kleiner ist als der des entsprechenden Zeichens in der zweiten Zeichenfolge.
3. Sortieren eines Strukturarrays
#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;> Verständnis:
Wir haben ein Array vom Typ Struktur deklariert, was bedeutet, dass jedes Element im Array ein Array von Strukturelementen ist. Im obigen Programm besteht die Struktur aus zwei ganzzahligen Elementen. Die Aufgabe besteht darin, das Array in Bezug auf das erste Strukturelement zu sortieren. Wenn zwei beliebige erste Elemente gleich sind, müssen wir es anhand des zweiten Elements sortieren.
Beispiel:
dünner Algorithmus
[[1, 2], [3, 4], [1, 4]]
Sortiertes Array: [[1, 2], [1, 4], [3, 4]]
Wir haben die Funktion rand() verwendet, um zufällige Elemente im Array zu generieren. In der Funktion „compare()“ müssen wir die beiden Zeiger in die Typstruktur umwandeln.
Die Besonderheit der Verwendung von qsort() ist die benutzerdefinierte Vergleichsfunktion, die wir nach unseren Wünschen gestalten können. Wir können auch einige Elemente in einem Array sortieren und den Rest unsortiert lassen.