qsort() هي دالة قياسية محددة مسبقًا في مكتبة C. يمكننا استخدام هذه الوظيفة لفرز مصفوفة بترتيب تصاعدي أو تنازلي. ويستخدم داخليًا خوارزمية الفرز السريع، ومن هنا جاء اسم qsort. يمكنه فرز مصفوفة من أي نوع بيانات، بما في ذلك السلاسل والهياكل. إنه يعمل بشكل جيد وفعال في التنفيذ. هناك دالة فرز () في لغة C++ مشابهة لـ qsort() في لغة C. في جوانب مثل وقت التشغيل والسلامة والمرونة، تتفوق عملية فرز () على 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 مؤشرين فارغين للإشارة إلى العنصرين المراد مقارنتهما.
- يجب أن نكتب نص المقارنة () بالطريقة التي يجب أن تعود بها:
- 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 a = *(int*) num1;
pvr الشكل الكامل
int b = *(int*) num2;
مصفوفة الإدخال من النوع . وبالتالي، يجب علينا كتابة المؤشرات الفارغة إلى مؤشرات صحيحة قبل إجراء أي عمليات لتخصيص الذاكرة المطلوبة. قمنا بتخزين القيم التي يشير إليها المؤشران في متغيرين صحيحين آخرين، a وb. ثم قمنا بمقارنة القيمتين باستخدام عوامل المقارنة.
بدلاً من استخدام متغيرين مؤقتين آخرين، يمكننا كتابة رمز من سطر واحد:
int compare(const void* num1, const void* num2) { return *(int*)a - *(int*)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() لإنشاء عناصر عشوائية في المصفوفة. في دالة المقارنة ()، نحتاج إلى كتابة المؤشرين لكتابة البنية.
تخصص استخدام qsort() هو وظيفة المقارنة المخصصة التي يمكننا تصميمها بالطريقة التي نريدها. يمكننا أيضًا فرز بعض العناصر في مصفوفة وترك الباقي دون فرز.
5;>