فرز التحديد

في علوم الحاسوب ، يُعدّ فرز التحديد خوارزمية فرز مقارنة موضعية . يتميز بتعقيد زمني قدره O ( n² ⁾ ، مما يجعله غير فعال مع القوائم الكبيرة، وعادةً ما يكون أداؤه أسوأ من فرز الإدراج المماثل . يُعرف فرز التحديد ببساطته، ويتمتع بمزايا أداء على الخوارزميات الأكثر تعقيدًا في بعض الحالات، لا سيما عندما تكون الذاكرة الإضافية محدودة.

تقسم الخوارزمية قائمة الإدخال إلى جزأين: قائمة فرعية مرتبة من العناصر، تُبنى من اليسار إلى اليمين في بداية القائمة (يسارها)، وقائمة فرعية أخرى من العناصر المتبقية غير المرتبة التي تشغل باقي القائمة. في البداية، تكون القائمة الفرعية المرتبة فارغة، بينما تمثل القائمة الفرعية غير المرتبة قائمة الإدخال بأكملها. تبدأ الخوارزمية بالبحث عن أصغر عنصر (أو أكبر عنصر، حسب ترتيب الفرز) في القائمة الفرعية غير المرتبة، ثم تستبدله بالعنصر الموجود في أقصى اليسار من القائمة غير المرتبة (ليصبح مرتبًا)، ثم تحرك حدود القائمة الفرعية عنصرًا واحدًا إلى اليمين.

إن كفاءة الوقت لفرز الاختيار هي تربيعية، لذلك هناك عدد من تقنيات الفرز التي تتمتع بتعقيد زمني أفضل من فرز الاختيار.

فيما يلي مثال على خوارزمية الفرز هذه التي تقوم بفرز خمسة عناصر:

(لم يظهر أي تغيير في هذين السطرين الأخيرين لأن الرقمين الأخيرين كانا بالترتيب بالفعل.)

يمكن استخدام فرز التحديد أيضًا على هياكل القوائم التي تجعل الإضافة والحذف فعالين، مثل القوائم المتصلة . في هذه الحالة، من الشائع حذف العنصر الأصغر من بقية القائمة، ثم إدراجه في نهاية القيم التي تم فرزها حتى الآن. على سبيل المثال:

arr[] = 64 25 12 22 11 // إيجاد أصغر عنصر في arr[0...4] // وضعها في البداية <11> 25 12 22 64 // إيجاد أصغر عنصر في arr[1...4] // ضعها في بداية arr[1...4] 11 <12> 25 22 64 // إيجاد أصغر عنصر في arr[2...4] // وضعها في بداية arr[2...4] 11 12 <22> 25 64 // إيجاد أصغر عنصر في arr[3...4] // ضعها في بداية arr[3...4] 11 12 22 <25> 64 

فيما يلي تطبيق مكتوب بلغة C.

void swap ( int * x , int * y ) { int temp = * x ; * x = * y ; * y = temp ; }// دالة فرز التحديد void selectionSort ( int a [], int length ) { // المرور على المصفوفة بأكملها (باستثناء العنصر الأخير) for ( int i = 0 ; i < length - 1 ; ++ i ) { int jMin = i ; // افتراض أن الموضع الحالي هو الحد الأدنى// البحث عن أصغر عنصر في الجزء غير المرتب for ( int j = i + 1 ; j < length ; ++ j ) { if ( a [ j ] < a [ jMin ]) { // تم العثور على عنصر أصغر jMin = j ; // تحديث فهرس العنصر الأصغر } }// قم بالتبديل فقط إذا تم العثور على عنصر أصغر إذا ( jMin != i ) { swap ( &a a [ i ], &a a [ jMin ]); } } }

لا يُعدّ تحليل خوارزمية فرز التحديد صعبًا مقارنةً بخوارزميات الفرز الأخرى، إذ لا تعتمد أيٌّ من حلقاتها على البيانات الموجودة في المصفوفة. ويتطلب اختيار العنصر الأدنى مسحًا.${\displaystyle n}$العناصر (أخذ${\displaystyle n-1}$ثم يتم استبداله بالموضع الأول. يتطلب إيجاد العنصر الأدنى التالي مسح العناصر المتبقية${\displaystyle n-1}$العناصر (أخذ${\displaystyle n-2}$المقارنات) وهكذا. لذلك، فإن العدد الإجمالي للمقارنات هو

${\displaystyle (n-1)+(n-2)+\dots +1=\sum _{i=1}^{n-1}i}$

باستخدام المتتابعة الحسابية ،

${\displaystyle \sum _{i=1}^{n-1}i={\frac {(n-1)+1}{2}}(n-1)={\frac {1}{2}}n(n-1)={\frac {1}{2}}(n^{2}-n)}$

وهو أمر معقد${\displaystyle O(n^{2})}$من حيث عدد المقارنات.

من بين خوارزميات الفرز التربيعي (خوارزميات الفرز ذات الحالة المتوسطة البسيطة Θ( n² ) )، يتفوق فرز الاختيار دائمًا تقريبًا على فرز الفقاعات وفرز الأقزام . يشبه فرز الإدراج إلى حد كبير فرز الاختيار ^، حيث أنه بعد التكرار رقم k ، يكون أول${\displaystyle k}$تكون عناصر المصفوفة مرتبة ترتيبًا تصاعديًا. وتكمن ميزة خوارزمية فرز الإدراج في أنها تفحص فقط العدد اللازم من العناصر لوضعها في المصفوفة المطلوبة.${\displaystyle k+1}$بينما يجب على فرز التحديد مسح جميع العناصر المتبقية للعثور على العنصر الأول.${\displaystyle k+1}$العنصر الأول.

تُظهر حسابات بسيطة أن فرز الإدراج يُجري عادةً نصف عدد المقارنات التي يُجريها فرز التحديد، مع أنه قد يُجري نفس العدد أو عددًا أقل بكثير اعتمادًا على ترتيب المصفوفة قبل الفرز. يُمكن اعتبار هذا ميزةً لبعض التطبيقات الآنية ، حيث يُؤدي فرز التحديد نفس الأداء بغض النظر عن ترتيب المصفوفة، بينما قد يختلف وقت تشغيل فرز الإدراج اختلافًا كبيرًا. مع ذلك، غالبًا ما تكون هذه ميزةً لفرز الإدراج، إذ يعمل بكفاءة أعلى بكثير إذا كانت المصفوفة مُرتبةً بالفعل أو "شبه مُرتبة".

بينما يُفضّل فرز التحديد على فرز الإدراج من حيث عدد عمليات الكتابة (${\displaystyle n-1}$المقايضات مقابل ما يصل إلى${\displaystyle n(n-1)/2}$(مع عمليات تبديل، حيث تتضمن كل عملية تبديل عمليتي كتابة)، يُعادل هذا ضعف الحد الأدنى النظري الذي تحققه خوارزمية فرز الدورة ، والتي تُجري على الأكثر n عملية كتابة. قد يكون هذا الأمر بالغ الأهمية إذا كانت عمليات الكتابة أكثر تكلفة بكثير من عمليات القراءة، كما هو الحال مع ذاكرة EEPROM أو ذاكرة الفلاش ، حيث تُقلل كل عملية كتابة من عمر الذاكرة.

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

وأخيرًا، يتفوق فرز التحديد بشكل كبير على المصفوفات الأكبر حجمًا بواسطة${\displaystyle \Theta (n\log n)}$تُعدّ خوارزميات فرق تسد، مثل فرز الدمج ، من بين الخوارزميات التي تُحسّن الأداء . مع ذلك، فإنّ فرز الإدراج أو فرز التحديد أسرع عادةً للمصفوفات الصغيرة (أي أقل من 10-20 عنصرًا). ومن التحسينات المفيدة عمليًا للخوارزميات التكرارية التحوّل إلى فرز الإدراج أو فرز التحديد للقوائم الفرعية "الصغيرة بما يكفي".

وُصفت خوارزمية فرز الكومة بأنها "ليست سوى تطبيق لخوارزمية فرز الاختيار باستخدام بنية البيانات المناسبة ". ^{[ 1 ]} وهي تُحسّن الخوارزمية الأساسية بشكل كبير من خلال استخدام بنية بيانات الكومة الضمنية للعثور على كل عنصر أدنى وإزالته.${\displaystyle \Theta (\log n)}$الوقت، بدلاً من فرز الاختيار العادي${\displaystyle \Theta (n)}$حلقة داخلية، مما يقلل من إجمالي وقت التشغيل إلى${\displaystyle \Theta (n\log n)}$.

يُحدد نوع ثنائي الاتجاه من فرز الاختيار (يُسمى فرز الاختيار المزدوج أو فرز الكوكتيل لتشابهه مع فرز خلط الكوكتيل ) القيمتين الدنيا والقصوى في القائمة في كل دورة. يتطلب هذا النوع ثلاث مقارنات لكل عنصرين (حيث تتم مقارنة عنصرين، ثم تتم مقارنة العنصر الأكبر بالقيمة القصوى والعنصر الأصغر بالقيمة الدنيا) بدلاً من مقارنة واحدة لكل عنصر في فرز الاختيار العادي، ولكنه يتطلب نصف عدد الدورات فقط، أي توفير صافٍ بنسبة 25%.

يمكن تطبيق فرز التحديد كفرز مستقر إذا تم، بدلاً من التبديل في الخطوة الثانية، إدخال القيمة الدنيا في الموضع الأول وإزاحة القيم الوسيطة للأعلى. ومع ذلك، يتطلب هذا التعديل إما بنية بيانات تدعم عمليات الإدخال أو الحذف بكفاءة، مثل القائمة المرتبطة، أو أنه يؤدي إلى أداء${\displaystyle \Theta (n^{2})}$يكتب.

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

بينغو ( المصفوفة أ ){ يقوم هذا الإجراء بالفرز بترتيب تصاعدي عن طريق  نقل العناصر ذات القيم القصوى بشكل متكرر إلى النهاية. } ابدأ last := length ( A ) - 1 ;{ كُتبت الدورة الأولى لتكون مشابهة جدًا  للدورات اللاحقة، ولكن بدون تبديل. } nextMax := A [ last ] ; for i := last - 1 downto 0 do if A [ i ] > nextMax then nextMax := A [ i ] ; while ( last > 0 ) and ( A [ last ] = nextMax ) do last := last - 1 ;بينما last > 0، ابدأ { تبحث كل حلقة رئيسية عن nextMax الجديد مع  تبديل العناصر التي تساوي prevMax في مكانها. } prevMax := nextMax ; nextMax := A [ last ] ; for i := last - 1 downto 0 do if A [ i ] > nextMax then if A [ i ] <> prevMax then nextMax := A [ i ] ; else begin swap ( A [ i ] , A [ last ]) ; last := last - 1 ; end while ( last > 0 ) and ( A [ last ] = nextMax ) do last := last - 1 ; end ; end ;

وبالتالي، إذا كان هناك في المتوسط ​​أكثر من عنصرين لهما نفس القيمة، فمن المتوقع أن يكون فرز البنغو أسرع لأنه ينفذ الحلقة الداخلية مرات أقل من فرز التحديد.

• خوارزمية الاختيار

• خوارزميات الفرز المتحركة: فرز التحديد في أرشيف الإنترنت (تمت أرشفته في 7 مارس 2015) - عرض توضيحي رسومي