تعرف على دالة الترتيب السريع qsort

السلام عليكم ورحمة الله وبركاته
إنه لمن الممتع أن تكتب دوالك بنفسك .. ستتعلم الكثير وتكتسف الأخطاء وتتدرب على المفاهيم الأساسية ..
ولكن عليك ان تعتاد رغم ذلك على استخدام الدوال الجاهزة التي قام عشرات المبرمجين بتطويرها لتصل الى المستوى المطلوب  ..
وغالبا ستجدها أسرع وأفضل من أي دالة تكتبها بنفسك .. (إن كانت تحقق المطلوب )

سنتعامل اليوم مع دالة الترتيب السريع qsort وهي التي تعتبر أسرع طرق الترتيب ..
الترتيب QuickSort والذي يأخذ( n*log(n عملية في الحالة المتوسطة .. لترتيب مصفوفة من n عنصراً .. ( هذه القيمة تسمى بالتعقيد الزمني Time Complexity وهي ليست عدد العمليات تماما  )
يجدر بك الاطلاع على خوارزمية الترتيب السريع لمعرفة كيفية عملها ... ولكن هذا غير ضروري الآن ..

تحتاج إلى معرفة أولية بالمؤشرات والدوال لفهم جيد .. كما انه من المهم جدا المامك بعملية تحويل الانواع cast

لنتعرف الآن على الدالة qsort
تأخذ هذا الدالة أربع وسطاء هي بالترتيب :
1-  مؤشر من نوع void يشير الى أول عنصر في المصفوفة (أي إلى المصفوفة ) .
2- عدد صحيح يحدد عدد عناصر المصفوفة .
3- عدد صحيح يحدد حجم العنصر الواحد في المصفوفة .
4- مؤشر إلى دالة مقارنة عنصرين ... صفاتها :
          1- تعيد عدداً صحيحاً يدل على ناتج مقارنة العنصرين الممررين كوسطاء
          2- تأخذ وسيطين من نوع const void *  أي أنهما مؤشران ثابتان على العنصرين الذين ستتم مقارنتهما .

أهم ما عليك تحديده هو أن دالة المقارنة إذا أعادت 0 فهي تقول أن القيمتين متساويتين
أما إذا أعادت أي عدد موجب فهذا يعني أن الوسيط الأول أكبر من الثاني
وإن أعادت قيمة سالبة فالوسيط الثاني هو الأكبر

  هذا كل ما تحتاجه لمعرفة استعمال الدالة ..

توقيع الدالة معقد بعض الشيء ولكن يمكننا تعديله قليلا لنقرأه كما يلي :

void qsort(void * _Base,
    int _NumOfElements, int _SizeOfElements,
       int (* _FuncCompare)(const void *, const void *));

(قمت باستبدال بعض الاسماء مثل size_t إلى int وحذف بعض المعرفات مثل__cdecl للتسهيل )
_______________________

لاستعمال الدالة .. يكفي تعريف دالة المقارنة فقط لا غير ثم يمكننا استعمال الدالة فورا ..

مثال يوضح طريقة الاستعمال :
نبدأ دوما مع دالة المقارنة .. حافظ على تعريف الدالة كما هو ..

int compare(const void*a,const void*b)
{
    int A=*((int*)a);
    int B=*((int*)b);
    if ( A < B )return -1;
    else if(A==B)return 0;
    else return 1;
}

يمكننا ان نجعل الترتيب تصاعديا أو تنازليا بتغيير الشروط ..
 ويمكن جعل الدالة أعقد لتقوم بمقارنة عناصر من كائن مع عناصر كائن آخر بطريقة تحددها انت ..
ليس هناك حدود لاستخدام الدالة طالما أنك تخافظ على القيم المعادة وتعريف الدالة كما هو ..

وهذا برنامج يوضح استخدام الدالة .. بأبسط ما يمكن ..

#include<cstdio>
int main()
{
    int a[10]={8,5,7,1,2,47,6,9,2,3};
    qsort ((void *)a, 10, sizeof(int), compare);
    for(int i=0;i<10;i++)
        printf("%i\n",a[i]);
}

لاحظ سهولة الاستخدام

كما أن وجود مؤشرات من نوع void*يعني أن الدالة عامة الاستخدام ولا تقتصر على نوع واحد من المصفوفات ..
المهم هنا هو الانتباه إلى القيام بتحويل الانواع المناسب عند تمرير الوسطاء وعند اختبار المقارنة ..

كيف يمكنك اغناء المشاركة ...
1- يمكنك كتابة برنامج يوضح ترتيب مصفوفة من struct ما .. يحوي اسماً ورقما ويقوم بالترتيب حسب الاسماء وعند تشابه الاسم يرتب حيب الرقم
2- يمكنك كتابة مثال آخر على استخدام الدالة ..
3- يمكنك تقديم روابط تشرح qsort من مصادر أخرى .. بشكل أفضل
4- يمكنك كتابة موضوع عن دوال أخرى للترتيب أو البحث مثل bsearch  مثلاً

كيف يمكنك الاساءة الى المشاركة ..
1-أن ترد بكلمة شكر فقط ..
2- أن تسأل عن أمر غير متعلق بالموضوع ..

أخيرا .. نسيت أن أذكر أن qsort موجودة في المكتبة cstdlib ..
والسلام عليكم ورحمة الله وبركاته
=================كاتب المقال: مصطفى 36a2 ==================