ทำความเข้าใจการเลือกเรียงลำดับด้วย Ruby

หมายเหตุ:นี่เป็นตอนที่ 2 ของซีรีส์ที่พิจารณาอัลกอริธึมการจัดเรียงต่างๆ ด้วย Ruby ส่วนที่ 1 สำรวจการจัดเรียงลูกโป่ง

ในโพสต์นี้ ฉันจะอธิบายวิธีการใช้อัลกอริธึมการเรียงลำดับการเลือกด้วย Ruby การเรียงลำดับการเลือกเป็นอัลกอริธึมการเรียงลำดับการเปรียบเทียบแบบแทนที่ ซึ่งหมายความว่ารายการที่จัดเรียงใช้พื้นที่เก็บข้อมูลเดียวกันกับรายการดั้งเดิม ก่อนที่เราจะดำเนินการต่อไป สิ่งสำคัญคือต้องสังเกตว่าอัลกอริธึมการเรียงลำดับการเลือกนั้นไม่ได้ใช้กันทั่วไปในทางปฏิบัติ เว้นแต่ชุดข้อมูลจะมีขนาดเล็ก (เช่น องค์ประกอบ 10-20) อย่างไรก็ตาม มันเป็นอัลกอริธึมเริ่มต้นที่ยอดเยี่ยมในการเรียนรู้และทำความเข้าใจ เช่นเดียวกับการเรียนรู้วิธีการขี่รถสามล้อก่อนขี่จักรยาน หากคุณต้องการ การใช้งานอาจมีปัญหาในการเขียนโค้ดสำหรับการสัมภาษณ์งาน หรือคุณอาจถูกขอให้อธิบายทำไม อัลกอริธึมเช่นการเรียงลำดับการเลือกจะไม่เป็นประโยชน์กับชุดข้อมูลขนาดใหญ่ การเรียงลำดับการเลือกมักจะมีประสิทธิภาพดีกว่าการเรียงลำดับแบบฟอง ซึ่งเป็นอัลกอริทึมแรกที่เราดูในชุดนี้

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

ถ้าติดตามยากก็ไม่ต้องเป็นห่วง! เราจะพูดถึงตัวอย่างที่เกิดขึ้นจริงต่อไป :)

ทีละขั้นตอน

เริ่มจากอาร์เรย์ที่มีองค์ประกอบดังต่อไปนี้ [10, 30, 27, 7, 33, 15, 40, 50]

วนซ้ำ:ค้นหาจำนวนที่น้อยที่สุด

ในกรณีนี้ จำนวนที่น้อยที่สุดคือ 7 ดังนั้นเราจึงวางไว้ที่จุดเริ่มต้นและย้าย 10 ไปที่ 7 เคยเป็น. อาร์เรย์ของเราตอนนี้มีลักษณะดังนี้:[7, 30, 27, 10, 33, 15, 40, 50]

วนซ้ำสอง:ค้นหาจำนวนที่น้อยที่สุดถัดไป

เริ่มต้นที่องค์ประกอบในตำแหน่งดัชนี 1 (จำไว้ว่าอาร์เรย์เป็น 0 ดัชนี) ค้นหาองค์ประกอบที่เล็กที่สุดถัดไป

ในกรณีนี้คือ 10. ย้าย 10 ไปที่ตำแหน่งที่สองในอาร์เรย์แล้วย้าย 30 ไปที่ 10 เคยเป็น. อาร์เรย์ที่ได้จะเป็นดังนี้:[7, 10, 27, 30, 33, 15, 40, 50]

จากที่นี่ เราจะดำเนินการตามกระบวนการนี้ต่อไปจนกว่าอาร์เรย์ของเราจะถูกจัดเรียงอย่างสมบูรณ์ ด้านล่างนี้ คุณสามารถดูอาร์เรย์ที่ได้หลังจากการทำซ้ำครั้งถัดไป

ซ้ำสาม:

[7, 10, 15, 30, 33, 27, 40, 50]

ซ้ำสี่:

[7, 10, 15, 27, 33, 30, 40, 50]

ซ้ำห้า:

[7, 10, 15, 27, 30, 33, 40, 50]

บิงโก! พวกเราเรียบร้อย!

หากคุณเป็นผู้เรียนรู้ด้วยภาพมากกว่า นี่คือตัวอย่างวิธีที่การเรียงลำดับการเลือกจะทำงานกับอาร์เรย์ของ []

เครดิตรูปภาพ

การนำทับทิมไปใช้

นี่คือฟังก์ชันการเรียงลำดับการเลือกที่เขียนด้วย 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 เท่ากับจำนวนองค์ประกอบ จำไว้ว่าเราต้องลบหนึ่งตัวเพราะอาร์เรย์มีดัชนี 0 ตัว

ต่อไป เราสร้างวงรอบนอกซึ่งกำลังจะเรียกใช้ n ครั้ง

min_index = i

ที่นี่ เรากำลังตั้งค่าดัชนีขั้นต่ำให้กับองค์ประกอบในตำแหน่งแรก

for j in (i + 1)..n

ต่อไป เราสร้างวงในของเรา บรรทัดนี้เขียนว่า "สำหรับองค์ประกอบในตำแหน่งที่สองถึงองค์ประกอบที่ n ให้ทำดังนี้" หากคุณไม่คุ้นเคยกับ .. โอเปอเรเตอร์จะสร้างช่วงจากจุดเริ่มต้นไปยังจุดสิ้นสุดโดยรวม ตัวอย่างเช่น 1..10 สร้างช่วงตั้งแต่ 1 ถึง 10 รวม

min_index = j if array[j] < array[min_index]

ภายในลูปนี้ เราตั้งค่า min_index เป็นองค์ประกอบใหม่หากน้อยกว่า min_index current ปัจจุบัน .

array[i], array[min_index] = array[min_index], array[i] if min_index != i

นอกวงในของเรา เราจะดูว่า min_index . ปัจจุบัน เท่ากับ i . หากสิ่งนี้เป็นจริง เราต้องสับเปลี่ยนองค์ประกอบของเรา เราตั้งค่า array[i] ไปยัง array[min_index] และ array[min_index] ไปยัง array[i] . ที่นี่ เรากำลังดำเนินการ "สลับ" เหมือนกับที่เราทำในตัวอย่างของเรา

ในที่สุด เมื่อเสร็จแล้ว เราก็เอาอาร์เรย์ของเราออกมา ซึ่งตอนนี้จัดเรียงแล้ว!

รวมทุกอย่างเข้าด้วยกัน

นี่คือโปรแกรมทั้งหมดของฉัน:

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 จากเทอร์มินัลเอาต์พุตต่อไปนี้:

7
10
15
27
30
33
40
50

เจ๋ง!

ทำความเข้าใจว่าทำไมการเรียงลำดับการเลือกจึงไม่มีประสิทธิภาพ

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

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

สรุปผล

เมื่อพิจารณาจากทั้งหมดแล้ว การเรียงลำดับการเลือกยังคงเป็นอัลกอริธึมที่น่าสนใจซึ่งอาจปรากฏขึ้นในความท้าทายในการเขียนโค้ด หรือคุณอาจได้รับฟังก์ชันการเรียงลำดับการเลือกและถามว่าสัญกรณ์ Big-O คืออะไรและเพราะเหตุใด หวังว่าตัวอย่างในบทความนี้จะช่วยให้คุณพร้อมที่จะรับมือกับสถานการณ์ใดสถานการณ์หนึ่ง