نوع من السباغيتي

خوارزمية فرز السباغيتي هي خوارزمية تناظرية خطية الزمن لفرز سلسلة من العناصر، قدمها أ . ك. ديودني في عموده بمجلة ساينتفك أمريكان . ^{[ 1} ] ^{[ 2 ] [ 3 ]} تقوم هذه الخوارزمية بفرز سلسلة من العناصر بكفاءة عالية، مستهلكةً مساحة تخزين ثابتة مقدارها O ( n ). وتتطلب معالجًا متوازيًا، يُفترض أن يكون قادرًا على إيجاد القيمة القصوى لسلسلة من العناصر في زمن ^مقداره O ( 1 ).

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

1. لكل عدد x في القائمة، احصل على قضيب طوله x . (إحدى الطرق العملية لاختيار الوحدة هي أن يكون أكبر عدد m في القائمة مساويًا لقضيب كامل من السباغيتي. في هذه الحالة، يساوي القضيب الكامل m وحدة من السباغيتي. للحصول على قضيب طوله x ، اكسر قضيبًا إلى نصفين بحيث يكون طول أحد النصفين x وحدة؛ وتخلص من النصف الآخر.)
2. بعد جمع جميع قضبان السباغيتي، أمسكها برفق في قبضتك وأنزلها على الطاولة بحيث تستقر جميعها بشكل عمودي. الآن، لكل قضيب، أنزل يدك الأخرى من الأعلى حتى تلامس قضيبًا - هذا القضيب هو الأطول بوضوح. أزل هذا القضيب وأدخله في بداية قائمة الإخراج (الفارغة في البداية) (أو ضعه في آخر خانة غير مستخدمة في مصفوفة الإخراج). كرر هذه العملية حتى إزالة جميع القضبان.

يستغرق تحضير n من أعواد السباغيتي وقتًا خطيًا. أما إنزال الأعواد على الطاولة فيستغرق وقتًا ثابتًا، O ( 1 ). هذا ممكن لأن اليد وأعواد السباغيتي والطاولة تعمل كوحدة حاسوبية متوازية بالكامل . بالتالي، يوجد n من الأعواد لإزالتها، لذا، بافتراض أن كل عملية ملامسة وإزالة تستغرق وقتًا ثابتًا، فإن التعقيد الزمني للخوارزمية في أسوأ الحالات هو O ( n ).

• الصفحة الرئيسية لـ AK Dewdney
• تطبيقات نموذج الفرز المادي، مركز بول للأبحاث في المعلوماتية
• الحوسبة الكلاسيكية/الكمومية، معهد IFF، مؤرشف بتاريخ 19 يوليو 2011 على موقع Wayback Machine