Java Selection Sort: คู่มือการทำงานและการเขียนโค้ด

Java selection sort หาค่าที่น้อยที่สุดในลิสต์ และย้ายค่านั้นไปไว้ต้นลิสต์ ทำซ้ำจนทุกสมาชิกในลิสต์แรกถูกเรียงลำดับ คืนค่าลิสต์ที่เรียงแล้ว

จะเรียงลิสต์ใน Java ยังไง? มีหลายทางเลือก ทางเลือกทั่วไปคือ selection sort

คู่มือนี้จะพูดถึงว่า selection sorts คืออะไร ทำงานอย่างไร และวิธีสร้าง selection sort ใน Java เพื่อให้คุณสร้างของตัวเองได้ มาเริ่มกัน!

Java Selection Sort คืออะไร?

Selection sort หาค่า minimum ในลิสต์ซ้ำๆ และย้ายไปต้นของ unsorted items ในลิสต์ กระบวนการซ้ำนี้ทำซ้ำสำหรับทุกสมาชิกในลิสต์ จนลิสต์เรียงลำดับ

สมาชิกตัวแรกในลิสต์ ถือว่าเป็นค่าน้อยที่สุด ค่านี้เป็น temporary value ที่เปลี่ยนทุกครั้งที่โปรแกรมเปรียบเทียบ ค่านี้เก็บในตัวแปรของตัวเอง

ใน selection sort ลิสต์มี 2 ส่วน: sorted list และ unsorted list เมื่อสมาชิกถูกเรียงแล้ว จะย้ายจาก unsorted subarray ไป sorted subarray

สามารถเรียงลำดับได้ทั้ง ascending (น้อยไปมาก) และ descending (มากไปน้อย)

เมื่อไหร่ควรใช้ Selection Sort?

Selection sorts เหมาะสำหรับเรียงลิสต์เล็ก (small list) เพราะมีวิธีมีประสิทธิภาพมากกว่าสำหรับลิสต์ใหญ่ อัลกอริทึธ เช่น merge sort, insertion sort, quick sort มีประสิทธิภาพมากกว่า selection sort ใน Java

Selection sort ทำงานดีที่สุดเมื่อการตรวจสอบทุกสมาชิกในอาร์เรย์เป็นสิ่งบังคับ กรณีที่มีสมาชิกไม่กี่ตัวหรือไม่มีตัวไหนถูกเรียงเลย Selection sorts มัก outperforms bubble sort ซึ่งเข้าใจง่ายกว่า

Selection Sorts ทำงานอย่างไร?

ไม่ควรพยายาม implement algorithm ใน Java โดยไม่รู้ก่อนว่า algorithm ของเราต้องทำอะไร มาเดินผ่านขั้นตอนที่ selection sort ใช้เรียงลิสต์ตามลำดับ

พิจารณา unsorted array นี้:

Selection sorts ตั้งตัวแรกเป็นค่าน้อยที่สุดในลิสต์ ค่านี้เป็น temporary value ที่เปลี่ยนทุกครั้งที่โปรแกรมเปรียบเทียบ เก็บในตัวแปรของตัวเอง

minimum = 17
17	14	9	12

"Minimum" item ถูกเปรียบเทียบกับสมาชิกตัวที่สอง สมาชิกตัวนี้อยู่ใน unsorted part ของอาร์เรย์ ทุกสมาชิกหลัง sorted elements เป็น unsorted

สมมติสมาชิกตัวที่สอง น้อยกว่า "minimum" item ค่า "minimum" จะกลายเป็นค่าของสมาชิกตัวที่สอง 14 น้อยกว่า 17 ดังนั้น minimum ใหม่คือ 14

minimum = 14
17	14	9	12

กระบวนการซ้ำนี้ทำซ้ำสำหรับทุกสมาชิกในลิสต์ 9 น้อยกว่า 14 minimum กลายเป็น 9 9 ไม่น้อยกว่า 12 minimum คงเดิม

หลัง iteration หนึ่ง ลิสต์พบว่า 9 เป็นตัวเลขน้อยที่สุด ย้ายไปต้นลิสต์:

กระบวนการเริ่มใหม่จาก unsorted element ตัวแรก ดังนั้นการเปรียบเทียบชุดต่อไปเริ่มจาก 17:

17 เท่ากับ minimum
เปรียบเทียบ 17 กับ 14 minimum กลายเป็น 14
เปรียบเทียบ 14 กับ 12 minimum กลายเป็น 12
ย้าย 12 ไปท้าย sorted items ในลิสต์

ลิสต์กลายเป็น:

กระบวนการซ้ำจนลิสต์เรียงแล้ว เมื่อ algorithm จบ จะได้ลิสต์:

ลิสต์เรียง ascending order แล้ว

วิธีสร้าง Selection Sort ใน Java

รู้ว่ามันทำงานยังไงเป็นอย่างหนึ่ง แต่นำมาเขียนโค้ดเป็นอีกอย่าง มาเขียน selection sort ใน Java ใช้ logic ที่อธิบายไป

ตั้งค่าโปรแกรม

สร้างไฟล์ selection_sort.java เริ่ม import Java Arrays library:

import java.util.Arrays;

ใช้ library นี้ทีหลัง แปลง sorted array เป็น string เพื่อพิมพ์คอนโซล

สร้าง Sort Function

ต่อไป ประกาศคลาส และสร้างเมธอดที่ทำ selection sort เพิ่มใน selection_sort.java:

class SelectionSort {
    void sortNumbers(int array[]) {
        int size = array.length;
        for (int item = 0; item < size - 1; item++) {
            int minimum = item;
            for (int number = minimum + 1; number < size; number++) {
                if (array[number] < array[minimum]) {
                    minimum = number;
                }
            }
            int temporary = array[item];
            array[item] = array[minimum];
            array[minimum] = temporary;
        }
    }
}

ในคลาส กำหนดเมธอด sortNumbers ทำ sort เริ่มคำนวณความยาวอาร์เรย์ เก็บในตัวแปร Java

สร้าง Java for loop วนทุกสมาชิกในลิสต์ ภายใน for loop หา minimum item ซึ่งเป็นตัวแรกในลิสต์

เริ่ม for loop อีกอัน เปรียบเทียบ minimum item กับทุกสมาชิกในลิสต์

ถ้าตัวเลขที่ for loop อ่าน น้อยกว่า minimum number ค่า "minimum" จะกลายเป็นตัวเลขนั้น ในลูป "number" แทน index ของตัวเลขที่เปรียบเทียบกับ minimum

เมื่อ minimum number เปรียบเทียบกับทุกตัวในลิสต์แล้ว inner for loop หยุด minimum number ถูกย้ายไปหลัง sorted numbers ในลิสต์

เรียก Sort Function

โค้ดยังไม่ทำอะไร เพราะยังไม่ได้เรียกคลาสและให้ลิสต์มาจัดการ

ใต้ sortNumbers method เพิ่มโค้ด:

public static void main(String args[]) {
    int[] toSort = { 17, 14, 9, 12 };
    SelectionSort newSort = new SelectionSort();
    newSort.sortNumbers(toSort);
    System.out.println(Arrays.toString(toSort));
}

ใน main method ประกาศลิสต์ toSort สร้าง instance SelectionSort ชื่อ newSort ใช้เรียก sortNumbers จัดเรียงค่าใน toSort array

หลัง sortNumbers ทำงานเสร็จ พิมพ์ sorted array ออกคอนโซล ใช้ Arrays.toString() แปลงอาร์เรย์เป็น string list

รันโค้ด:

[9, 12, 14, 17]

ลิสต์ถูกเรียงแล้ว!

Selection Sort Java: เรียงค่า Descending Order

สังเกตว่า สามารถเรียง descending order ได้ แทนบรรทัดนี้ใน sortNumbers method:

if (array[number] < array[minimum]) {

ด้วยโค้ดนี้:

if (array[number] > array[minimum]) {

โค้ดนี้เช็คว่า "minimum" value มากกว่าที่ for loop เข้าถึงหรือไม่ หมายถึง "minimum" จะสะท้อนค่าสูงสุดในลิสต์ แทนที่จะเป็นค่าต่ำสุด

เพื่อป้องกันความสับสน ควร rename "minimum" เป็น "maximum" หากเรียง descending order

คุณทำได้แล้ว! คุณเรียงลิสต์ใน Java ด้วย selection sorting algorithm

Complexity ของ Java Selection Sort คืออะไร?

มี 3 time complexities พิจารณาเวลาประเมิน algorithm: best case, worst case, average case

Selection sort มี best, average, worst case complexity เป็น O(n^2) หมายถึง algorithm จะช้าขึ้น exponentially เมื่อจำนวนสมาชิกในลิสต์เพิ่ม

งงกับ complexity ของ algorithms? อ่าน series 2 ส่วนของเราเกี่ยวกับ Big O Notation สัญกรณ์ที่ใช้อธิบาย complexity ของ algorithms

สรุป

Selection sorts เป็นวิธีมีประสิทธิภาพสำหรับเรียงลิสต์ข้อมูล ทำงานโดยเลือกค่าน้อยที่สุดจาก unsorted list ย้ายไปต้น unsorted list ทำซ้ำจนลิสต์เรียงแล้ว

อยากเป็น Java developer? อ่าน How to Learn Java guide ของเรา จะมี learning tips และคำแนะนำ online courses และ learning resources ที่ดีที่สุด