خوارزمية الترتيب "فطائر البان-كيك"

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

اعتدنا أثناء الترتيب على البحث عن الخوارزمية ذات عدد المقارنات الأقل less comparisons , او على الخوارزمية ذات عدد الاستبدالات الأقل less swaps بين العناصر ,

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

إن سبب تعدد خوارزميات الترتيب هو اختلاف الخوارزمية المثالية لبنية المعطيات التي لدينا , وهذا مبدأ هام جداً في دراسة الخوارزميات , فقد تكون عملية الاستبدال swap مكلفة في بنية ما , بينما تكون (O(1

في بنية أخرى , لذلك علينا العثور على خوارزمية تشمل العمليات الأقل كلفة حسب البنية المعطاة

لنرجع إلى فطائرنا ..

إن عملية استبدال فطيرتين مكلفة !

فهي تسبب اتساخ اليد بالـ"sauce" الموجود عليها , كما ان استخدام الملاعق لاستبدال الفطيرتين ... لك أن تتخيل ذلك , رفع ما فوق الفطيرة السفلى ثم رفع ما فوق الفطيرة العليا ثم التبديل ثم انزال الكدسات المرفوعة ... عملية مكلفة بكل ما تعني الكلمة

ولكن ماذا عن عملية القلب flip  ؟

يمكننا وضع ملعقة بداخل الكدسة ثم قلب كل ما فوق هذه الكدسة , الشكل التالي يوضح كدسة فطائر قبل وبعد القلب

واضح ان العملية بسيطة جداً , وغير مكلفة , ولذلك تم عمل خوارزمية الترتيب Flip Sort او ما يسمى Pancake Sort التي تعتمد على هذه الـ operator غير المكلفة , الـ FLIP operator

في هذه الخورازمية يمكننا فقط القيام بعملية الـ flip هذه , ولترتيب القائمة التي لدينا علينا اتباع الخطوات التالية :

إذا كان لدينا n عنصر , فعلينا تكرار ما يلي n  مرة ولنضع عدادا i يبدأ من 1 :

1- العثور على العنصر الأكبر خلال المجال من i إلى n

2- وضع الملعقة على موضع العنصر الأكبر وقلب الكدسة التي فوقه .

3- وضع الملعقة في الموضع i وقلب الكدسة التي فوقه

4- زيادة العداد i والتوقف إذا كان i==n

للتوضيح : عملية قلب الكدسة هي عملية flip للعناصر من موضع القلب إلى القمة (أي إلى n )

هذا المقطع يوضح هذه الخوارزمية

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

وبذلك يمكننا تحسينها إلى :

إذا كان لدينا n عنصر , فعلينا تكرار ما يلي n  مرة ولنضع عدادا i يبدأ من 1 :

1- العثور على العنصر الأكبر خلال المجال من i إلى n

2-

   2.1- إذا كان العنصر الأكبر في الموضع i نتركه كما هو

   2.2- إذا كان العنصر الأكبر في الموضع n نقوم بوضع الملعقة في الموضع i ونقلب الكدسة رأساً على عقب

   2.3- إذا لم يكن العنصر الأكبر هو العنصر i  ولا  العنصر n  فعلينا وضع المعقة في موضع العنصر الأكبر وليكن j وقلب الكدسة التي فوقها عندها سيصبح في الموضع n ثم ننفذ 2.2

3-نزيد قيمة i (عند هذه النقطة يكون كل العناصر من الأسفل وحتى i مرتبة ) ونتوقف إذا كان i==n

إذا اعتبرنا عملية الـ flip هي العملية الوحيدة فإن أكبر عدد من الـ flip تحتاجه الكدسة حتى يتم ترتيبها هو 2*n (مرتان لكل موضع )

ولا ننسى أننا بحاجة إلى العثور على العنصر الأكبر في الكدسة , مما يعني (O(n للبحث كل مرة , وبذلك يكون التعقيد الزمني للخوارزمية لو كانت عملية القلب (O(1 هي (O(n²

ولكن عملية القلب حوسبياً هي عملية (O(n وبالتالي تعقيد الخوارزمية حسابياً هو (O(n³ إذا هي فعالة في الحياة العملية أكثر منها في الحاسوب .

كانت هذه لمحة موجزة و سريعة عن هذه الخوارزمية , أرجو أن تكون مفيدة

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

المصادر :

Wikipedia

GeeksForGeeks