فرز الاختيار Java البرنامج مع المثال

كيف يعمل فرز التحديد؟

ينفذ "فرز التحديد" خوارزمية فرز بسيطة كما يلي:

• تبحث الخوارزمية بشكل متكرر عن العنصر الأدنى.
• قم بتبديل العنصر الحالي بعنصر له أقل قيمة
• مع كل تكرار/تمرير لفرز التحديد، يتم تبديل العناصر.

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

نظرًا لأن عملية تبديل واحدة فقط تحدث في كل دورة، يتم ترتيب مصفوفة من n عنصرًا بعد n-1 عملية تبديل على الأكثر. هذه الخاصية هي ما يميز هذا الروتين عن الروتينات الأخرى للمبتدئين. Java خوارزميات الفرز، التي تنقل البيانات بشكل متكرر.

استخدم tracيتبع المثال أدناه مصفوفة العينة {860، 8، 200، 9} تمامًا كما يطبعها البرنامج في القسم التالي أثناء وقت التشغيل.

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

Java برنامج لتنفيذ فرز التحديد

يُسمى الصنف أدناه SelectionSortAlgo ويقع ضمن الحزمة com.guru99. تُعرّف الدالة main() مصفوفة العينة، ثم تطبعها، وتُمررها إلى الدالة selection() لفرزها، ثم تطبعها مرة أخرى. تقوم الدالة المساعدة printArray() بكتابة جميع العناصر في سطر واحد، وهو ما يُنتج سجل المرور والتجاوز المقروء.

داخل الدالة selection()، تحدد الحلقة الخارجية الحدود بين المناطق المصنفة وغير المصنفة، ويحتفظ المتغير index بموضع أصغر قيمة تم رؤيتها حتى الآن، وتقوم عمليات التعيين الثلاثة في نهاية كل تمريرة بتنفيذ عملية التبديل.

package com.guru99;
 
public class SelectionSortAlgo {
 
	public static void main(String a[])
	{  
		int[] myArray = {860,8,200,9}; 
		
		System.out.println("------Before Selection Sort-----");
 
		printArray(myArray);
 
 
		selection(myArray);//sorting array using selection sort  
 
		System.out.println("-----After Selection Sort-----");  
 
		printArray(myArray); 
	} 
	
		public static void selection(int[] array)
	{  
		for (int i = 0; i < array.length - 1; i++)  
		{  System.out.println("Sort Pass Number "+(i+1));
			int index = i;  
			for (int j = i + 1; j < array.length; j++)
			{   
			    System.out.println("Comparing "+ array[index]  + " and " + array[j]);  
				if (array[j] < array[index]){ 
				System.out.println(array[index]  + " is greater than " + array[j] );
					index = j;
				
				
				}  
			}  
 
			int smallerNumber = array[index];   
			array[index] = array[i];  
			array[i] = smallerNumber;  
			System.out.println("Swapping Elements: New Array After Swap");
			printArray(array);
		}  
	}  
	static void printArray(int[] array){
	    
	    for(int i=0; i < array.length; i++)
		{  
			System.out.print(array[i] + " ");  
		} 
	    System.out.println();
	    
	}
 
}

الإخراج:

يؤدي تجميع وتشغيل الفئة إلى إنتاج سجل وحدة التحكم أدناه، مع كتلة واحدة من الإخراج لكل تمريرة.

------Before Selection Sort-----
860 8 200 9 
Sort Pass Number 1
Comparing 860 and 8
860 is greater than 8
Comparing 8 and 200
Comparing 8 and 9
Swapping Elements: New Array After Swap
8 860 200 9 
Sort Pass Number 2
Comparing 860 and 200
860 is greater than 200
Comparing 200 and 9
200 is greater than 9
Swapping Elements: New Array After Swap
8 9 200 860 
Sort Pass Number 3
Comparing 200 and 860
Swapping Elements: New Array After Swap
8 9 200 860 
-----After Selection Sort-----
8 9 200 860

هناك مشكلتان تواجهان المبتدئين عند تشغيل هذا المثال لأول مرة. لأن الملف يُعلن package com.guru99;يجب أن يكون المصدر موجودًا في مكان مطابق com/guru99 وإلا سيُبلغ المُصرّف عن عدم تطابق اسم الحزمة أو الفئة. يجب حينها تشغيل الفئة باستخدام اسمها الكامل. java com.guru99.SelectionSortAlgoلأنه واضح java SelectionSortAlgo يُثير خطأ NoClassDefFoundError.

تُعدّ حدود الحلقة من بين الفخاخ الشائعة الأخرى. تتوقف الحلقة الخارجية عند array.length - 1 وتبدأ الحلقة الداخلية عند i + 1يؤدي تغيير أي من الحدود إلى تمريرة فارغة إضافية أو إلى استثناء ArrayIndexOutOfBoundsException.

تعقيد الوقت والمساحة لفرز الاختيار

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

تترتب على هذا الصف الموحد من الأرقام ثلاث نتائج:

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

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

مزايا وعيوب فرز الاختيار

إن فهم أين تفيد الخوارزمية وأين تضر يجعل من السهل تحديد متى يكون اللجوء إليها أمراً معقولاً.

المزايا

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

عيوب

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

باختصار، اختر فرز التحديد عندما تكون المصفوفة صغيرة وكل عملية كتابة مكلفة، وتجنبه عندما تكون مجموعة البيانات كبيرة أو قريبة بالفعل من الترتيب.

فرز التحديد مقابل Bubblفرز e مقابل فرز الإدراج

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

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

الأسئلة الشائعة