دالة qsort

qsort هي دالة برمجية من مكتبة سي المعيارية ، تنفذ خوارزمية ترتيب (فرز) لمصفوفات من كائنات اعتباطية من تعريف المستخدم، استناداً على دالة أخرى للمقارنة، يعرِّفها المستخدم . تمت تسميتها بناءاً على خوارزمية "الفرز الأسرع- quicker sort" (تعديل من الفرز السريع (quicksort) من قبل R. S. Scowen) ، والذي تم استخدامه في الأصل لتنفيذه في مكتبة Unix C ، على الرغم من أن معيار C لا يتطلب تنفيذ الفرز السريع.

يتم تحقيق العمل على أنواع مختلفة من البيانات ( تعدد الأشكال-Polymorphism ) من خلال أخذ مؤشر دالة إلى دالة مقارنة ، بالإضافة إلى متغير يحدد حجم كائنات الإدخال الفردية الخاصة بها. تتطلب سي المعيارية دالة المقارنة لتنفيذ الترتيب الكلي على العناصر في المصفوفة المٌدخلة.

على سبيل المثال، يمكن لدالة qsort أن تقوم بترتيب هيكل بيانات "طابور الأولويات- priority queue"، المبني على مصفوفة (array) من العقد التي تضم كل منهم ما يدل على أولويتها و موضعها في الطابور، و التي قد يتم نداءها في نهاية عملية إضافة (إدراج) عقدة جديدة (enqueue)، لوضع كل عقدة في موضعها المناسب في الطابور. في حال استخدام الدالة في تطبيق متشعب، يجب مراعاة التزامن بين شرائط التعليمات التي تحاول الوصول للطابور ذو الأولوية، بحيث تكون عملية إضافة العٌقد عملية ذرية- غير قابلة للمقاطعة.

يجب ملاحظة ما يلي:

1- لن تصلح دالة qsort لفرز طابور أولويات مبني على هيكل القوائم المتصلة، حيث أن العٌقد في هذه الحالة غير مختزنة كقطعة متجاورة بالذاكرة كما المصفوفة، بل إن كل عقدة تشير للتي تليها.

2- في حال إدراج عقدة جديدة في طابور الأولويات، يٌفضل أن تبحث العقدة عن موضعها في الطابور بتعقيد زمني $O(n)$ بدلاً من إدراجها في نهاية الطابور ثم إجراء عملية الفرز بتعقيد زمني $O(nlog(n))$ ، حيث أن n هو طول الطابور.

تاريخها

تظهر دالة qsort في Version 2 Unix في عام 1972 كدالة مكتبية بلغة التجميع. تختلف واجهتها عن الإصدار الحديث ، الذي يمكن أن يكون نموذجها الإعلاني (prototype) مثل qsort(void * start, void * end, unsigned length) لترتيب سلاسل نصية بطول "length" من البايتات المخزنة بشكل متصل في الذاكرة من النطاق [ start، end). هذا ، وبالإضافة لعدم وجود دالة مقارنة قابلة للاستبدال ، فإن ذلك جعل من غير المناسب فرز الأعداد الصحيحة ذوات النهاية الأصغر (Little-Endian) للنظام بشكل صحيح ، أو أي هياكل بيانات أخرى.

في الإصدار 3 من نظام التشغيل Unix ، تم توسيع الواجهة عن طريق استدعاء دالة مقارنة. قد يتم تعديل هذه الدالة من قبل المستخدم لتنفيذ أي نوع من الترتيب (تصاعدي/تنازلي) ، بطريقة مكافئة للمُدخل "compar" لدالة qsort في صورتها المعتمدة.

الإصدار 4 من Unix يضيف تنفيذ برمجي بلغة C ، بواجهة مشابهة للمعيار. تمت إعادة كتابته في عام 1983 لصالح Berkeley Software Distribution (BSD) . تم توحيد الدالة في ANSI C عام 1989. تمت إزالة الكود البرمجي بلغة التجميع في الإصدار 6 Unix .

في عام 1991 ، لاحظ موظفو Bell Labs أن إصدارات AT&T و BSD من qsort تستهلك وقتاً تربيعياً لبعض المدخلات البسيطة. وهكذا صمم جون بنتلي ودوغلاس ماكلروي تطبيقًا جديدًا أسرع وأكثر قوة. أنتج McIlroy لاحقًا مدخلات تربيعية أكثر تعقيدًا ، تسمى AntiQuicksort ، في عام 1998.

مثال

يوضح الكود التالي بلغة C كيفية ترتيب مصفوفة من الأعداد الصحيحة باستخدام دالة qsort :

#include <stdlib.h>

/* 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;
    int y = *(const int *)q;

    /* Avoid return x - y, which can cause undefined behaviour
       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.

    return 0;
    // All the logic is often alternatively written:
    return (x > y) - (x < y);
}

/* 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);
}

ملحقات

نظرًا لأن دالة المقارنة مثل "compare_ints" الخاصة بـ qsort لا تقبل سوى مؤشرين ، فإن تمرير معلمات إضافية (على سبيل المثال: دالة مقارنة تقارن الفرق بين القيمتين المشار لهما بالمؤشرين الممرين للدالة نفسها مع قيمة أخرى) يجب أن يتم تكون القيمة الأخرى لمتغير من المتغيرات العامة (global variables). تم حل المشكلة بواسطة أنظمة BSD وGNU الشبيهة بـ Unix من خلال إدخال وظيفة qsort_r ، والتي تسمح بتمرير معلمة إضافية إلى وظيفة المقارنة. الإصداران من qsort_r لهما أوامر وسيطة مختلفة. يعرّف C11 الملحق K qsort_s بشكل أساسي مطابق لـ qsort_r الخاص بـ GNU.

مراجع