การเลือกเรียงลำดับ Java โปรแกรมพร้อมตัวอย่าง

⚡ สรุปอย่างชาญฉลาด

การเรียงลำดับแบบเลือกใน Java ฟังก์ชันนี้จะสแกนส่วนที่ยังไม่ได้เรียงลำดับของอาร์เรย์ซ้ำๆ ค้นหาค่าที่เล็กที่สุดที่เหลืออยู่ และสลับค่าดังกล่าวไปยังตำแหน่งที่ต้องการ โดยจะดำเนินการให้เสร็จสิ้นด้วยการสลับตำแหน่งอย่างมากที่สุด n-1 ครั้ง โดยไม่คำนึงถึงลำดับของข้อมูลขาเข้า

  • 🔘 ความหมาย: อัลกอริทึมการเรียงลำดับแบบเลือก (Selection sort) จะแบ่งอาร์เรย์ออกเป็นส่วนที่เรียงลำดับแล้วและส่วนที่ยังไม่ได้เรียงลำดับในแต่ละรอบการประมวลผล
  • ☑️ กระบวนการ: แต่ละรอบจะค้นหาองค์ประกอบที่ต่ำที่สุดในบริเวณที่ยังไม่ได้เรียงลำดับ และสลับตำแหน่งไปข้างหน้า
  • ✅ โปรแกรม: การขอ Java ตัวอย่างนี้เรียงลำดับ {860, 8, 200, 9} และพิมพ์ผลการเปรียบเทียบและการสลับแต่ละครั้ง
  • 🧪 ซับซ้อน: กรณีที่ดีที่สุด กรณีเฉลี่ย และกรณีที่แย่ที่สุด ล้วนใช้เวลา O(n²) เนื่องจากจำนวนการเปรียบเทียบไม่ลดลงเลย
  • 🛠️ หน่วยความจำ: การสลับเปลี่ยนเกิดขึ้นภายในอาร์เรย์เดิม ดังนั้นพื้นที่เสริมจึงยังคงอยู่ที่ O(1)
  • 📊 พฤติกรรม: เวอร์ชันคลาสสิกนั้นไม่เสถียร แต่กลับมีการเขียนข้อมูลน้อยที่สุดเมื่อเทียบกับการเรียงลำดับแบบกำลังสองอื่นๆ

การเลือกเรียงลำดับ Java โปรแกรมพร้อมตัวอย่าง

การเรียงลำดับการเลือกทำงานอย่างไร

Selection Sort ใช้อัลกอริธึมการเรียงลำดับอย่างง่ายดังต่อไปนี้:

  • อัลกอริทึมจะค้นหาองค์ประกอบที่ต่ำที่สุดซ้ำๆ
  • สลับองค์ประกอบปัจจุบันกับองค์ประกอบที่มีค่าต่ำสุด
  • ทุกครั้งที่เรียงลำดับการเลือกซ้ำ/ผ่าน องค์ประกอบจะถูกสลับ

ดังนั้น ทุกครั้งที่ผ่านเข้าไป จะเป็นการปฏิบัติต่อ แถว โดยแบ่งออกเป็นสองส่วน: ส่วนที่เรียงลำดับแล้วซึ่งขยายจากด้านซ้าย และส่วนที่ยังไม่ได้เรียงลำดับซึ่งหดตัวลงทางด้านขวา อัลกอริทึมจะเดินไปตามส่วนที่ยังไม่ได้เรียงลำดับ จดจำดัชนีของค่าที่เล็กที่สุดที่พบ และแลกเปลี่ยนค่านั้นกับตำแหน่งแรกที่ยังไม่ได้เรียงลำดับ

เนื่องจากมีการสลับตำแหน่งเพียงครั้งเดียวต่อรอบ ดังนั้นอาร์เรย์ที่มี n องค์ประกอบจึงเรียงลำดับตามการสลับตำแหน่งอย่างมากที่สุด n-1 ครั้ง คุณสมบัตินี้เองที่ทำให้รูทีนนี้แตกต่างจากรูทีนระดับเริ่มต้นอื่นๆ Java อัลกอริทึมการเรียงลำดับ ซึ่งมีการเคลื่อนย้ายข้อมูลบ่อยกว่ามาก

การขอ tracตัวอย่างอาร์เรย์ด้านล่าง {860, 8, 200, 9} เป็นไปตามที่โปรแกรมในส่วนถัดไปพิมพ์ออกมาขณะรันโปรแกรมทุกประการ

ส่ง การเปรียบเทียบที่พิมพ์ ค่าที่น้อยที่สุดที่พบ อาร์เรย์หลังการสลับ
เริ่มต้น - - 860 8 200 9
1 860 และ 8, 8 และ 200, 8 และ 9 8 8 860 200 9
2 860 และ 200, 200 และ 9 9 8 9 200 860
3 และ 200 860 200 8 9 200 860

มีรายละเอียดสองอย่างในเรื่องนั้น tracมีบางประเด็นที่ควรหยุดพิจารณา ประการแรก การประมวลผลรอบที่ 3 ยังคงรายงานการสลับตำแหน่งแม้ว่าลำดับจะไม่เปลี่ยนแปลง เนื่องจากค่าที่เล็กที่สุดที่เหลืออยู่จะอยู่ที่ดัชนีปัจจุบันอยู่แล้ว และโปรแกรมจะสลับองค์ประกอบนั้นกับตัวเอง ประการที่สอง จำนวนการเปรียบเทียบลดลงหนึ่งครั้งในแต่ละรอบ (สามครั้ง จากนั้นสองครั้ง จากนั้นหนึ่งครั้ง) ซึ่งเป็นรูปแบบที่อยู่เบื้องหลังตัวเลขความซับซ้อนที่ปรากฏอยู่ด้านล่างของหน้านี้

Java โปรแกรมที่จะดำเนินการ Selection Sort

คลาสต่อไปนี้มีชื่อว่า 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();
	    
	}
 
}

Output:

การคอมไพล์และรันคลาสจะสร้างเอาต์พุตในคอนโซลดังที่แสดงด้านล่าง โดยมีเอาต์พุตหนึ่งบล็อกต่อรอบ

------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

ความซับซ้อนด้านเวลาและพื้นที่ของการเรียงลำดับแบบเลือก (Selection Sort)

ลูปภายในของโปรแกรมจะทำงานจนถึงจุดสิ้นสุดของอาร์เรย์เสมอ ดังนั้นอัลกอริทึมจึงทำการเปรียบเทียบจำนวนเท่ากันไม่ว่าข้อมูลจะมีลักษณะอย่างไร สำหรับอาร์เรย์ที่มี n องค์ประกอบ จำนวนการเปรียบเทียบทั้งหมดคือ n(n-1)/2 ซึ่งสำหรับตัวอย่างที่มีสี่องค์ประกอบจะเท่ากับหก และผลลัพธ์ข้างต้นก็แสดงบรรทัดการเปรียบเทียบหกบรรทัดอย่างแม่นยำ

กรณี เปรียบเทียบ แลกเปลี่ยน ความซับซ้อนของเวลา พื้นที่เสริม
ดีที่สุด (อาร์เรย์เรียงลำดับแล้ว) n(n-1)/2 n-1 โอ(n²) O (1)
ค่าเฉลี่ย (เรียงลำดับแบบสุ่ม) n(n-1)/2 n-1 โอ(n²) O (1)
แย่ที่สุด (เรียงลำดับจากมากไปน้อย) n(n-1)/2 n-1 โอ(n²) O (1)

จากตัวเลขที่เรียงกันเป็นแถวอย่างเป็นระเบียบนั้น มีผลตามมาสามประการดังนี้:

  • การเรียงลำดับแบบเลือก (Selection sort) ไม่สามารถปรับเปลี่ยนได้ ต้นทุนในการป้อนข้อมูลที่เรียงลำดับแล้วเท่ากับต้นทุนในการป้อนข้อมูลที่กลับด้าน ดังนั้นจึงไม่มีทางลัดออกก่อนกำหนดแบบใดๆ เรียงฟอง ข้อเสนอ
  • จำนวนการสลับตำแหน่งเป็นจุดเด่นของอัลกอริทึมนี้ โดยมีการสลับตำแหน่งอย่างมากที่สุดเพียง n-1 ครั้ง ซึ่งน้อยกว่าจำนวนการเคลื่อนย้ายแบบกำลังสองที่อัลกอริทึมการเรียงลำดับแบบง่ายอื่นๆ สามารถทำได้มาก
  • การใช้หน่วยความจำคงที่ มีเพียงตัวนับลูปและตัวแปรชั่วคราวสองตัวคือ index และ smallerNumber เท่านั้นที่จำเป็น ดังนั้นพื้นที่เสริมจึงเป็น O(1) และการเรียงลำดับเกิดขึ้นในตำแหน่งเดิม

การเติบโตแบบกำลังสองเป็นข้อจำกัดในทางปฏิบัติ การเพิ่มขนาดของอาร์เรย์เป็นสองเท่าจะทำให้งานเปรียบเทียบเพิ่มขึ้นเป็นสี่เท่าโดยประมาณ ดังนั้นการเรียงลำดับแบบเลือกจึงเหมาะสำหรับการสอน อาร์เรย์ขนาดเล็ก และโค้ดฝังตัว มากกว่าชุดข้อมูลสำหรับการใช้งานจริง ซึ่งอัลกอริทึม O(n log n) เป็นตัวเลือกที่เหมาะสมกว่า

ข้อดีและข้อเสียของการเรียงลำดับแบบเลือก (Selection Sort)

การเข้าใจว่าอัลกอริทึมมีประโยชน์ในด้านใดและมีข้อเสียในด้านใด จะช่วยให้ตัดสินใจได้ง่ายขึ้นว่าเมื่อใดจึงเหมาะสมที่จะใช้อัลกอริทึมนั้น

ข้อดี

  • หลักการนั้นสั้นและอ่านง่าย จึงนิยมใช้เป็นแบบฝึกหัดการเรียงลำดับเบื้องต้นควบคู่ไปกับแบบฝึกหัดอื่นๆ การเรียงลำดับการแทรก.
  • มันทำการเรียงลำดับในตำแหน่งเดิม ดังนั้นจึงไม่จำเป็นต้องจัดสรรอาร์เรย์ตัวที่สอง และการใช้หน่วยความจำจะไม่เพิ่มขึ้นตามปริมาณข้อมูลที่ป้อนเข้ามา
  • มันทำการเขียนข้อมูลลงในอาร์เรย์อย่างมากที่สุด n-1 ครั้ง ซึ่งมีความสำคัญในระบบจัดเก็บข้อมูลที่การเขียนข้อมูลช้าหรือทำให้สื่อบันทึกข้อมูลสึกหรอเร็ว
  • ระยะเวลาในการทำงานของมันสามารถคาดเดาได้อย่างสมบูรณ์ เนื่องจากจำนวนการเปรียบเทียบขึ้นอยู่กับความยาวของอาร์เรย์เท่านั้น

ข้อเสีย

  • ทุกกรณีมีความซับซ้อน O(n²) ดังนั้นอัลกอริทึมจึงไม่สามารถรองรับชุดข้อมูลขนาดใหญ่ได้
  • โปรแกรมนี้ไม่สามารถตรวจจับอาร์เรย์ที่เรียงลำดับแล้วได้ ดังนั้นจึงไม่จบการทำงานก่อนกำหนด
  • รูปแบบคลาสสิกที่แสดงไว้ข้างต้นนั้นไม่เสถียร ดังนั้นค่าที่เท่ากันสองค่าอาจอยู่ในลำดับที่ตรงกันข้ามได้
  • โดยทั่วไปแล้ว วิธีการนี้มักใช้ได้ผลดีกว่าการเรียงลำดับแบบแทรก (insertion sort) กับข้อมูลที่เรียงลำดับเกือบสมบูรณ์ ซึ่งในกรณีหลัง การเรียงลำดับแบบแทรกจะใช้เวลาใกล้เคียงกับเวลาเชิงเส้น

โดยสรุป ควรเลือกใช้การเรียงลำดับแบบเลือก (selection sort) เมื่ออาร์เรย์มีขนาดเล็กและการเขียนข้อมูลแต่ละครั้งมีค่าใช้จ่ายสูง และควรหลีกเลี่ยงการใช้การเรียงลำดับแบบนี้เมื่อชุดข้อมูลมีขนาดใหญ่หรือใกล้เคียงกับการเรียงลำดับอยู่แล้ว

การเรียงลำดับแบบเลือกเทียบกับการเรียงลำดับแบบเลือก Bubble-Sort เทียบกับ Insertion Sort

อัลกอริทึมทั้งสามแบบเป็นอัลกอริทึมการเรียงลำดับแบบเปรียบเทียบแบบกำลังสองและทำงานในตำแหน่งเดิม แต่พวกมันมีพฤติกรรมที่แตกต่างกันเมื่อรูปร่างของข้อมูลป้อนเข้าเปลี่ยนแปลงไป

เกณฑ์ การเรียงลำดับการเลือก Bubblเรียงลำดับ การเรียงลำดับการแทรก
เวลาที่ดีที่สุด โอ(n²) O (n) O (n)
เวลาเฉลี่ยและเวลาในกรณีที่แย่ที่สุด โอ(n²) โอ(n²) โอ(n²)
ในกรณีที่เลวร้ายที่สุด อาจมีการสลับหรือเปลี่ยนตำแหน่งได้ n-1 การแลกเปลี่ยน n(n-1)/2 สลับ เลื่อนได้สูงสุดถึง n(n-1)/2 ครั้ง
มีเสถียรภาพ ไม่ มี (ใบกำกับภาษีเต็มรูปแบบ) มี (ใบกำกับภาษีเต็มรูปแบบ)
ปรับตัวให้เข้ากับข้อมูลที่เรียงลำดับแล้ว ไม่ มี (ใบกำกับภาษีเต็มรูปแบบ) มี (ใบกำกับภาษีเต็มรูปแบบ)
พื้นที่เสริม O (1) O (1) O (1)
การใช้งานทั่วไป จำนวนผู้เขียนน้อยที่สุดที่จำเป็น การสอนและการระบุข้อมูลที่เรียงลำดับแล้ว อาร์เรย์ขนาดเล็กหรือเกือบเรียงลำดับแล้ว

ตารางนี้อธิบายคำตอบทั่วไปในการสัมภาษณ์งาน การเรียงลำดับแบบ Selection sort ชนะเลิศในด้านจำนวนการสลับตำแหน่ง การเรียงลำดับแบบ Bubble sort ชนะเลิศในด้านการจดจำข้อมูลที่เรียงลำดับแล้ว และการเรียงลำดับแบบ Insertion sort มักจะเร็วที่สุดในสามวิธีนี้ในทางปฏิบัติ เนื่องจากข้อมูลจริงมักจะเรียงลำดับมาแล้วบางส่วน ไม่มีวิธีใดเทียบได้กับ Merge sort หรือ Quick sort เมื่ออาร์เรย์มีขนาดใหญ่เกินกว่าสองสามสิบองค์ประกอบ

คำถามที่พบบ่อย

หลังจากวนซ้ำ n-1 ครั้ง บริเวณที่ยังไม่ได้เรียงลำดับจะมีองค์ประกอบเพียงตัวเดียว และมีองค์ประกอบเดี่ยวอยู่ในตำแหน่งที่ถูกต้องแล้ว การวนซ้ำอีกครั้งจะไม่เปรียบเทียบอะไรเลย ดังนั้นขอบเขตของลูปจึงหลีกเลี่ยงการวนซ้ำที่สูญเปล่า

ผู้ช่วย AI สามารถบรรยายแต่ละรอบด้วยคำพูด สร้างชุดทดสอบเพิ่มเติม และนับจำนวนการเปรียบเทียบสำหรับข้อมูลป้อนเข้าที่กำหนด ใช้คำอธิบายนี้เป็นสื่อช่วยในการศึกษา และตรวจสอบความซับซ้อนใดๆ กับตำราเรียนก่อนที่จะอ้างอิง

ใช่. นักบิน GitHub ดำเนินการตามวิธีการจากลายเซ็นหรือความคิดเห็น ตรวจสอบจุดเริ่มต้นของลูปภายในและบรรทัดการสลับด้วยตนเอง เนื่องจากเวอร์ชันที่สร้างขึ้นบางครั้งจะสลับด้วย i แทนที่จะใช้ดัชนีต่ำสุดที่จัดเก็บไว้

เวอร์ชันที่แสดงอยู่นี้ไม่เสถียร เนื่องจากค่าที่เท่ากันค่าหนึ่งอาจกระโดดข้ามค่าอีกค่าหนึ่งไปได้ Shiftการใช้บล็อกขององค์ประกอบแทนการสลับping รักษาลำดับเดิมของคีย์ที่เท่ากันไว้ แต่ต้องแลกมาด้วยการเขียนข้อมูลเพิ่มขึ้น

Reverse การเปรียบเทียบภายในลูปด้านใน การทดสอบว่า array[j] มากกว่า array[index] หรือไม่ tracks คือค่าที่เหลืออยู่มากที่สุด ดังนั้นในแต่ละรอบ ค่าสูงสุดจะถูกเลื่อนไปข้างหน้า และอาร์เรย์ที่ได้จะเรียงจากค่าสูงไปค่าต่ำ

ใช่แล้ว วิธีการเรียกซ้ำจะหาค่าต่ำสุดของซับอาร์เรย์ปัจจุบัน สลับค่าดังกล่าวไปไว้ด้านหน้า จากนั้นเรียกตัวเองซ้ำอีกครั้งกับส่วนที่เหลือ จำนวนการเปรียบเทียบจะไม่เปลี่ยนแปลง แต่สแต็กการเรียกจะเพิ่มพื้นที่ O(n) ดังนั้นจึงนิยมใช้รูปแบบลูปมากกว่า

ข้อผิดพลาดที่พบบ่อย ได้แก่ การลืมตั้งค่าดัชนีกลับไปที่ i ในตอนเริ่มต้นแต่ละรอบ การเริ่มลูปภายในที่ i แทนที่จะเป็น i + 1 และการสลับตำแหน่งping array[j] แทนที่จะเป็น array[index] ซึ่งทำให้สูญเสียข้อมูลไป track ที่มีค่าน้อยที่สุด

ไม่ครับ Arrays.sort() ใช้ quicksort แบบ dual-pivot กับข้อมูลพื้นฐาน และ TimSort กับอ็อบเจ็กต์ โดยใช้การเรียงลำดับแบบแทรกบนพาร์ติชันเล็กๆ Selection sort มักปรากฏในสื่อการสอนและโค้ดที่เขียนด้วยมือมากกว่าในไลบรารีมาตรฐาน

สรุปโพสต์นี้ด้วย: