Note: ส่วนที่ 2 ของซีรีส์ Sorting Algorithms ด้วย Ruby ส่วนที่ 1 สำรวจ Bubble Sort
ในโพสต์นี้ ผมจะเดินผ่านการ Implement Selection Sort Algorithm ด้วย Ruby Selection Sort เป็น In-place Comparison Sorting Algorithm หมายถึง Sorted Items ครอบครอง Storage เดียวกับ Original ก่อนไปต่อ สำคัญที่ต้องทราบว่า Selection Sort ไม่ค่อยใช้ใน Practice เว้นแต่ Dataset เล็ก (เช่น 10-20 Elements) แต่เป็น Starter Algorithm เรียนรู้ได้ดี คล้ายเรียนขี่สามล้อก่อนจักรยาน Implementation อาจขึ้นใน Coding Challenge สัมภาษณ์งาน หรืออาจถูกถามว่า ทำไม Algorithm แบบ Selection Sort ไม่ Practical บน Dataset ใหญ่ Selection Sort ปกติ Outperform Bubble Sort ซึ่งเป็น Algorithm แรกในซีรีส์นี้
ภาพรวม Selection Sort แบ่ง Array สองส่วน: ส่วน Sorted และ Unsorted เริ่มต้น Sorted Section ว่าง และ Unsorted Portion มี Elements ทั้งหมด Selection Sort ใช้ Two Loops Outer Loop Iterate n ครั้ง (n = จำนวน Elements) เราตั้ง "Min Index" ไปที่ Element แรก แล้วใช้ Loop อีกอัน Compare Elements สลับ Min Index ถ้า Adjacent Element น้อยกว่า Current Minimum
ถ้ายากต่อการติดตาม อย่ากลัว! เราจะเดินผ่านตัวอย่างจริงต่อไป :)
Step By Step
เริ่มกับ Array Elements: [10, 30, 27, 7, 33, 15, 40, 50]
Iteration หนึ่ง: หาตัวเลขน้อยที่สุด
ในกรณีนี้ ตัวเลขน้อยที่สุดคือ 7 วางไว้ต้นและย้าย 10 ไปที่ 7 เดิม Array กลายเป็น: [7, 30, 27, 10, 33, 15, 40, 50]
Iteration สอง: หาตัวเลขน้อยที่สุดถัดไป
เริ่มที่ Element Index 1 (Arrays 0-indexed) หา Next Smallest Element
ในกรณีนี้คือ 10. ย้าย 10 ไปตำแหน่งสอง และ 30 ไปที่ 10 เดิม Array กลายเป็น: [7, 10, 27, 30, 33, 15, 40, 50]
จากนี้ทำ Process เดียวกันต่อจน Array Sorted ด้านล่างคือ Arrays ผลลัพธ์หลัง Iterations ต่อไป
Iteration สาม:
[7, 10, 15, 30, 33, 27, 40, 50]
Iteration สี่:
[7, 10, 15, 27, 33, 30, 40, 50]
Iteration ห้า:
[7, 10, 15, 27, 30, 33, 40, 50]
Bingo! Sorted แล้ว!
ถ้าคุณเป็น Visual Learner นี่คือตัวอย่าง Selection Sort กับ Array []
Photo credit
A Ruby Implementation
นี่คือ Selection Sort Function ใน Ruby:
def selection_sort(array) n = array.length - 1 n.times do |i| min_index = i for j in (i + 1)..n min_index = j if array[j] < array[min_index] end array[i], array[min_index] = array[min_index], array[i] if min_index != i end puts array end มาดูว่าทำงานอย่างไร
แรก ตั้ง n เท่ากับจำนวน Elements จำได้ว่า ลบหนึ่งเพราะ Arrays 0-indexed
ต่อไป สร้าง Outer Loop รัน n ครั้ง
min_index = i ที่นี่ ตั้ง Minimum Index ไปที่ Element ตำแหน่งแรก
for j in (i + 1)..n ต่อไป สร้าง Inner Loop บรรทัดนี้พูดว่า "สำหรับ Element ตำแหน่งสอง ถึง nth Element ทำต่อไป" ถ้าไม่คุ้นเคย Operator .. มันสร้าง Range จาก Start ถึง End Inclusive เช่น 1..10 สร้าง Range 1 ถึง 10 Inclusive
min_index = j if array[j] < array[min_index] ภายใน Loop ตั้ง min_index เป็น Element ใหม่ถ้ามันน้อยกว่า min_index ปัจจุบัน
array[i], array[min_index] = array[min_index], array[i] if min_index != i นอก Inner Loop เราเช็คว่า Current min_index เท่ากับ i หรือไม่ ถ้า True เราต้อง Shuffle Elements ตั้ง array[i] เป็น array[min_index] และ array[min_index] เป็น array[i] ที่นี่เราทำ "Swap" เหมือนตัวอย่าง
สุดท้าย จบแล้ว Output Array ที่ Sorted แล้ว!
Putting it All Together
นี่คือ Full Program ของผม:
def selection_sort(array) n = array.length - 1 n.times do |i| min_index = i for j in (i + 1)..n min_index = j if array[j] < array[min_index] end array[i], array[min_index] = array[min_index], array[i] if min_index != i end puts array end array = [10, 30, 27, 7, 33, 15, 40, 50] selection_sort(array) รัน ruby ruby-selection-sort.rb จาก Terminal Output:
7 10 15 27 30 33 40 50 Cool!
ทำไม Selection Sort ไม่ Efficient
หนึ่งวิธีวัด Efficiency คือ "Big-O Notation" แทน Worst-case Performance เพื่อเปรียบเทียบ Algorithms เช่น Algorithm Big-O O(1) หมายถึง Worst-case Run Time Constant ขณะ n เพิ่ม ในขณะที่ O(n) หมายถึง Worst-case Run Time เพิ่ม Linear ตาม n หมายถึงถ้าคุณมี Array 100 Elements และเลือกระหว่าง O(n) และ O(1) คุณเลือก O(1) เพราะ O(1) ชนะ O(100) แน่นอน
เหมือน Bubble Sort Selection Sort มี Worst-case และ Average Complexity O(n^2) เนื่องจาก Nested Loops หมายถึง Efficiency ลดลง drastically เมื่อ Elements เยอะขึ้น
สรุป
ทั้งหมดที่พิจารณา Selection Sort ยังเป็น Algorithm น่าสนใจ อาจ Pop-up ใน Coding Challenge หรือให้ Selection Sort Function ถาม Big-O Notation และทำไม หวังว่า Examples ในบทความจะช่วยให้คุณพร้อมสำหรับทั้งสอง Scenario
