دالة qsort
في البداية، qsort هي دالة برمجية من مكتبة سي المعيارية ، تنفذ خوارزمية ترتيب (فرز) لمصفوفات من كائنات اعتباطية من تعريف المستعمل، استناداً على دالة أخرى للمقارنة، يعرِّفها المستعمل . تمت تسميتها بناءاً على خوارزمية "الفرز الأسرع- quicker sort" (تعديل من الفرز السريع (quicksort) من قبل R. S. Scowen) ، والذي تم استخدامه في الأصل لتنفيذه في مكتبة Unix C ، على الرغم من أن معيار C لا يتطلب تنفيذ الفرز السريع. وفيما يلي تفاصيل أوسع عن ذلك.
ومن جهة أخرى، يتم تحقيق العمل على أنواع مختلفة من البيانات ( تعدد الأشكال-Polymorphism ) من خلال أخذ مؤشر دالة إلى دالة مقارنة ، إلى جانب متغير يحدد حجم كائنات الإدخال الفردية الخاصة بها. تتطلب سي المعيارية دالة المقارنة لتنفيذ الترتيب الكلي على العناصر في المصفوفة المٌدخلة.
إضافةً إلى ذلك، مثلًا، يمكن لدالة qsort أن تقوم بترتيب هيكل بيانات "طابور الأولويات- priority queue"، المبني على مصفوفة (array) من العقد التي تضم كل منهم ما يدل على أولويتها و موضعها في الطابور، و التي قد يتم نداءها في نهاية عملية إضافة (إدراج) عقدة جديدة (enqueue)، لوضع كل عقدة في موضعها المناسب في الطابور. في حال استخدام الدالة في تطبيق متشعب، يجب مراعاة التزامن بين شرائط التعليمات التي تحاول الوصول للطابور ذو الأولوية، بحيث تكون عملية إضافة العٌقد عملية ذرية- غير قابلة للمقاطعة.
يجب ملاحظة ما يلي:
إضافةً إلى ذلك، 1- لن تصلح دالة qsort لفرز طابور أولويات مبني على هيكل القوائم المتصلة، حيث أن العٌقد في هذه الحالة غير مختزنة كقطعة متجاورة بالذاكرة كما المصفوفة، بل إن كل عقدة تشير للتي تليها.
وفي هذا السياق، 2- في حال إدراج عقدة جديدة في طابور الأولويات، يٌفضل أن تبحث العقدة عن موضعها في الطابور بتعقيد زمني بدلاً من إدراجها في نهاية الطابور ثم إجراء عملية الفرز بتعقيد زمني ، حيث أن n هو طول الطابور.
because of signed integer overflow. */
- if (x < y)
- return -1; // Return -1 if you want ascending, 1 if you want descending order.
- else if (x > y)
- return 1; // Return 1 if you want ascending, -1 if you want descending order.
int y = *(const int *)q;
/* Avoid return x - y, which can cause undefined behaviour
return 0;
return (x > y) - (x < y);
// All the logic is often alternatively written:
مثال
في هذا الإطار، يوضح الكود التالي بلغة C كيفية ترتيب مصفوفة من الأعداد الصحيحة باستخدام دالة qsort : #include
ومن ناحية أخرى، /* Comparison function. Receives two generic (void) pointers to the items under comparison. */
int compare_ints(const void *p, const void *q) {
int x = *(const int *)p;
تاريخها
من جانب آخر، تظهر دالة qsort في Version 2 Unix في عام 1972 كدالة مكتبية بلغة التجميع. تختلف واجهتها عن الإصدار الحديث ، الذي يمكن أن يكون نموذجها الإعلاني (prototype) مثل qsort(void * start, void * end, unsigned length) لترتيب سلاسل نصية بطول "length" من البايتات المخزنة بشكل متصل في الذاكرة من النطاق [ start، end). هذا ، وبالإضافة لعدم وجود دالة مقارنة قابلة للاستبدال ، فإن ذلك جعل من غير المناسب فرز الأعداد الصحيحة ذوات النهاية الأصغر (Little-Endian) للنظام بشكل صحيح ، أو أي هياكل بيانات أخرى.
كذلك، في عام 1991 ، لاحظ موظفو Bell Labs أن إصدارات AT&T و BSD من qsort تستهلك وقتاً تربيعياً لبعض المدخلات البسيطة. وهكذا صمم جون بنتلي ودوغلاس ماكلروي تطبيقًا جديدًا أسرع وأكثر قوة. أنتج McIlroy لاحقًا مدخلات تربيعية أكثر تعقيدًا ، تسمى AntiQuicksort ، في سنة 1998.
في هذا الإطار، الإصدار 4 من Unix يضيف تنفيذ برمجي بلغة C ، بواجهة مشابهة للمعيار. تمت إعادة كتابته في سنة 1983 لصالح Berkeley Software Distribution (BSD) . تم توحيد الدالة في ANSI C عام 1989. تمت إزالة الكود البرمجي بلغة التجميع في الإصدار 6 Unix .
كذلك، في الإصدار 3 من نظام التشغيل Unix ، تم توسيع الواجهة عن طريق استدعاء دالة مقارنة. قد يتم تعديل هذه الدالة من قبل المستعمل لتنفيذ أي نوع من الترتيب (تصاعدي/تنازلي) ، بطريقة مكافئة للمُدخل "compar" لدالة qsort في صورتها المعتمدة.
ملحقات
وعلى صعيد آخر، نظرًا لأن دالة المقارنة مثل "compare_ints" الخاصة بـ qsort لا تقبل سوى مؤشرين ، فإن تمرير معلمات إضافية (مثلًا: دالة مقارنة تقارن الفرق بين القيمتين المشار لهما بالمؤشرين الممرين للدالة نفسها مع قيمة أخرى) يجب أن يتم تكون القيمة الأخرى لمتغير من المتغيرات العامة (global variables). تم حل المشكلة بواسطة أنظمة BSD وGNU الشبيهة بـ Unix من خلال إدخال وظيفة qsort_r ، والتي تسمح بتمرير معلمة إضافية إلى وظيفة المقارنة. الإصداران من qsort_r لهما أوامر وسيطة مختلفة. يعرّف C11 الملحق K qsort_s بشكل أساسي مطابق لـ qsort_r الخاص بـ GNU.
}
- /* Sort an array of n integers, pointed to by a. */
- void sort_ints(int *a, size_t n) {
- qsort(a, n, sizeof(*a), compare_ints);
- }
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟