• 0
مصطفى 36a2

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

سؤال

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

post-256536-0-96201000-1404935855.gif

حديثنا اليوم عن خوارزمية ترتيب ممتعة , بالرغم من كون تعقيدها الزمني (O(n2 , إلا أنها ملفتة للنظر بفكرتها , ومعرفتُها (قد) تؤدي بنا إلى تطوير خوارزميات أخرى أو على الأقل التفكير بطريقة جديدة , والهدف من استهداف هذه الخوارزمية في هذه المقالة هو جماليتها لا فاعليتها .

خوارزمية خلّاط الكوكتيل !

أو باسمها الرسمي الترتيب الفقاعي ثنائي الاتجاه .

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

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

مثال (على الترتيب الفقاعي) :لدينا القائمة

post-256536-0-54977100-1404932924.gif

نريد ترتيبها تصاعدياً بحيث يكون الأصغر على اليسار والأكبر على اليمين

لذلك نقوم بعمل n-1 مقارنة (حيث n هنا هو 6 ) كما يلي

post-256536-0-56295700-1404932979.gif

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

فتصبح

post-256536-0-29226700-1404933017.gif

ثم نقوم بمقارنة الزوج الثاني

post-256536-0-97415300-1404933058.gif

ونقوم بالاستبدال لأن الأيسر أكبر من الأيمن

post-256536-0-61904600-1404933104.gif

وهكذا سينتج لدينا بعد كل مقارنة واستبدال التسلسل التالي
post-256536-0-12959300-1404933216.gif

والآن انتهى المرور الأول (احتاج إلى 5 عمليات استبدال)

 لاحظ كيف أن الرقم 9 انتقل من أقصى اليمين إلى أقصى اليسار  ,ولكن الرقم الأصغر 1 انتقل خطوة واحدة فقط لليمين وهذا ما يسمى بمشكلة السلحفاة ,

 أي أن الرقم الصغير يسير ببطء شديد نحو موضعه الحقيقي , فالترتيب الفقاعي للقائمة السابقة (بعد انتهاء المرور الثاني , يحتاج إلى 3 عمليات استبدال ) سيكون :

post-256536-0-88567200-1404933285.gif

لاحظوا أن النتيجة ظهرت وكأننا قمنا بعمل insertion sort بحيث وضعنا الـ 4 في مكانها وأزحنا الباقي لليسار

بعد المرور الثالث (عمليتا استبدال) :

post-256536-0-85193100-1404933321.gif

وبعد المرور الرابع ( عملية استبدال واحدة )

post-256536-0-73616200-1404933362.gif

احتجنا إلى 11 عملية استبدال

أما ترتيب الكوكتيل , فالاختلاف الوحيد بينه وبين الترتيب الفقاعي هو أن المرور ذو الرقم الزوجي ( مثلاً المرور الثاني والرابع .. ) يكون من اليمين لليسار (بعكس جهة المرور الفردي )

لنرجع إلى القائمة نفسها :

post-256536-0-54977100-1404932924.gif

المرور الأول مطابق تماماً للترتيب الفقاعي (يحتاج 5 عمليات استبدال ) وسيعطي :

post-256536-0-73616200-1404933362.gif

والآن إلى المرور الثاني :

نبدأ من اليمين إلى اليسار (سنرمز بالمقارنة التي لا ينتج عنها استبدال بخط , والتي ينتج عنها استبدال بسهمين متعاكسين)

post-256536-0-76694700-1404933591.gif

انتهى المرور الثاني (احتاج 3 عمليات استبدال ) بوضع 1 في البداية , وبذلك تخلصنا من أثر السلحفاة .

 بعد انتهاء المرور الثالث (باستخدام عمليتي استبدال )سيكون لدينا :

post-256536-0-06297500-1404933648.gif

وبانتهاء المرور الرابع (بعملية استبدال واحدة )

post-256536-0-78433000-1404933706.gif

 

كلا الخوارزميتين احتاج 11 عملية استبدال , وكلاهما قام بـ 4 مرات مرور على المصفوفة .

ملاحظة : في المراجع يتم اعتبار المرورين (من اليسار لليمين ثم من اليمين لليسار كمرور واحد للكوكتيل)

فأين هو التحسين ؟

أحياناً تحتاج خوارزمية الكوكتيل عدداً أقل من عمليات المرور مثلاً المصفوفة (2,3,4,5,1) , وفي الحالة الوسطية فإن ترتيب الكوكتيل يكون أسرع بأقل من مرتين تقريباً من الترتيب الفقاعي .

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

كما ذكرت في بداية المقالة , فالهدف هو رؤية جمالية الخوارزمية , لذلك أترككم مع فيديو يوضح عملية ترتيب قائمة

( حيث تم تمثيل قيمة العناصر بارتفاع العمود )

الفيديو يستحق المشاهدة بالفعل

http://www.youtube.com/watch?v=njClLBoEbfI

http://www.youtube.com/watch?v=JiJXnEpDk5o

 

المراجع :

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

http://www.codingunit.com/cocktail-sort-algorithm-or-shaker-sort-algorithm

http://en.algoritmy.net/article/40270/Shaker-sort

 

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

تم تعديل بواسطه مصطفى 36a2
3

شارك هذا الرد


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

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

لاتوجد إجابات على هذا السؤال حتى الآن .

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

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



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

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

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