• 0
مصطفى 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

 

 

والله ولي التوفيق

3

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

3 إجابة على هذا السؤال .

  • 0

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

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

وإياكم أخي الكريم :)
عندما تحصر تفكيرك بالترتيب التصاعدي والتنازلي , تكون فد تجاوزت الكثير من الأمور المهمة , على كل حال إعادة تعريف عملية المقارنة > تعطي نفس نتائج وضع تابع compare ولكن بأسلوب مختلف

ولكن انظر إلى بعض الأمور الهامة : ماذا لو أردنا ترتيب قائمة من كائنات من نوع معين , مثلاً فيل :p
نريد ترتيب قائمة الفيلة حسب حجم الفيل أولاً ثم طول الأنياب ثانياً ثم مصدر الفيل , من افريقيا أم من سوريا .. ( أصلاً لا يوجد عندنا فيلة )

المهم : مثل هذا يحتاج إعادة تعريف المقارنة , أو تابع compare

 

لو أردت وضع الأعداد الزوجية في البداية والفردية في النهاية فالأمر بسيط :

داخل تابع المقارنة : إذا كان الأول زوجي والثاني فردي نعيد true ( إذا كان الأول فردي والآخر زوجي نعيد false)
أما إن كانا من نفس النوع فنعيد a<b عادية

وبذلك نخبر تابع الترتيب بأن يضع الزوجي دوماً قبل الفردي .
أحييك على الفكرة الجميلة

وفقك الله

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

حسنا فهمت . لا أدري لماذا حصرت تفكيري في التصاعدي والتنازلي فقط ، أما "الفيلة ههههه" فقد أفهمتني فوائد أكبر . سدد الله خطاك ووفقك

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

من فضلك سجل دخول لتتمكن من التعليق

ستتمكن من اضافه تعليقات بعد التسجيل



سجل دخولك الان

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .