عبد العزيز: بوت:صيانة المراجع.

2023-08-16T21:42:53Z

بوت:صيانة المراجع.

صفحة جديدة

{{يتيمة|تاريخ =أغسطس 2023}}
{{مقالة غير مراجعة|تاريخ =أغسطس 2023}}
'''qsort''' هي دالة برمجية من [[مكتبة سي المعيارية|مكتبة سي المعيارية ،]] تنفذ [[خوارزمية ترتيب|خوارزمية]] ترتيب (فرز) لمصفوفات من كائنات اعتباطية من تعريف المستخدم، استناداً على دالة أخرى للمقارنة، يعرِّفها المستخدم . تمت تسميتها بناءاً على خوارزمية "الفرز الأسرع- quicker sort" <ref name="v2">{{استشهاد ويب|صفحة=193|محرر1-وصلة=Ken_Thompson|محرر2-وصلة=Dennis_Ritchie|تاريخ =June 12, 1972|عنوان =UNIX Programmer's Manual, Second Edition|مسار = https://www.tuhs.org/Archive/Distributions/Research/Dennis_v2/v2man.pdf#page=193|ناشر =[[مختبرات بل|Bell Telephone Laboratories]]|مسار أرشيف= https://web.archive.org/web/20230730004315/https://www.tuhs.org/Archive/Distributions/Research/Dennis_v2/v2man.pdf|تاريخ أرشيف=2023-07-30}}</ref> (تعديل من [[ترتيب سريع|الفرز السريع]] (quicksort) من قبل R. S. Scowen) ، والذي تم استخدامه في الأصل لتنفيذه في مكتبة [[يونكس|Unix]] C ، على الرغم من أن معيار C لا يتطلب تنفيذ الفرز السريع. <ref name="engineering">{{استشهاد بدورية محكمة|الأول=Jon L.|الأخير=Bentley|الأخير2=McIlroy|المجلد=23|العدد=11|صفحات=1249–1265|سنة=1993|DOI=10.1002/spe.4380231105|صحيفة=Software: Practice and Experience|عنوان=Engineering a sort function|مسار = http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8162|الأول2=M. Douglas|مسار أرشيف= https://web.archive.org/web/20230603043530/https://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8162|تاريخ أرشيف=2023-06-03}}</ref>

يتم تحقيق العمل على أنواع مختلفة من البيانات ( ''[[تعددية الأشكال (علم الحاسوب)|تعدد الأشكال]]''-Polymorphism ) من خلال أخذ [[مؤشر دالة]] إلى دالة مقارنة ، بالإضافة إلى متغير يحدد حجم كائنات الإدخال الفردية الخاصة بها. تتطلب [[أنسي سي|سي المعيارية]] دالة المقارنة لتنفيذ [[ترتيب كلي|الترتيب الكلي]] على العناصر في المصفوفة المٌدخلة. <ref>ISO/IEC 9899:201x, Programming Languages—C (draft). §7.22.5. November 16, 2010.</ref>

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

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

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

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

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

في [[يونكس مركز البحوث|الإصدار 3 من نظام التشغيل Unix]] ، تم توسيع الواجهة عن طريق استدعاء دالة مقارنة. قد يتم تعديل هذه الدالة من قبل المستخدم لتنفيذ أي نوع من الترتيب (تصاعدي/تنازلي) ، بطريقة مكافئة للمُدخل "<code>compar</code>" لدالة '''qsort''' في صورتها المعتمدة. <ref>{{استشهاد ويب|محرر1-وصلة=Ken_Thompson|محرر2-وصلة=Dennis_Ritchie|تاريخ =February 1973|صفحة ="qsort(III)"|عنوان =UNIX Programmer's Manual, Third Edition|مسار = https://minnie.tuhs.org/cgi-bin/utree.pl?file=V3/man/man3/qsort.3|ناشر =[[مختبرات بل|Bell Telephone Laboratories]]|مسار أرشيف= https://web.archive.org/web/20230724162149/https://minnie.tuhs.org/cgi-bin/utree.pl?file=V3/man/man3/qsort.3|تاريخ أرشيف=2023-07-24}}</ref>

[[يونكس مركز البحوث|الإصدار 4 من Unix]] يضيف تنفيذ برمجي بلغة C ، بواجهة مشابهة للمعيار. <ref>{{استشهاد ويب|محرر1-وصلة=Ken_Thompson|محرر2-وصلة=Dennis_Ritchie|تاريخ =November 1973|صفحة ="qsort(III)"|عنوان =UNIX Programmer's Manual, Fourth Edition|مسار = https://minnie.tuhs.org/cgi-bin/utree.pl?file=V4/man/man3/qsort.3|ناشر =[[مختبرات بل|Bell Telephone Laboratories]]|مسار أرشيف= https://web.archive.org/web/20230724162147/https://minnie.tuhs.org/cgi-bin/utree.pl?file=V4/man/man3/qsort.3|تاريخ أرشيف=2023-07-24}}</ref> تمت إعادة كتابته في عام 1983 لصالح [[توزيعة برمجيات بيركلي|Berkeley Software Distribution]] (BSD) . <ref name="engineering" /> تم توحيد الدالة في [[أنسي سي|ANSI C]] عام 1989. تمت إزالة الكود البرمجي بلغة التجميع في الإصدار 6 Unix . <ref>{{استشهاد ويب|عنوان=qsort(III), from UNIX Programmer's Manual, Sixth Edition|مسار = http://minnie.tuhs.org/cgi-bin/utree.pl?file=V6/usr/man/man3/qsort.3|موقع =Unix Archive|مسار أرشيف= https://web.archive.org/web/20230225015936/https://minnie.tuhs.org/cgi-bin/utree.pl?file=V6/usr/man/man3/qsort.3|تاريخ أرشيف=2023-02-25}}</ref>

في عام 1991 ، لاحظ موظفو Bell Labs أن إصدارات AT&T و BSD من qsort تستهلك [[تعقيد الوقت|وقتاً تربيعياً]] لبعض المدخلات البسيطة. وهكذا صمم [[جون بنتلي (عالم حاسوب)|جون بنتلي]] [[دوغلاس ماكلروي|ودوغلاس ماكلروي]] تطبيقًا جديدًا أسرع وأكثر قوة. <ref name="engineering" /> أنتج McIlroy لاحقًا مدخلات تربيعية أكثر تعقيدًا ، تسمى ''AntiQuicksort'' ، في عام 1998. <ref>{{استشهاد بدورية محكمة|الأخير=McIlroy|الأول=M. D.|المجلد=29|صفحات=341–344|DOI=10.1002/(SICI)1097-024X(19990410)29:4<341::AID-SPE237>3.0.CO;2-R|العدد=4|صحيفة=Software—Practice & Experience|تاريخ=10 April 1999|عنوان=A killer adversary for quicksort|مسار = https://www.cs.dartmouth.edu/~doug/mdmspe.pdf|مسار أرشيف= https://web.archive.org/web/20230619014319/https://www.cs.dartmouth.edu/~doug/mdmspe.pdf|تاريخ أرشيف=2023-06-19}}</ref>

== مثال ==
يوضح الكود التالي بلغة C كيفية ترتيب مصفوفة من الأعداد الصحيحة باستخدام دالة qsort : <syntaxhighlight lang="c">
#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);
}
</syntaxhighlight>

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

<big>'''مراجع'''</big>
{{مراجع}}

{{مقالات بحاجة لشريط بوابات}}

[[تصنيف:خوارزميات ترتيب]]
[[تصنيف:مكتبة سي المعيارية]]
[[تصنيف:صفحات بترجمات غير مراجعة]]

دالة qsort - تاريخ المراجعة

عبد العزيز: بوت:صيانة المراجع.