تعرّف على التابع 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 ==========