تطبيق خوارزمية Depth First Search لرسم متاهة

السلام عليكم ورحمة الله وبركاته
تعتبر خوارزمية Depth First Search أحد الخوارزميات للمرور على جميع النقاط المتصلة connected nodes في مخطط Graph ما ..
لا أريد التكرار فالموضوع عليه الكثير من الشروحات الواضحة على youTube  كما أن صفحة wikipedia فيها شرح ممتاز (وفيديو ملحق لإنشاء متاهة أيضاً )
ولكن لتبسيط الأمر .. تخيل أن لدينا شجرة كثيرة الفروع , حتى أن فروعها متداخلة , يعني يمكن أن يتقاطع فرعان ويندمجا !
تخيل أن هذه شجرة :
https://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Minimum_spanning_tree.svg/2000px-Minimum_spanning_tree.svg.png
هذه الأشجاء التخيلية التي تحوي فروعاً وتقاطعات تُسمّى Graphs (مخططات )
المهم ..
تخيل أننا نريد المرور على جميع فروع الشجرة . سنبدأ من الجذر ونصعد .. ثم سيتفرع الجذع الى عدة فروع .. وكل فرع سيتفرع لاحقاً وهكذا ..
هناك عدة طرق يمكننا من خلالها ضمان المرور على جميع الفروع .(المرور على جميع الفروع والتقاطعات(العقد) يُسمّى traversing )
إحداها طريقة Depth first Search
تحتاج لتطبيقها إلى مكدّس ومعرفة بسيطة في الحلقات والشروط .
خوارزمية DFS :
0-نضع الجذر في المكدس
ونبدأ الحلقة طالما أن المكدس غير فارغ :
1- نقوم بوضع علامة على العنصر في قمة المكدس للدلالة على انه قد تمت زيارته
2- نقوم باختبار وجود عناصر مرتبطة بالعنصر الحالي(قمة المكدس ) وهل هي صالحة للزيارة (تكون صالحة للزيارة إن كانت مرتبطة بالعنصر ولم تتم زيارتها من قبل )
3- كل عنصر يحقق الشرط في الخطوة 2 نضعه في المكدس
4- إن لم يحقق أي عنصر الشرط في الخطوة 2 نقوم بإخراج العنصر الحالي من المكدس
5- ان كان المكدس غير فارغ نذهب للخطوة 1

لنحول الخوارزمية إلى كود
نحتاج إلى آلية تكديس وسنستعمل std::stack, وآلية loop ويمكن أن نستعمل for  ,
وسنحتاج آلية لإعادة القيام بالعملية على العقدة الجديدة (يمكن أن نستعمل العودية recursion ولكن سنطبق اليوم بواسطة حلقة while)
كما أننا نحتاج وجود المخطط وبه العقد المتصلة (النقاط المتصلة) وسنستعمل ببساطة مصفوفة من بعدين , كل عنصرين متجاورين فيها يكونان مرتبطين
مثال للمصفوفة :
1 2 3
4 5 6
7 8 9
نقول أن 1 مع 4 و 2 مرتبطة , وكذلك :  9 مع 6 و 8 وهكذا
(يمكن لك أن تعتبر وجود ارتباطات بالمائل مثل 5 و 9 ان أردت )
يمكننا وضع علامة على النقطة التي تمت زيارتها ببساطة بتغيير قيمة المصفوفة مثلاً من 0 إلى 1
أخيراً  : نلاحظ أن الخطوة 4 لم تعد تحتاج إلى for loop  لأن العقد المرتبطة في حالة المصفوفة هي 4 كحد أقصى لذلك سنكتبها يدوياً

لنبدأ ..على بركة الله
تحويل الخوارزمية إلى كود :
أولا ودوماً أولاً : تطبيق بنية الـGraph
ببساطة مصفوفة يمكن ان تحوي 0 أو 1 .. bool
bool graph[30][30]={false};
القيمة false تعني أننا لم نزر أي عقدة بعد .
ثانياً : كيفية الامساك بعقدة ما ..
في حالتنا عن طريق الموضع في المصفوفة
سنكتب  struct بسيط يُمثّل الموضع

struct coord{
    int x;
    int y;
    coord(int x1,int y1){
        x=x1;
        y=y1;
    }
};

ولا ننسى آلية التكديس

stack <coord> s;

والآن  الحلقة التي سنعمل بداخلها الخطوات من 1 إلى 5 , وبها سنتابع بقية العمل , ولكن قبل الدخول إليها علينا دفع الجذر إلى المكدس (أو أي عقدة نرغب في البدء منها )

while(!s.empty())
{
 
}

سنقوم بملء التابع السابق كما توضّح الخوارزمية

1-عملية وضع علامة على الفرع الذي تمت زيارته

        graph[s.top().y][s.top().x]=true;

2-اختبار صلاحية زيارة جميع العقد المرتبطة , وبعد انتهاء العقد المرتبطة ( أو عدم وجودها فالأمر سيان ) أخرج العقدة الحالية من stack
سنختبر كل جهة على حدة كما يلي:

//look at left
        if(valid(s.top().y,s.top().x-1)){
            s.push(coord(s.top().y,s.top().x-1));
        }
        //look at right
        else if(valid(s.top().y,s.top().x+1)){
            s.push(coord(s.top().y,s.top().x+1));
        }
        //look up
        else if(valid(s.top().y-1,s.top().x)){
            s.push(coord(s.top().y-1,s.top().x));
        }
        //look down
        else if(valid(s.top().y+1,s.top().x)){
            s.push(coord(s.top().y+1,s.top().x));
        }
        else{
            s.pop();
        }

الكود بصيغته النهائية :
الكود :
أولاً : البنى والتوابع المساعدة

struct coord{
    int x;
    int y;
    coord(int y1,int x1){
        x=x1;
        y=y1;
    }
};
const int X=10,Y=10;
bool graph[Y][X]={false};
stack <coord> s;
bool valid(int y,int x){
    if(x<X&&x>=0)
        if(y<Y&&y>=0)
            if(graph[y][x]==false)
                return true;
    return false;
}

والتنفيذ في الدالةmain

int main()
{
    //push the current node
    s.push(coord(0,0));

    while(!s.empty())
    {
        graph[s.top().y][s.top().x]=true;

        //look at left
        if(valid(s.top().y,s.top().x-1)){
            s.push(coord(s.top().y,s.top().x-1));
        }
        //look at right
        else if(valid(s.top().y,s.top().x+1)){
            s.push(coord(s.top().y,s.top().x+1));
        }
        //look up
        else if(valid(s.top().y-1,s.top().x)){
            s.push(coord(s.top().y-1,s.top().x));
        }
        //look down
        else if(valid(s.top().y+1,s.top().x)){
            s.push(coord(s.top().y+1,s.top().x));
        }
        else{
            s.pop();
        }
    }

    return 0;
}

كي نتابع عملية السير سنكتب تابع بسيط لإظهار المخطط بعد كل تغيير
هذا مثال

void printGraph()
{
/*
Put here any implementation to return the pointer to top left
*/    

    cout << s.size() << " " << s.top().x <<" " <<s.top().y<< endl;
    for(int i=0;i<Y;i++)
    {
        for(int j=0;j<X;j++)
        {
            cout<<(graph[i][j]?'#':' ');
        }
        cout <<endl;
    }
/*
Put here any implementation to Sleep for 10-100 milli second
*/    
}

في ويندوز سأستعمل تابعين من الـ API

void printGraph()
{
    COORD topLeft={0,0};
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),topLeft);
    cout << s.size() << " " << s.top().x <<" " <<s.top().y<< "     " << endl;
    for(int i=0;i<Y;i++)
    {
        for(int j=0;j<X;j++)
        {
            cout<<(graph[i][j]?' ':'#');
        }
        cout <<endl;
    }
    Sleep(30);
}

ثم ضع استدعاء التابع داخل حلقة while الخاصة بالخوارزمية
جرب الكود التالي  في ويندوز (++C)

#include<stack>
#include<iostream>
#include<windows.h>
using std::stack;
using std::cout;
using std::endl;

struct coord{
    int x;
    int y;
    coord(int y1,int x1){
        x=x1;
        y=y1;
    }
};
const int X=10,Y=10;
bool graph[Y][X]={false};
stack <coord> s;
void printGraph()
{
    COORD topLeft={0,0};
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),topLeft);
    cout << s.size() << " " << s.top().x <<" " <<s.top().y<< "     " << endl;
    for(int i=0;i<Y;i++)
    {
        for(int j=0;j<X;j++)
        {
            cout<<(graph[i][j]?' ':'#');
        }
        cout <<endl;
    }
    Sleep(30);
}
bool valid(int y,int x){
    if(x<X&&x>=0)
        if(y<Y&&y>=0)
            if(graph[y][x]==false)
                return true;
    return false;
}

int main()
{

    //put flag on the visited node
    int x=0,y=0;

    //push the current node
    s.push(coord(x,y));

    while(!s.empty())
    {
        printGraph();
        graph[s.top().y][s.top().x]=true;

        //look at left
        if(valid(s.top().y,s.top().x-1)){
            s.push(coord(s.top().y,s.top().x-1));
        }
        //look at right
        else if(valid(s.top().y,s.top().x+1)){
            s.push(coord(s.top().y,s.top().x+1));
        }
        //look up
        else if(valid(s.top().y-1,s.top().x)){
            s.push(coord(s.top().y-1,s.top().x));
        }
        //look down
        else if(valid(s.top().y+1,s.top().x)){
            s.push(coord(s.top().y+1,s.top().x));
        }
        else{
            s.pop();
        }
    }
    return 0;
}

تجدر الإشارة إلى فكرة هامّة جداً ..
يعتمد المعالج في استدعاء التوابع على مكدّس خاص بالاستدعاءات
ويمكننا الاستغناء عن مكدسنا std::stack والاستعانة بالمكدس الخاص بالاستعداءات
وذلك عن طريق وضع العملية في تابع بدلاً من while , وبدلاً من عملية push سنقوم باستدعاء التابع مرة أخرى , وبمجرد انتهاء التابع أو عمل return  سيتم عمل pop للقيمة الحالية
انظر الكود التالي(أبسط من السابق)

#include<iostream>
#include<windows.h>
using std::cout;
using std::endl;

const int X=10,Y=10;
bool graph[Y][X]={false};
void printGraph()
{
    COORD topLeft={0,0};
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),topLeft);
    for(int i=0;i<Y;i++)
    {
        for(int j=0;j<X;j++)
        {
            cout<<(graph[i][j]?' ':'#');
        }
        cout <<endl;
    }
    Sleep(30);
}
bool valid(int y,int x){
    if(x<X&&x>=0)
        if(y<Y&&y>=0)
            if(graph[y][x]==false)
                return true;
    return false;
}
void function(int y,int x){
    printGraph();
    graph[y][x]=true;

    //look at left
    if(valid(y,x-1)){
        //s.push(coord(s.top().y,s.top().x-1));
        function(y,x-1);
    }
    //look at right
    if(valid(y,x+1)){
        //s.push(coord(s.top().y,s.top().x+1));
        function(y,x+1);
    }
    //look up
    if(valid(y-1,x)){
        //s.push(coord(s.top().y-1,s.top().x));
        function(y-1,x);
    }
    //look down
    if(valid(y+1,x)){
        //s.push(coord(s.top().y+1,s.top().x));
        function(y+1,x);
    }
//        s.pop();
        return ;
}
int main()
{
    function(0,0);
    return 0;
}

ولكننا خسرنا ميزة تتبع المكدس فلم يعد بإمكاننا مثلاً كتابة

cout << s.size() << " " << s.top().x <<" " <<s.top().y<< "     " << endl;

إذا جربت الكود , فستلاحظ أنه يسير بطريقة عادية ليمر على جميع عناصر المصفوفة , ولكن جرب كتابة

 function(5,5);

وسيبدأ من المنتصف , وعندها ستلاحظ سلوكاً غير متوقع (ربما) في المرور على جميع العناصر .

والآن إلى إنشاء المتاهة:
ببساطة سنتحرك خطوتين بدلاً من خطوة واحدة , وبذلك سنترك فراغات تُشكّل الحوائط !

#include<cstdio>
#include<windows.h>

const int X=21,Y=21;
bool graph[Y][X]={false};
void printGraph()
{
    COORD topLeft={0,0};
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),topLeft);
    for(int i=0;i<Y;i++)
    {
        for(int j=0;j<X;j++)
        {
            putchar(graph[i][j]?' ':'#');
        }
        putchar('\n');
    }
}
bool valid(int y,int x){
    if(x<X&&x>=0)
        if(y<Y&&y>=0)
            if(graph[y][x]==false)
                return true;
    return false;
}
void function(int y,int x){
    printGraph();

    //look at left
    if(valid(y,x-2)){
        //s.push(coord(s.top().y,s.top().x-1));
        graph[y][x-1]=true;
        graph[y][x-2]=true;
        function(y,x-2);
    }
    //look at right
    if(valid(y,x+2)){
        //s.push(coord(s.top().y,s.top().x+1));
        graph[y][x+1]=true;
        graph[y][x+2]=true;
        function(y,x+2);
    }
    //look up
    if(valid(y-2,x)){
        //s.push(coord(s.top().y-1,s.top().x));
        graph[y-1][x]=true;
        graph[y-2][x]=true;
        function(y-2,x);
    }
    //look down
    if(valid(y+2,x)){
        //s.push(coord(s.top().y+1,s.top().x));
        graph[y+1][x]=true;
        graph[y+2][x]=true;
        function(y+2,x);
    }
//        s.pop();
        return ;
}
int main()
{
    function(5,5);
    Sleep(100000);
    return 0;
}

جرب الكود , وستلاحظ أن المتاهة سهلة جداً  للحل
ولجعلها صعبة وعشوائية سنغير فقط طريقة الرؤية للكود ! ماذا يعني هذا ؟ يعني أن نجعل اختبارات (اليسارواليمين .. ) غير ثابته , فمثلاً يمكن أن نختبر المرور للأسفل قبل اليمين وهكذا ..
لاحظ اختلافات الكود :

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<windows.h>

const int X=31,Y=31;
bool graph[Y][X]={false};
void printGraph()
{
    COORD topLeft={0,0};
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),topLeft);
    for(int i=0;i<Y;i++)
    {
        for(int j=0;j<X;j++)
        {
            putchar(graph[i][j]?' ':'#');
        }
        putchar('\n');
    }
}
bool valid(int y,int x){
    if(x<X&&x>=0)
        if(y<Y&&y>=0)
            if(graph[y][x]==false)
                return true;
    return false;
}
void function(int y,int x){
    printGraph();
    for(int i=0;i<10;i++){//to ensure passing all valid moves
        int dx=0,dy=0;
        while(dx^dy==0){
            dy=rand()%2;//zero or one
            dx=rand()%2;//zero or one
        }
        if(rand()%2==1)
            dx*=-1,
            dy*=-1;
        if(valid(y+2*dy,x+2*dx)){
            //s.push(coord(s.top().y,s.top().x-1));
            graph[y+dy][x+dx]=true;
            graph[y+2*dy][x+2*dx]=true;
            function(y+2*dy,x+2*dx);
        }
    }
        return ;
}
int main()
{
    srand(time(0));
    function(5,5);
    Sleep(100000);
    return 0;
{

في الختام أود لفت الانتباه إلى أنه من الأمور الهامة جداً عند دراسة الخوارزميات عدم خلط الخورازمية بالتطبيق ,
مثلاً فتطبيق رسم المتاهة هو أحد التطبيقات لخوارزمية DFS وليس هو الخوارزمية , وقد وضعته كمثال رسومي جيد لبيان جمال الخوارزمية ليس أكثر .

والله ولي التوفيق
===================كاتب المقال: مصطفى 36a2==================

تعرف على دالة الترتيب السريع 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 ==================

تعرّف على التابع std::sort

السلام عليكم ورحمة الله ويركاته

هدف هذا المقال هو التعرف على تابع الترتيب الجاهز في مكتبة STL التي توفرها ++C , والذي يتم تطوير الـimplimentation بداخله نسخةً بعد نسخة , فقد بدأت بالترتيب السريع quick sort مع أول ظهور لها (إذ كانت تماثل تابع qsort في cstdlib ) أما الآن فهي تعتمد خوارزميات ترتيب أفضل , وأكثر ثباتاً ( ليست عشوائية , وتحقق(n*log (n في الحالة الأسوأ ) , آخر نسخة أعرفها تستخدم intro sort كمرحلة أولى ثم insertion sort كمرحلة ثانية .

فهرس المقالة :
1-  تعريف التابع sort
2- وسطاء التابع
2.5- عملية المقارنة
3- Member < Operator
4- Global < Operator
5- تمرير الوسيط الثالث كمؤشر إلى تابع
6- تمرير الوسيط الثالث كــ function object
7- تمرير الوسيط الثالث كعبارة lambda

التابع sort :
ما يهمنا هنا هو استخدام هذا التابع , والمعرّف كقالب template بالشكلين التاليين :

template <class RandomAccessIterator>
void sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

التعريف الأول يستخدم االعملية <  لمقارنة العناصر , أما الثاني فيستخدم تابع خاص للمقارنة .

وسطاء التابع :
الوسيط الأول: مؤشر وصول عشوائي لأول عنصر في القائمة المراد ترتيبها , مثلاً لو أردنا ترتيب مصفوفة فهو عنوان أول عنصر , أما لو أردنا ترتيب vector فهو الـ iterator الذي تعيده الدالة ()begin
الوسيط الثاني: مؤشر وصول عشوائي للعنصر بعد الأخير القائمة المراد ترتيبها .مثلاً لو أردنا ترتيب مصفوفة فهو عنوان أول عنصر + عدد العناصر , أما لو أردنا ترتيب vector فهو الـ iterator الذي تعيده الدالة ()end
الوسيط الثالث : هو مؤشر إلى تابع , أو functor سيتم شرحه بالتفصيل لاحقاً في هذا المقال .
مثال على ترتيب مصفوفة أعداد صحيحة :

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int a[]={9,7,5, 4,1,8,  2,3,4,  5};
    sort(a,a+10);
    for(int i=0;i<10;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

مثال على ترتيب vector :

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    vector<int>a={9,7,5, 4,1,8,  2,3,4,  5};
    sort(a.begin(),a.end());
    for(int i=0;i<10;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

عملية المقارنة :
أثناء القيام بعملية الترتيب , تتم مقارنة العناصر .
في لغة C يوجد التابع qsort الذي يحتاج وسيطاً هو تابع مقارنة , يعيد 1 في حال كان الوسيط الأول أكبر من الثاني , و -1 في حال أصغر , و 0 في حال التساوي .
أما في ++C , فالتابع sort  يقوم باختبار بولياني bool يعيد true أو false

Member < Operator :
ففي النسخة الأولى من التابع (ذات الوسيطين ) يقوم تلقائياً باختبار(if(a<b أي أنه يستخدم العملية (أصغر > )  , فلو كنت تريد ترتيب قائمة من نوع جديد , يجب أن يحوي هذا النوع بداخله على تعريف للعملية > .
مثال : لدينا نوع جديد اسمه book وأردنا تعريف عملية المقارنة > بحسب تاريخ الكتاب , ثم اسم مؤلفه ,

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
struct book{
    int date;// 2000bc --> 2014 ac
    string author;
    book(int d,string a):date(d),author(a){
    }
    bool operator<(const book second){
        if(date<second.date)
            return true;
        else if(date==second.date){
            if(author<=second.author)
                return true;
            else
                return false;
        }else
            return false;
    }
    void print(){
        cout<<"author "<<author<<" date:"<<date<<endl;
    }
};
int main()
{
    vector<book>a;
    a.push_back(book(1999,"mohammad"));
    a.push_back(book(2014,"mostafa"));
    a.push_back(book(2010,"ahmad"));
    a.push_back(book(1988,"mohammad"));
    sort(a.begin(),a.end());
    for(unsigned int i=0;i<a.size();i++){
        a[i].print();
    }
    return 0;
}
/*
( ملاحظة : الكود لا يعمل على Code::blocks لسبب لا أعرفه , تمت تجربته بنجاح على VS2008 )
*/

هنا استعملنا العملية كـ member function , وكملاحظة سريعة : يمكننا استخدام أي من التعاريف التالية للوسيط :

    bool operator<(const book second);
    bool operator<(const book &second);
    bool operator<(book second);
    bool operator<(book &second);

ولكن تختلف بغعاليتها , أما من ناحية الصلاحية فهي صالحة .

Global < Operator:
كما يمكننا تعريف عملية > بدون وضعها داخل فئة معينة , أي تعريقها كــ  Global Operator كما يلي :

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
struct book{
    int date;// 2000bc --> 2014 ac
    string author;
    book(int d,string a):date(d),author(a){
    }
    void print(){
        cout<<"author "<<author<<" date:"<<date<<endl;
    }
};
bool operator<(const book&first,const book&second){
        if(first.date<second.date)
            return true;
        else if(first.date==second.date){
            if(first.author<=second.author)
                return true;
            else
                return false;
        }else
            return false;
    }
int main()
{
    vector<book>a;
    a.push_back(book(1999,"mohammad"));
    a.push_back(book(2014,"mostafa"));
    a.push_back(book(2010,"ahmad"));
    a.push_back(book(1988,"mohammad"));
    sort(a.begin(),a.end());
    for(unsigned int i=0;i<a.size();i++){
        a[i].print();
    }
    return 0;
}
 

إن مسألة تعريف عملية الأصغر, مسألة مثيرة للاهتمام , فلا يمكنك ترتيب قائمة إن لم تكن تستطيع تحديد أي العناصر تريدها أن تكون في بداية القائمة وأيها في نهاية القائمة .
وعلى هذا المبدأ , يتعمد (التعريف الثاني للتابع ) على الوسيط الثالث compare
وهو تابع يأخذ وسيطين (من نوع العناصر في القائمة) ويعيد قيمة بوليانية boolean تكون true إن كان الأول أصغر من الثاني وfalse إن كان أكبر أو يساوي .
وبذلك يمكننا خداع الدالة بحيث تتعامل مع العملية > ونكون فعلياً نتعامل معها على أنها < لكي نعكس الترتيب (تصاعدي أو تنازلي )
ولكن للأسف , لا يمكننا إعادة تعريف عملية > للأنواع الأساسية , مثل int . فالكود التالي يعتبر خاطئاً

bool operator<(const int&a,const int&b){
    /*some operations*/
}

لذلك سنلجأ إلى كتابة تابع compare يقوم بالمهمة , وهو تماماً كفكرة عملية الـ > , يعيد قيمة بوليانية boolean ويأخذ وسيطين هما القيمتان المراد مقارنتهما .

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

#include <iostream>
#include <algorithm>
using namespace std;

bool compare(const int&a,const int&b){
    if(a<b)
        return true;
    else return false;
}
int main()
{
    int a[]={9, 7,6,4,   8,2,5, 4,3,1};
    sort(a,a+10,compare);
    for(unsigned int i=0;i<10;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

الكود السابق يقوم بالترتيب التصاعدي العادي , أما التالي فهو (بتغيير محتوى تابع المقارنة ) يقوم بالترتيب التنازلي (سأضع الدالة compare  فقط )

bool compare(const int&a,const int&b){
    if(b<a)
        return true;
    else return false;
}

لاحظوا أننا لو كتبنا الدالة compare كما يلي :

bool compare(const int&a,const int&b){
    return true;
}

سيتم وضع المصفوفة بشكل عشوائي لأن عملية الترتيب لن تتم بأي شكل منطقي .

تمرير الوسيط الثالث كــ function object :
يمكن تمرير الوسيط كـ functor أي كـ struct تم تعريف العملية () بداخله , وهذه الطريقة مفيدة في تسريع الكود , حيث يمكنها استغلال خاصية الـ inlining في الكود

#include <iostream>
#include <algorithm>
using namespace std;

struct test{
    bool operator()(const int&a,const int&b){
        if(a>b)
            return true;
        else return false;
    }
};
int main()
{
    int a[]={9, 7,6,4,   8,2,5, 4,3,1};
    sort(a,a+10,test());
    for(unsigned int i=0;i<10;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

أحد هذه الfunctor الجاهزة هو greater نستخدمه للترتيب التنازلي كـ functor جاهز :

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int a[]={9, 7,6,4,   8,2,5, 4,3,1};
    sort(a,a+10,greater<int>());
    for(unsigned int i=0;i<10;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

تمرير الوسيط الثالث كعبارة lambda  (خاص بـ C++11 وما بعد ) :
بالعودة إلى مؤشر التابع , من الأمور الممتعة في C++11 تعابير lambda , التي تسمح بتعريق التابع في وقت استخدامه ,وأحياناً يكون استخدامه مفيداً جداً في توضيح الكود ( بحيث نضع طريقة المقارنة في نفس مكان استدعاء الترتيب )

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int a[]={9, 7,6,4,   8,2,5, 4,3,1};
    sort(a,a+10,[](const int&a,const int&b){if(a>b)return true;else return false;});
    for(unsigned int i=0;i<10;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

هنا نصل إلى نهاية المقالة , أرجو أن أكون قد نقلت معظم الطرق التي تستخدم بها المقارنة في هذه الدالة , وأتمنى انه قد أصبح بإمكانك البدء باستخدام التابع std::sort دون أن تجد صعوبة في تحديد الطريقة التي تريد بها ترتيب العناصر .


المصادر :
STL Sort Comparison Function
cpp-reference
كيف تكتب تابع compare
مثال على ترتيب vector يحوي vector


والله ولي التوفيق
==========كاتب المقال : مصطفى 36a2 ==========