فرز q

دالة qsort هي دالة من مكتبة C القياسية تُنفّذ خوارزمية فرز لمصفوفات من كائنات عشوائية وفقًا لدالة مقارنة يُحددها المستخدم. سُميت هذه الدالة نسبةً إلى خوارزمية "الفرز السريع" ^{[ 1 ]} (وهي نسخة معدلة من خوارزمية الفرز السريع من تطوير RS Scowen)، والتي استُخدمت فيالأصل لتنفيذها في مكتبة C الخاصة بنظام Unix ، على الرغم من أن معيار C لا يشترط ذلك لتنفيذ خوارزمية الفرز السريع. ^{[ 2 ]} وهي مُدمجةفي مكتبة C++ القياسية .<stdlib.h><cstdlib>

تُحقق القدرة على التعامل مع أنواع مختلفة من البيانات ( تعدد الأشكال ) من خلال أخذ مؤشر دالة إلى دالة مقارنة ثلاثية ، بالإضافة إلى مُعامل يُحدد حجم كل كائن من كائنات الإدخال الخاصة بها. يتطلب معيار لغة C أن تُنفذ دالة المقارنة ترتيبًا كليًا على عناصر مصفوفة الإدخال. ^{[ 3 ]}

ظهرت دالة qsort في الإصدار الثاني من نظام يونكس عام 1972 كدالة فرعية للغة التجميع . تختلف واجهتها عن النسخة الحديثة، إذ يمكن تمثيلها ظاهريًا على أنها تقوم بفرز سلاسل بايتات متجاورة بطول n من النطاق [ start , end ). ^{[ 1 ]} هذا، بالإضافة إلى عدم وجود دالة مقارنة قابلة للاستبدال، يجعلها غير مناسبة لفرز الأعداد الصحيحة ذات الترتيب الصغير (little-endian) في النظام ، أو أي هياكل بيانات أخرى.voidqsort(void*start,void*end,unsignedintlength)length

في الإصدار الثالث من يونكس ، تم توسيع الواجهة باستدعاء compar(III)، بواجهة مطابقة لواجهة memcmp الحديثة . يمكن لبرنامج المستخدم تجاوز هذه الدالة لتنفيذ أي نوع من الترتيب، بطريقة مكافئة لوسيط الدالة standard (مع أنها عامة على مستوى البرنامج، بالطبع). ^{[ 4 ]}comparqsort

أضاف الإصدار الرابع من يونكس تطبيقًا بلغة C، بواجهة مكافئة للمعيار. ^{[ 5 ]} أُعيدت كتابته عام 1983 لتوزيعة برمجيات بيركلي . ^{[ 2 ]} تم توحيد الدالة في معيار ANSI C (1989). أُزيل تطبيق لغة التجميع في الإصدار السادس من يونكس . ^{[ 6 ]}

في عام 1991، لاحظ موظفو مختبرات بيل أن إصدارات AT&T وBSD من البرنامج qsortتستهلك وقتًا تربيعيًا لبعض المدخلات البسيطة. ولذلك، قام جون بنتلي ودوغلاس ماكلروي بتصميم تطبيق جديد أسرع وأكثر كفاءة. ^{[ 2 ]} وفي وقت لاحق، أنتج ماكلروي في عام 1998 برنامجًا أكثر تعقيدًا بمدخلات تربيعية، أطلق عليه اسم AntiQuicksort . تقوم هذه الدالة بإنشاء بيانات معادية بشكل فوري. ^{[ 7 ]}

يوضح جزء الكود التالي المكتوب بلغة C كيفية فرز قائمة من الأعداد الصحيحة باستخدام qsort.

#include <stdlib.h>// دالة المقارنة. تستقبل مؤشرين عامين (فارغين) إلى العناصر المراد مقارنتها. int compareInts ( const void * p , const void * q ) { int x = * ( const int * ) p ; int y = * ( const int * ) q ;// تجنب إرجاع x - y، فقد يتسبب ذلك في سلوك غير محدد // بسبب تجاوز سعة الأعداد الصحيحة الموقعة. إذا ( x < y ) { // أرجع -1 للترتيب التصاعدي، و+1 للترتيب التنازلي. أرجع -1 ؛ } وإلا إذا ( x > y ) { // أرجع +1 للترتيب التصاعدي، و-1 للترتيب التنازلي. أرجع 1 ؛ } وإلا { أرجع 0 ؛ } }// يمكن كتابة هذا بشكل أكثر اختصارًا على النحو التالي: int compareInts ( const void * p , const void * q ) { int x = * ( const int * ) p ; int y = * ( const int * ) q ;return ( x > y ) - ( x < y ); }// فرز مصفوفة من n عددًا صحيحًا، يشير إليها المؤشر a. void sortInts ( int * a , size_t n ) { qsort ( a , n , sizeof ( * a ), compareInts ); }

بما أن دالة المقارنة في الأصل qsortلا تقبل سوى مؤشرين، فإن تمرير معلمات إضافية (مثل إنشاء دالة مقارنة تقارن بين قيمتين بناءً على الفرق بينهما) يتطلب استخدام متغيرات عامة . وقد حلت أنظمة BSD و GNU الشبيهة بنظام Unix هذه المشكلة من خلال إضافة qsort_rدالة تسمح بتمرير معلمة إضافية إلى دالة المقارنة. qsort_rيختلف ترتيب الوسائط في النسختين. يُعرّف الملحق K من معيار C11qsort_s دالة مطابقة تقريبًا لدالة GNU qsort_r. كما تحتوي مكتبات macOS و FreeBSDqsort_b على دالة أخرى، وهي نسخة معدلة تستخدم الكتل ، وهي نظير للإغلاقات ، كحل بديل للمشكلة نفسها. ^{[ 8 ]}

في لغة C++، يُعد استخدام std::sort أسرع (أو بدءًا من C++20 فصاعدًا). ​​بالمقارنة مع std ::sort، فإن std::sort المُنمذج أكثر أمانًا من حيث النوع، لأنه لا يتطلب الوصول إلى عناصر البيانات عبر مؤشرات غير آمنة، كما هو الحال مع std::sort. أيضًا، يصل std::sort إلى دالة المقارنة باستخدام مؤشر دالة، مما يستلزم عددًا كبيرًا من استدعاءات الدوال المتكررة، بينما في std::sort ، يمكن تضمين دوال المقارنة في كود الكائن المخصص المُنشأ لإنشاء قالب. عمليًا، غالبًا ما يكون كود C++ الذي يستخدم std::sort أسرع بكثير في فرز البيانات البسيطة مثل الأعداد الصحيحة من كود C المكافئ الذي يستخدم std ::sort . ^{[ 9 ]}std::ranges::sort::qsortstd::sortvoid::qsort::qsortstd::sortstd::sort::qsort