فرز الخيوط

فرز السلاسل هو خوارزمية فرز تكرارية تُرتّب عناصر القائمة ترتيبًا تصاعديًا. يبلغ تعقيدها الزمني في أسوأ الحالات O ( n² ⁾ ، والذي يحدث عندما تكون قائمة الإدخال مُرتّبة عكسيًا. ^{[ 1 ]} أما في أفضل الحالات، فيبلغ تعقيدها الزمني O ( n ) ، والذي يحدث عندما تكون قائمة الإدخال مُرتّبة بالفعل.

تبدأ الخوارزمية بنقل العنصر الأول من القائمة إلى قائمة فرعية. ^{[ 1 ]} ثم تقارن العنصر الأخير في القائمة الفرعية بكل عنصر لاحق في القائمة الأصلية. ^{[ 1 ]} إذا وُجد عنصر في القائمة الأصلية أكبر من العنصر الأخير في القائمة الفرعية، يُزال هذا العنصر من القائمة الأصلية ويُضاف إلى القائمة الفرعية. [1] تستمر هذه العملية حتى تتم مقارنة العنصر الأخير في القائمة الفرعية بالعناصر المتبقية في القائمة الأصلية. ^{[ 1 ]} بعد ذلك، تُدمج القائمة الفرعية في قائمة جديدة. ^{[ 1 ]} تُكرر هذه العملية وتُدمج جميع القوائم الفرعية حتى تُصبح جميع العناصر مُرتبة. ^{[ 1 ] تُسمى هذه الخوارزمية بفرز الخيوط ، لأنها تُنشئ خيوطًا من العناصر المُرتبة داخل العناصر غير المُرتبة ،} وتُزال هذه الخيوط واحدًا تلو الآخر. ^{[ 1 ] تُستخدم} هذه الخوارزمية أيضًا في خوارزمية J Sort للعناصر التي يقل عددها عن 40 عنصرًا. ^{[ 2 ]}

يستند هذا المثال إلى وصف الخوارزمية الواردة في كتاب الممارسات التي تدعمها تكنولوجيا المعلومات ونماذج الإدارة الناشئة . ^{[ 1 ]}

الخطوة 1: ابدأ بقائمة من الأرقام: {5، 1، 4، 2، 0، 9، 6، 3، 8، 7}.

الخطوة 2: بعد ذلك، انقل العنصر الأول من القائمة إلى قائمة فرعية جديدة: تحتوي القائمة الفرعية على {5}.

الخطوة 3: ثم، قم بالمرور على القائمة الأصلية وقارن كل رقم بـ 5 حتى يكون هناك رقم أكبر من 5.

• 1 < 5، لذلك لا تتم إضافة 1 إلى القائمة الفرعية.
• 4 < 5، لذلك لا تتم إضافة 4 إلى القائمة الفرعية.
• 2 < 5، لذلك لا تتم إضافة 2 إلى القائمة الفرعية.
• 0 < 5، لذلك لا تتم إضافة 0 إلى القائمة الفرعية.
• 9 > 5، لذلك تتم إضافة 9 إلى القائمة الفرعية وإزالتها من القائمة الأصلية.

الخطوة 4: الآن قارن الرقم 9 مع العناصر المتبقية في القائمة الأصلية حتى يصبح هناك رقم أكبر من 9.  

• 6 < 9، لذلك لا تتم إضافة 6 إلى القائمة الفرعية.
• 3 < 9، لذلك لا تتم إضافة 3 إلى القائمة الفرعية.
• 8 < 9، لذلك لا تتم إضافة 8 إلى القائمة الفرعية.
• 7 < 9، لذلك لا تتم إضافة 7 إلى القائمة الفرعية.

الخطوة 5: الآن لم تعد هناك عناصر لمقارنة 9 بها، لذا قم بدمج القائمة الفرعية في قائمة جديدة تسمى قائمة الحلول.

بعد الخطوة 5، تحتوي القائمة الأصلية على {1، 4، 2، 0، 6، 3، 8، 7}.

القائمة الفرعية فارغة، وقائمة الحلول تحتوي على {5، 9}.

الخطوة 6: انقل العنصر الأول من القائمة الأصلية إلى القائمة الفرعية: تحتوي القائمة الفرعية على {1}.

الخطوة 7: قم بالمرور على القائمة الأصلية وقارن كل رقم بالرقم 1 حتى يصبح هناك رقم أكبر من 1.

• 4 > 1، لذلك تتم إضافة 4 إلى القائمة الفرعية ويتم إزالة 4 من القائمة الأصلية.

الخطوة 8: الآن قارن الرقم 4 مع العناصر المتبقية في القائمة الأصلية حتى يصبح هناك رقم أكبر من 4.

• 2 < 4، لذلك لا تتم إضافة 2 إلى القائمة الفرعية.
• 0 < 4، لذلك لا تتم إضافة 0 إلى القائمة الفرعية.
• 6 > 4، لذلك تتم إضافة 6 إلى القائمة الفرعية وإزالتها من القائمة الأصلية.

الخطوة 9: الآن قارن الرقم 6 مع العناصر المتبقية في القائمة الأصلية حتى يصبح هناك رقم أكبر من 6.  

• 3 < 6، لذلك لا تتم إضافة 3 إلى القائمة الفرعية.
• 8 > 6، لذلك تتم إضافة 8 إلى القائمة الفرعية وإزالتها من القائمة الأصلية.

الخطوة 10: الآن قارن الرقم 8 مع العناصر المتبقية في القائمة الأصلية حتى يصبح هناك رقم أكبر من 8.

• 7 < 8، لذلك لا تتم إضافة 7 إلى القائمة الفرعية.

الخطوة 11: بما أنه لم يعد هناك عناصر في القائمة الأصلية للمقارنة مع {8}، يتم دمج القائمة الفرعية مع قائمة الحل. الآن تحتوي القائمة الأصلية على {2، 0، 3، 7}، والقائمة الفرعية فارغة، وقائمة الحل تحتوي على {1، 4، 5، 6، 8، 9}.

الخطوة 12:  انقل العنصر الأول من القائمة الأصلية إلى القائمة الفرعية. تحتوي القائمة الفرعية على {2}.

الخطوة 13: قم بالمرور على القائمة الأصلية وقارن كل رقم بالرقم 2 حتى يكون هناك رقم أكبر من 2.

• 0 < 2، لذلك لا تتم إضافة 0 إلى القائمة الفرعية.
• 3 > 2، لذلك تتم إضافة 3 إلى القائمة الفرعية وإزالتها من القائمة الأصلية.

الخطوة 14: الآن قارن 3 مع العناصر المتبقية في القائمة الأصلية حتى يصبح هناك رقم أكبر من 3.

• 7 > 3، لذلك تتم إضافة 7 إلى القائمة الفرعية وإزالتها من القائمة الأصلية.

الخطوة 15: بما أنه لم يعد هناك عناصر في القائمة الأصلية للمقارنة مع {7}، يتم دمج القائمة الفرعية مع قائمة الحل. تحتوي القائمة الأصلية الآن على {0}، والقائمة الفرعية فارغة، وقائمة الحل تحتوي على {1، 2، 3، 4، 5، 6، 7، 8، 9}.

الخطوة 16:  انقل العنصر الأول من القائمة الأصلية إلى القائمة الفرعية. تحتوي القائمة الفرعية على {0}.

الخطوة 17:  بما أن القائمة الأصلية أصبحت فارغة، يتم دمج القائمة الفرعية مع قائمة الحلول. تحتوي قائمة الحلول الآن على {0، 1، 2، 3، 4، 5، 6، 7، 8، 9}. لم تعد هناك عناصر في القائمة الأصلية، وقد تم ترتيب جميع عناصر قائمة الحلول بنجاح ترتيبًا تصاعديًا.

بما أن خوارزمية فرز الخيوط تتطلب العديد من عمليات الإضافة والحذف، فمن الأفضل استخدام قائمة مرتبطة عند تطبيقها. ^{[ 3 ]} تتطلب القوائم المرتبطة وقتًا ثابتًا لكل من إضافة العناصر وحذفها باستخدام المُكرِّرات. يرتبط وقت المرور عبر القائمة المرتبطة ارتباطًا مباشرًا بحجم القائمة المدخلة. ^{[ 4 ]} تم تنفيذ التطبيق التالي بلغة Java 8، وهو مبني على وصف الخوارزمية الوارد في كتاب " الممارسات المُمكّنة بتقنية المعلومات ونماذج الإدارة الناشئة" . ^{[ 1 ]}

حزمة فرز الخيوط ؛استيراد java.util.* ;public class strandSort {static LinkedList <Integer> solList = new LinkedList <Integer> ( ) ;​​static int k = 0 ;/** هذه طريقة فرز سلاسل متكررة. تأخذ قائمة مرتبطة من * الأعداد الصحيحة كمعامل لها. تتحقق أولاً من الحالة الأساسية لمعرفة ما إذا كانت * القائمة المرتبطة فارغة. ثم ينتقل إلى خوارزمية فرز الخيوط حتى * القائمة المرتبطة فارغة. * * @param origList: * قائمة مرتبطة من الأعداد الصحيحة */public static void strandSortIterative ( LinkedList < Integer > origList ) {// الحالة الأساسيةإذا كانت القائمة الأصلية فارغة {​يعود ؛}آخر {// أنشئ القائمة الفرعية وأضف العنصر الأول منها// القائمة المرتبطة الأصلية بالقائمة الفرعية.// ثم قم بإزالة العنصر الأول من القائمة الأصلية.LinkedList <Integer> subList = new LinkedList <Integer> ( ) ;​​subList.add ( origList.getFirst ( ) ) ;​origList.removeFirst ( ) ;// تكرار المرور على القائمة الأصلية، والتحقق مما إذا كانت أي عناصر// أكبر من العنصر الموجود في القائمة الفرعية.int index = 0 ;for ( int j = 0 ; j < origList.size ( ) ; j ++ ) {إذا كان ( العنصر j في القائمة الأصلية > العنصر index في القائمة الفرعية ) {subList.add ( origList.get ( j ) ) ;​​origList.remove ( j ) ;​j = j - 1 ;index = index + 1 ;}}// دمج القائمة الفرعية في قائمة الحلول.// هناك حالتان لهذه الخطوة/// الحالة 1: الاستدعاء التكراري الأول، أضف جميع العناصر إلى// قائمة الحلول بالترتيب التسلسليإذا كان ( k == 0 ) {for ( int i = 0 ; i < subList.size ( ) ; i ++ ) {solList.add ( subList.get ( i ) ) ;​​k = k + 1 ;}}// الحالة الثانية: بعد الاستدعاء التكراري الأول،// دمج القائمة الفرعية مع قائمة الحلول.// يتم ذلك عن طريق مقارنة أكبر عنصر في القائمة الفرعية (وهو دائمًا العنصر الأخير)// مع العنصر الأول في قائمة الحلول.آخر {int subEnd = subList.size ( ) - 1 ;​int solStart = 0 ;بينما ( ! قائمة_الفرعية.فارغة ( ) ) {إذا كان ( subEnd.get ( subList ) > solStart.get ( solList ) ) {​​solStart ++ ;} آخر {solList.add ( solStart , subList.get ( subEnd ) ) ;​​subList.remove ( subEnd ) ;​subEnd -- ;solStart = 0 ;}}}strandSortIterative ( origList );}}public static void main ( String [] args ) {// إنشاء قائمة مرتبطة جديدة من الأعداد الصحيحةLinkedList <Integer> origList = new LinkedList <Integer> ( ) ;​​// أضف الأعداد الصحيحة التالية إلى القائمة المرتبطة: {5، 1، 4، 2، 0، 9، 6، 3، 8، 7}origList.add ( 5 ) ;​origList.add ( 1 ) ;​origList.add ( 4 ) ;​origList.add ( 2 ) ;​origList.add ( 0 ) ;​origList.add ( 9 ) ;​origList.add ( 6 ) ;​origList.add ( 3 ) ;​origList.add ( 8 ) ;​origList.add ( 7 ) ;​strandSortIterative ( origList );// اطبع قائمة الحلولfor ( int i = 0 ; i < solList.size ( ) ; i ++ ) {System.out.println ( solList.get ( i ) ) ;​​​​}}}