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