Algorithm การจัดเรียงข้อมูลแบบ Selection Sort

สวัสดีครับ ในบทความนี้จะเป็นการแนะนำ Algorithm การจัดเรียงข้อมูลแบบ Selection Sort มีประสิทธิภาพในการทำงานเร็วสุดที่ O(n²) เฉลี่ย O(n²) แย่สุด O(n²)  ซึ่ง ในการทำงานเร็วสุด (Best Case) ก็ยังถือว่าน้อยกว่า Bubble Sort อยู่มาก

Selection Sort

Selection Sort มีวิธีการเขียนคือ เราจะมีการสร้างลูป (Loop) สองตัวขึ้นมา นั้นก็คือ i และ j โดยให้ลูป i ทำงานตั้งแต่แรกจนถึง n-1 และ j จะทำงานตั้งแต่ i+1 ไปจนถึง n โดยในลูป j เราจะสร้างเงื่อนไขว่า หาก ค่าของ arr[j] น้อยกว่า arr[i] เราก็จะสลับสองตัวนี้ เมื่อ j ทำงานไปครบหนึ่งรอบ ก็จะเพิ่มค่า i

จะได้โค้ดหน้าตา ดังนี้ (Python)

def selectionsort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(i+1, n):
            if(arr[j] < arr[i]):
                temp = arr[j]
                arr[j] = arr[i]
                arr[i] = temp
                print("i =",i,"j =",j,arr)

ได้ผลลัพท์ดังนี้

Selection sort in 3 minutes

วิดีโอสาธิตวิธีการจัดเรียงข้อมูลแบบ Selection Sort โดย Michael Sambol

อ้างอิง: geeksforgeeks.org, Michael Sambol