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

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

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

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

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

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

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

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

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

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

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

فتصبح

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

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

وهكذا سينتج لدينا بعد كل مقارنة واستبدال التسلسل التالي

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

كلا الخوارزميتين احتاج 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

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