qsort() היא פונקציה סטנדרטית מוגדרת מראש בספריית C. אנו יכולים להשתמש בפונקציה זו כדי למיין מערך בסדר עולה או יורד. הוא משתמש באופן פנימי באלגוריתם המיון המהיר, ומכאן השם qsort. זה יכול למיין מערך מכל סוג נתונים, כולל מחרוזות ומבנים. זה עובד היטב ויעיל ליישום. יש פונקציה sort() ב-C++ בדומה ל-qsort() ב-C. בהיבטים כמו זמן ריצה, בטיחות וגמישות, sort() עולה על qsort().
מדריך זה מסביר את הפונקציה qsort() עם דוגמאות. תקן C לא ציין את המורכבות של הפונקציה, אך מכיוון שבאופן פנימי הוא עוקב אחר אלגוריתם המיון המהיר, מורכבות הזמן הממוצעת שלה נלקחת באופן טנטטיבי להיות O(n*logn). הפונקציה מוגדרת בקובץ הכותרת stdlib; לפיכך עלינו לכלול אותו לפני השימוש בו.
#include
תחביר של הפונקציה:
qsort(array, number, size, function)
מַעֲרָך : המערך שיש למיין.
ניק בלבד
מספר : מספר האלמנטים במערך שאנו רוצים למיין
גודל : גודל של רכיב בודד של המערך
פוּנקצִיָה : פונקציית השוואה מותאמת אישית שעלינו לכתוב בפורמט מוגדר:
פורמט מוגדר של הפונקציה:
int compare( const void* a, const void* b) { } - qsort() קורא לפונקציה compare() עבור כל שני אלמנטים במערך.
- הטיעונים a ו-b הם שני מצביעים לריק להצביע על שני האלמנטים שיש להשוות.
- עלינו לכתוב את הגוף של compare() באופן שבו הוא אמור להחזיר:
- 0 אם שני יסודות שווים
- -1 או כל מספר שלם שלילי אחר אם האלמנט הראשון קטן מהאלמנט השני
- 1 או כל מספר חיובי אחר אם האלמנט הראשון גדול מהשני.
- השם של פונקציית ההשוואה יכול להיות כל דבר, אבל השם חייב להינתן בדיוק כארגומנט לפונקציה qsort() .
- const void* a פירושו a הוא מצביע ריק שערכו קבוע. לפני השימוש, עלינו לשדר מצביע ריק לסוג נתונים כלשהו.
כעת, נחקור את הפונקציות למיון מערכים מסוגי נתונים שונים.
1. מיון מספרים שלמים:
#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)> הֲבָנָה:
בשתי שורות אלו:
מחרוזת של int
int a = *(int*) num1;
int b = *(int*) num2;
מערך הקלט הוא מסוג . לפיכך, עלינו להקליד את מצביעי הריק למצביעים שלמים לפני ביצוע פעולות כלשהן להקצאת הזיכרון הנדרש. אחסנו את הערכים ששני המצביעים מצביעים עליהם בשני משתנים שלמים אחרים, a ו-b. לאחר מכן, השווינו את שני הערכים באמצעות אופרטורי ההשוואה.
במקום להשתמש בשני משתנים זמניים נוספים, נוכל לכתוב קוד בשורה אחת:
int compare(const void* num1, const void* num2) { return *(int*)a - *(int*)b; } - אם a==b, מוחזר 0; אם a > b, מוחזר מספר שלם חיובי; אם
2. מיון מחרוזות
#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;> הֲבָנָה:
- יש לנו מערך של מחרוזות. ההבדל בין מערך שלמים למערך מחרוזת הוא ש:
- מערך שלמים הוא אוסף של מספרים שלמים
- מערך מחרוזת הוא אוסף של מערכי תווים/מצביעי תווים.
- לפיכך, בפונקציית ההשוואה, עלינו להטיל את מצביעי הריק ל-(char**)a ולא (char*)a.
[[מחרוזת 1], [מחרוזת 2]?]
כאשר אנו משתמשים ב-char*, הוא מצביע על המערך, ולאחר מכן, כדי להצביע על מחרוזת במערך, אנו צריכים מצביע כפול. - השתמשנו בפונקציה strcmp() כאן. הפונקציה מוגדרת בקובץ הכותרת string.h. אנחנו צריכים לכלול את זה קודם.
- 0 אם שתי המחרוזות זהות
- 1 אם ערך ASCII של תו במחרוזת גדול מהתו המקביל במחרוזת השנייה
- -1 אם ערך ASCII של תו במחרוזת קטן מהתו המקביל במחרוזת השנייה.
3. מיון מערך מבנה
#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;> הֲבָנָה:
הכרזנו על מערך מסוג Structure, כלומר כל אלמנט במערך הוא מערך של רכיבי מבנה. בתוכנית לעיל, למבנה שני אלמנטים שלמים. המשימה היא למיין את המערך ביחס לאלמנט המבנה הראשון, ואם יש שני אלמנטים ראשונים שווים, עלינו למיין אותו באמצעות האלמנט השני.
דוגמא:
[[1, 2], [3, 4], [1, 4]]
מערך ממוין: [[1, 2], [1, 4], [3, 4]]
השתמשנו בפונקציה rand() כדי ליצור אלמנטים אקראיים במערך. בפונקציה compare() אנחנו צריכים להטיל את שני המצביעים לסוג המבנה.
השוואת מחרוזות ב-java
המומחיות של השימוש ב-qsort() היא פונקציית ההשוואה המותאמת אישית שאנו יכולים לעצב כפי שאנו רוצים. אנחנו יכולים גם למיין כמה אלמנטים במערך ולהשאיר את השאר לא ממוינים.