خوارزمية ترتيب المشط

#16 أغسطس 2014 في 22:47 صاحب الموضوع

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

ترتيب المشط خوارزمية ترتيب بسيطةً نسبياً , صممها في البداية Włodzimierz Dobosiewicz في عام 1980^. ثم أعاد اكتشافها Stephen Lacey و Richard Box في عام 1991. وتعد تحسيناً لخوارزمية ترتيب الفقاعات.

الخوارزمية

الفكرة الأساسية هي إزالة السلاحف, أو القيم الصغيرة الفريبة من نهاية القائمة, فهي سبب رئيسي في بطء خوارزمية ترتيب الفقاعات .

في حين لا تسبب الأرانب, القيم الكبيرة في بداية القائمة, أي مشكلة في ترتيب الفقاعات.

عند مقارنة أي عنصرين في ترتيب الفقاعات يكون بينهما فجوة (مسافة بين عنصرين) قيمتها 1.

الفكرة الأساسية في ترتيب المشط هي : إمكانية جعل هذه الفجوة أكبر من 1.

بكلام أكثر تخصصاً, تم تعديل الحلقة الداخلية في ترتيب الفقاعات, حيث تتم عملية الـتبديل الفعلية, بحيث تتناقص قيمة الفجوة بين العناصر التي تتم مقارنتها (خلال كل دورة للحقة الخارجية) بخطوات يحددها عامل الانكماش .

يتم ذلك كما يلي: [ حجم الدخل\عامل الانكماش , حجم الدخل\عامل الانكماش^2, حجم الدخل\عامل الانكماش^3, ...., 1 ]. وذلك على عكس ترتيب الفقاعات, حيث تكون قيمة الفجوة ثابتة أي 1.

تبدأ قيمة الفجوة من حجم القائمة مقسوماً على عامل الانكماش (عادةً 1.3), ويتم ترتيب القائمة بهذه القيمة للفجوة (بعد تقريبها لأقرب عدد صحيح أصغر منها إن لزم الأمر) .

ثم يتم تقسيم قيمة الفجوة على عامل الانكماش مرة أخرى ,ثم إعادة ترتيب المقائمة بقيمة الفجوة الجديدة , وهكذا يتم تكرار العملية حتى وصول قيمة الفجوة إلى 1.

عند هذه المرحلة , تتابع خوارزمية ترتيب المشط بقيمة الفجوة 1 حتى إتمام عملية الترتيب كلّيّاً . بالتالي فهي مكافئة لترتيب الفقاعات خلال هذه المرحلة , ولكن معظم السلاحف الموجودة يكون قد تم التعامل معها , ولذلك سيكون ترتيب الفقاعات فعالاً خلال هذه المرحلة.

يؤثّر معامل الانكماش بشكل كبير على ترتيب المشط . وقد اقترح المؤلف في مقاله الأصلي عن الخوارزمية قيمة 1.3 للهذا العامل .فالقيمة الصغيرة للمعامل تسبب بطء الخوارزمية لاحتياجها للمزيد من المقارنات , بينما تسبب القيمة الكبيرة للمعامل عدم حدوث أي مقارنة .وقد وجد Lacey و Box بالتجربة (عبر اختبار ترتيب المشط على أكثر من 200,000 قائمة عشوائية )أن القيمة 1.3 هي الأفضل لعامل الانكماش.

الصورة المتحركة التالية توضح الترتيب لقائمة من أعمدة مختلفة الأطوال :

شبه الكود

================================================================================

   تابع    ترتيب_المشط(  مصفوفة   الدخل )
    الفجوة    :=    الدخل.الحجم \\تهيئة حجم الفجوة
    الانكماش    :=    1.3 \\تعيين قيمة عامل الانكماش

       كرر حتى تصبح    الفجوة   =   1 و المبادَل   =    غ يرصحيح
        \\تحديث قيمة الفجوة لمشط جديد. ما يلي مجرد مثال
        الفجوة   := عددصحيح( الفجوة \ الانكماش  )\\قسمة صحيحة
        إذا كانت الفجوة < 1
          \\أصغر قيمة للفجوة هي 1
          الفجوة := 1
        نهاية جملة الشرط

        س    :=   0
        المبادَل   :=    غيرصحيح \\انظر ترتيب الفقاع ات للتوضيح

        \\"مشطٌ" واحد على قائمة الدخل
        كرر حتى تصبح س + الفجوة >= الدخل.الحجم
            إذا كانت الدخل[س] > الدخل[س+الفجوة]
                مبادلة (الدخل[س], الدخل[س+الفجوة])
                المبادَل := صحيح \\ ضع علامة بأن عملية تبادل قد تمّت مما يعني
                                \\ أن القائمة ليست مرتبة بالضرورة
            نهاية جملة الشرط
            س := س + 1
        نهاية جملة الشرط
    نهاية حلقة التكرار
نهاية التابع

================================================================================

وإليكم كود بسيط بلغة ++C هو مجرد ترجمة مباشرة لشبة الكود:

#include <iostream>using namespace std;int*CombSort(int*input,int input_size){    int gap=input_size;    double shrink=1.3;    bool swapped;    while (!( gap==1 and swapped==false )){//repeate until gap==1 and swapped==false        gap=int(gap/shrink);        if(gap<1)        {            gap=1;        }//end if        int i=0;        swapped=false;        while(!(    i+gap>=input_size    )){            if(input>input[i+gap]){                swap(input,input[i+gap]);                swapped=true;            }//end if            i=i+1;        }//end while    }//end while    return input;}//end combSortint main(){    int A[10]={9,7,1,8,6,4,5,2,4,1};    for(int i=0;i<10;i++)        cout<<A<<" ";    cout<<endl;    CombSort(A,10);    for(int i=0;i<10;i++)        cout<<A<<" ";    cout<<endl;    return 0;}

خاتمة :

أخي الكريم , لقد قمت أثناء كتابة هذه المقالة بالرجوع إلى صفحة ويكيبيديا الانكليزية كمرجع رئيسي , ولكن رغبة مني في تحسين المقال الذي بين يديك الآن , ورغبة مني في تحقيق الأمنية الغالية وهي وجود مرجع عربي ممتاز لعلوم الحاسب بشكل رئيسي , فقد قمت بكتابة صفحة ويكيبيديا العربية الخاصة بترتيب المشط , أرجو من أن تساهم في تحسينها لأنك تفيدنا جميعاً بذلك , كما أرجو أن يكون هذا المقال بذرة لمقالات أخرى نساهم فيها جميعاً , ربما يتطوع أحدنا لتشكيل ُ ٌ ٍ ِ ُ بعض الكلمات , وآخر لتصحيح بعض الأخطاء الإملائية وآخر لاستبدال الكلمات المترجمة بترجمة أفضل , كل هذا ليس له علاقة بخبرتك في الموضوع بل بغيرتك على لغتنا العربية وحبك لها .

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

تم تعديل هذه المشاركة بواسطة مصطفى 36a2 في 7 أغسطس 2014 في 10:01

#211 أغسطس 2014 في 00:04

لدي سؤال عن الtime complexity لخوارزمية المشط. حسب الويكي بالانجليزي ان اسوأ وقت هو $mimetex.cgi?O(n^2)$ وأفضل وقت هو $mimetex.cgi?O(n)$ والمتوسط هو $n^p)$ . حيث ان $mimetex.cgi?n$ هو عدد الارقام و $mimetex.cgi?p$ رقم لم افهمه من الويكي الانجليزي.

وطبعا هناك خوارزميات اسرع. لكن سؤالي هو: ماهو الجانب الذي يجعل خوارزمية المشط افضل من خوارزمية الهبل؟

هذه خوارزمية الهبل كتبتها. شبيهة بالمشط الا انها تفرض ان الفراغ دائما 0.

#include <stdio.h>

/* prints array */
void pa (int *a, int len, char *s);

int main() {
    /* unsorted array */
    int a[] = {5, 3, 10, 11, 1, 0, 100};
    int a_len = sizeof(a)/sizeof(int);
    pa(a, a_len, "unsorted array");

    /* sort array */
    int issorted = 1;
    do {
        printf("\tsorting..\n");
        issorted = 1;
        int c;
        for (c = 1; c < a_len; c++) {
            if (a[c] < a[c-1]) {
                issorted = 0;
                printf("\t\tswapping a[%d]=%d and a[%d]=%d\n", c-1, a[c-1], c, a[c]);
                int tmp = a[c];
                a[c] = a[c-1];
                a[c-1] = tmp;
            }
        }
    } while (issorted == 0);
    pa(a, a_len, "sorted array");

    return 0;
}

/* prints array */
void pa (int *a, int len, char *s) {
    printf("%s: ", s);
    int c;
    for (c = 0; c < len; c++) {
        printf("%d ", a[c]);
    }
    printf("\n");
}

يبدو لي ان خوارزمية الهبل ايضا تتمتع بنفس اسوأ وقت وأفضل وقت (صححني لو كنت مخطئا) لكن لم احسب الوقت المتوسط بعد. وهذا مايجعلني احتار في: هل خوارزمية المشط افضل من خوارزمية الهبل؟ واذا كان الجواب "نعم" فلماذا؟

نقطة جانبية: احييك على الكتابة في منصة الويكي. تصرف ذكي وسيؤدي الى تكاتف الجهود مستقبلا لتطوير المقالة اكثر واكثر. خطوة ذكية لم اشاهد مثلها في اي منتدى عربي اخر بنفسي.

تم تعديل هذه المشاركة بواسطة جونكر في 11 أغسطس 2014 في 00:14

حان الموعد حان موعدنـا :ph34r: جاء البطل يفرح شاشتنا
اهجم اهجم، لا تلــــــــي :ph34r: نحن معك أجمعيـــــــــن

#323 أغسطس 2014 في 08:34

شكراً لك جونكر على الرد والإثراء , السبب الأساسي من وجود ترتيب المشط هو إزالة السلاحف , والخوارزمية التي ذكرتها في ردك هي ترتيب الفقاعة bubble sort حسب ظني , ولكن من الامور الهامة التي يجب التنويه إليها هي أن خوارزمية المشط هي مرحلة أولية فقط تسبق ترتيب الفقاعة (يعني في الآخر سنستخدم ترتيب الفقاعة ولكن بعد ان نكون حسّنّا من حالة القائمة ) وهنا يأتي مفهوم الـ p والذي يمثل عدد المرات التي استخدمنا فيها المشط (قبل الوصول للفجوة gap=1) مثلاً لو بدأنا بفجوة 11 ثم 8 ثم 6 ثم 4 ثم 3 ثم 2 ثم 1 نقول أن p=7

ولكن لا تهتم كثيراً بالحالة المتوسطة نظرياً فهي غالباً غير مجدية عملياً بل قم بتجربة سلاسل عشوائية وترتيبها لتعطيك فكرة (وسطية) عن فائدة الخوارزمية

ماذكرته بخصوص الحالة المتوسطة خاطئ من ناحيتين :

الأولى : المقام هو 2^p وليس n^p

الثانية : هذه العلاقة ليست Big-Oh يعني ليست الحد الأعلى , بل omega يا صديق , هذا هو الحد الأدنى .

إذاً فالحد الأدنى هو 2^pا/n² حيث p هو عدد مرات استخدام فجوة أكبر من 1 انظر هنا واقرأCitation for complexity

بالعودة إلى أهمية الخوارزمية وفائدتها :

مثلاً السلسلة 9 8 7 6 5 4 3 2 1 10 تحتاج إلى 9 دورات في الحلقة do -while التي كتبتها حتى تنقل 10 إلى مكانه الصحيح(وفي كل دورة 9 عمليات مقارنة واحدة منها فقط مفيدة) (وهنا نسمي الـ10سلحفاة لأنها تنتقل خطوة واحدة كل دورة ) طبعاً هذا يعتمد على عملية المقارنة . يمكن أن تكون الخوارزمية تعمل على نقل الأصغر لليسار أو الأكبر لليمين .

إذا كانت تنقل الأكبر لليمين فهنا السلاحف هي القيم الصغيرة , أما إن كانت تنقل الأصغر لليسار فالقيم الكبيرة هي السلاحف.

سأعتمد في المقارنة السلسلة

int A[10]={10,2,3,4,5,6,7,8,9,1};

لأنها تحوي سلاحف في الاتجاهين .

إليك بعض الأرقام فهذا أفضل , هنا تجد 50 مقارنة و 13 عمليات استبدال في المشط , مقابل 90 مقارنة و 17 استبدال للفقاعة(أو الهبل كما تفضلت)

على أي حال المصفوفات العشوائية أفضل دليل على جودة الحالة المتوسطة للمشط , التطبيق على مصفوفة من 1000 عنصر عشوائي والنتيجة comparsisons=22712 swaps=4435 في المشط , مقابل comparisons = 946053 swaps=247855 في الفقاعة

أخيراً , سأنهي الرد بمصفوفة من 1000000 عنصر ما رأيك :)

comparsisons=56666781 swaps=10219199 نتيجة مبهرة أليس كذلك ;) تقريباً N*log(N)l

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

#428 أغسطس 2014 في 09:03

ابداع انت مذهل... يبدو ان الشرح العربي اسهل للفهم بواسطة المخ العربي :wub: :D :P اذا المشط والهبل (او الفقاعة) يتفقون في اسوا وقت وافضل وقت ولكن يختلفون في الوقت المتوسط بفارق شاسع

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

صفحة المشط http://en.wikipedia.org/wiki/Comb_sort#cite_note-BB-1

صفحة الفقاعة: http://en.wikipedia.org/wiki/Bubble_sort

تم تعديل هذه المشاركة بواسطة جونكر في 28 أغسطس 2014 في 09:13

حان الموعد حان موعدنـا :ph34r: جاء البطل يفرح شاشتنا
اهجم اهجم، لا تلــــــــي :ph34r: نحن معك أجمعيـــــــــن

#528 أغسطس 2014 في 09:09

اضافة: يبدو ان ظنك ان خوارزمية الهبل = خوارزمية الفقاعة صحيح.

بينما كنت اتحقق اعجبتني هذه الصورة المتحركة عن خوارزمية الفقاعة (او الهبل) من صفحة الويكي.

حان الموعد حان موعدنـا :ph34r: جاء البطل يفرح شاشتنا
اهجم اهجم، لا تلــــــــي :ph34r: نحن معك أجمعيـــــــــن

#629 أغسطس 2014 في 00:18

هذا اسمه عمل جماعي :) شكراً جزيلاً لك للإثراء

الصورة في الرد السابق توضح السلاحف في ترتيب الفقاعة أيّما توضيح .

بصراحة لو لم تسأل عن أهمية الخوارزمية لما كنت انتبهت للأمر , لذلك سؤالك كان مصيرياً في هذا الـThread (كيف نترجم هذه الكلمة )

المهم : بخصوص وجود Big-Oh في ترتيب الفقاعة في الجدول لا أظن أن فيه خطأ , ولكن وجود Omega في الحالة الأسوأ للمشط (يبدو) غير صحيح , لذلك اقترحت تعديله وربما يتم الموافقه عليه (رغم أنه مأخوذ من المرجع كما يقولون)

أظن أن الخوارزمية القادمة يجب أن تكون Shell Sort (ماذا سأترجمها ! ترتيب القوقعة ؟ فليكن )

بالتوفيق جونكر (متى سيحين دورك في الكتابة ;) )

#729 أغسطس 2014 في 03:51

الان صفحة الويكي الانجليزية لخوارزمية المشط سليمة شكرا لتصحيح

بالنسبة للويكي الانجليزية لخوارزمية الفقاعة الذي كتبته انا كان خطائا (احيانا افكر في شيء واكتب شيء اخر)...
كان قصدي هو لماذا "افضل" وقت مرموز له بالبيق اوه؟ اليس ينبغي ان يكون اوميغا لانه lower bound؟ (هذا سؤال مني وليس اقرار غير مباشر بالخطأ)

تم تعديل هذه المشاركة بواسطة جونكر في 29 أغسطس 2014 في 03:51

حان الموعد حان موعدنـا :ph34r: جاء البطل يفرح شاشتنا
اهجم اهجم، لا تلــــــــي :ph34r: نحن معك أجمعيـــــــــن

#829 أغسطس 2014 في 19:36

أظن أن الوقت الأفضل كـ Big-Oh أو كـ Big-Omega هو نفسه هنا $mimetex.cgi?O(n)$ أو $mimetex.cgi?\Omega(n)$ لا فرق , فكلاهما صحيح هنا .(استخدم وسم latex هكذا [latx]Hello[\latex] فقط استبدل الـ\ بـ / )

تم تعديل هذه المشاركة بواسطة مصطفى 36a2 في 29 أغسطس 2014 في 19:44

#931 أغسطس 2014 في 05:07

اظن ان رقمز اوميغا يستخدم فقط لافضل وقت بينما البيق اوه يستخدم لأسوأ وقت

حان الموعد حان موعدنـا :ph34r: جاء البطل يفرح شاشتنا
اهجم اهجم، لا تلــــــــي :ph34r: نحن معك أجمعيـــــــــن

#104 سبتمبر 2014 في 16:21

مارايك تشرح لنا بالعربي هذه المقالات:

http://en.wikipedia.org/wiki/Block_sort

http://en.wikipedia.org/wiki/Smoothsort

كلاهما غير مترجم بالعربي، لكن الافضل من هذا ان time complexity و ال space complexity لهذه الخوارزميات قوية جدا. اظن انه لا يوجد ماهو افضل منهم.

ايضا كلاهم لديهم نفس worst/best/avg time complexity, space complexity

حان الموعد حان موعدنـا :ph34r: جاء البطل يفرح شاشتنا
اهجم اهجم، لا تلــــــــي :ph34r: نحن معك أجمعيـــــــــن

#114 سبتمبر 2014 في 19:19

يا إلهي ! Block Sort لا تبدو شيئاً أرغب في قراءته حتى :)

أما smooth sort فقد أعجبتني :) تستحق الدراسة

شكراً جزيلاً لك , برأيك هل تحتاج الصفحة الحالية(التي نحن فيها) إلى المزيد من المعلومات أو الاختبارات ؟

#1210 سبتمبر 2014 في 23:15

نعم ارى انه جيد. بانتظار الدرس الجديد :tbyay:

حان الموعد حان موعدنـا :ph34r: جاء البطل يفرح شاشتنا
اهجم اهجم، لا تلــــــــي :ph34r: نحن معك أجمعيـــــــــن

#1311 سبتمبر 2014 في 22:39

جونكر انظر الى هذا :
يقولون أن smoothSort سيء من ناحية الـ constant وأنه ليس cache-frindly وهذا يعني أن QuickSort الذي يعاني بعض المعوقات أفضل منه عملياً !
على كل حال , موعدنا يوم الثلاثاء لتحليل هذه الخوارزمية بإذن الله

بالتوفيق

#1412 سبتمبر 2014 في 01:22

معلومة رائعة! يبدو ان عائلة خوارزميات الاشجار بدؤوا بالتفوق لانهم افضل من ناحية الكاش. والكويك سورت حسب الذي اعرفه انه يشبه نمو الشجرة (pvot point عشوائي وpartition، وكل partition سيتم ايجاد pvot point فيه وثم partitio. حركات recursion شبيه بالtrees في رأيي). صححني ان كنت مخطئا

سأحاول ان لا انسى اهمية الكاش مرة اخرى

حان الموعد حان موعدنـا :ph34r: جاء البطل يفرح شاشتنا
اهجم اهجم، لا تلــــــــي :ph34r: نحن معك أجمعيـــــــــن

#1512 سبتمبر 2014 في 20:47

كلامك صحيح من ناحية النمو , فالحالة المثالية للـ pivot هو أن يقسم الـقائمة المراد ترتيبها إلى قسمين متساويين (partitions ) وهذا يعني التحول 1 ثم 2 ثم 4 ثم 8 partitions وهكذا .. مما يوصلنا إلى ما يشبه balanced binary tree

ولا تنس أيضاً الميزة الهامة وهي أن خوارزميات الـ divide and conquer مثل quick sort هي parallelized وهذا يعني المزيد من السرعة .

رغم أنه بعيد عن quick sort :

أغلب الكتب التي تبحث في الـ Data Structures وتشرح عمليات الـdictionary تستقر في النهاية على الـ Binary Heap والـ Binary tree والـ **** Tree كلها أشجار ..

لذلك دراسة الأشجار والعمليات عليها أمر هام جداً , وأود هنا ذكر Segment Tree و Interval Tree التين تحلان العديد من المسائل الصعبة .. ولا أنسى Binary indexed Tree وكلها كما تفضلت تعتمد البنية الشجرية نظرياً (رغم تمثيلها في مصفوفة واحدة عادةً )

لا أريد الخروج كثيراً عن الموضوع لنترك مناقشة الأشجار إلى شجرة أخرى :)

#1619 سبتمبر 2014 في 22:20

ممتاز..

هل هناك درس جديد تريد وضعه عن اي موضوع يتعلق بالخوارزميات؟

حان الموعد حان موعدنـا :ph34r: جاء البطل يفرح شاشتنا
اهجم اهجم، لا تلــــــــي :ph34r: نحن معك أجمعيـــــــــن

#1719 سبتمبر 2014 في 23:32

كنت قد بدأت الكتابة بالفعل عنخوارزمية kruskal لإيجاد minimum spanning tree , وكنت أرغب في الكتابة عن LIS فكتبت هذا

بصراحة محتار ما التسلسل المناسب للخروج عن الرتابة في الكتابة في الامور الموجودة وفي نفس الوقت عدم التشتت في المواضيع

هل لديك فكرة ؟ وبماذا يمكننا التعاون في الكتابة أو تقسم المواضيع ؟

شكراً لك للسؤال

خوارزمية ترتيب المشط

مواضيع مشابهة