การเรียงลำดับแบบเลือก

จากวิกิพีเดีย สารานุกรมเสรี
การเรียงลำดับแบบเลือก
Selection-Sort-Animation.gif
แสดงขั้นตอนการทำงานของการเรียงลำดับแบบเลือก; สีเหลือง คือ เรียงเรียบร้อยแล้ว ; สีแดง คือ ค่าที่น้อยที่สุดในปัจจุบัน ; สีฟ้า คือ ค่าที่กำลังพิจารณา
ประเภท ขั้นตอนวิธีการเรียงลำดับ
โครงสร้างข้อมูล รายการ
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด O(n^2)
ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด O(n^2)
ประสิทธิภาพเมื่อเกิดกรณีทั่วไป O(n^2)
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด ใช้พื่นที่ O(1) เพิ่มเติม
    

ในสาขาวิทยาการคอมพิวเตอร์ การเรียงลำดับแบบเลือก (อังกฤษ: selection sort) เป็นขั้นตอนวิธีการเรียงลำดับอย่างง่ายโดยใช้วิธีการเปรียบเทียบ ทำงานโดยการหาค่าเหมาะสมที่สุด (ค่ามากสุดหรือน้อยสุด) ที่อยู่ในรายการส่วนที่ยังไม่เรียงและนำค่าเหมาะที่สุดนั้นมาต่อท้ายของส่วนที่เรียงแล้ว ก็จะทำให้ส่วนที่เรียงแล้วมีขนาดใหญ่ขึ้นทีละหนึ่งในแต่ละรอบการทำงาน ทำเช่นนี้จนไม่มีส่วนที่ยังไม่เรียงก็เสร็จ แต่ด้วยประสิทธิภาพเมื่อเกิดกรณีทั่วไปที่ O(n2) ทำให้ไม่เหมาะที่จะใช้ในกรณีที่มีข้อมูลในรายการเป็นจำนวนมาก แต่ถ้าหากปรับปรุงการหาค่าเหมาะสมที่สุดในรายการด้วยแถวคอยลำดับความสำคัญที่ทำให้เกิดผลด้วยโครงสร้างข้อมูลแบบฮีปทวิภาคจะเรียกว่าการเรียงลำดับแบบฮีป ซึ่งมีประสิทธิภาพดีกว่าที่ O(n log n)

การวิเคราะห์[แก้]

ประสิทธิภาพ[แก้]

การเรียงลำดับแบบเลือกไม่เพียงง่ายต่อการเข้าใจแล้ว ก็ง่ายต่อการวิเคราะห์ด้วยเพราะว่าข้อมูลที่อยู่ในรายการนั้นแทบไม่มีผลต่อการทำงานของการเรียงลำดับแบบเลือกเลย เริ่มด้วยส่วนของการเลือกค่าที่เหมาะสมที่สุด (มากสุดหรือน้อยสุด) จากข้อมูลส่วนที่ยังไม่เรียงนั้นหากในส่วนนี้มีข้อมูลอยู่ n ตัว ก็จะเปรียบเทียบอย่างน้อย n-1 ครั้ง เมื่อได้ค่าเหมาะสมที่สุดแล้วก็สลับกับตัวแรกของส่วนที่ยังไม่เรียง แล้วลดขนาดของส่วนที่ยังไม่เรียงลงหนึ่ง แล้วก็หาค่าเหมาะสมที่สุดใหม่อีกครั้ง และแน่นอนส่วนที่ยังไม่เรียงก็จะเหลือข้อมูล n-1 ตัว (ก็ต้องเปรียบเทียบ n-2 ครั้ง) ทำเช่นนั้นไปเรื่อยๆ ดังนั้นจำนวนการเปรียบเทียบทั้งหมดเท่ากับ (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 \in \theta (n^2)

ตัวอย่างทีละขั้นตอน[แก้]

การเรียงลำดับข้อมูลในรายการดังนี้ 64 25 12 22 11 ด้วยขั้นตอนวิธีแบบเลือก เริ่มต้นถือว่าทุกตัวในรายการยังไม่เรียง
ครั้งที่ 1 หาตัวที่มีค่าน้อยที่สุดในรายการส่วนที่ยังไม่เรียงนั่นคือ 11 สลับกับตัวแรกของข้อมูลที่ยังไม่เรียงนั่นคือ 64
(64 25 12 22 11) \to (11 25 12 22 64)
ครั้งที่ 2 หาตัวที่มีค่าน้อยที่สุดนั่นคือ 12 สลับกับตัวแรกนั่นคือ 25
(11 25 12 22 64) \to (11 12 25 22 64)
ครั้งที่ 3 หาตัวที่มีค่าน้อยที่สุดนั่นคือ 22 สลับกับตัวแรกนั่นคือ 25
(11 12 25 22 64) \to (11 12 22 25 64)
เรียงเสร็จเรียบร้อย

การนำมาใช้งาน[แก้]

ตัวอย่างรหัสเทียม[แก้]

begin selectionSort ( A คือ แถวลำดับที่จะถูกเรียง )
   for i = 0 to ขนาดของ(A) - 1
      ให้ตำแหน่งของค่าน้อยสุด คือ i
      for j = i+1 to ขนาดของ(A) - 1
	 if A[j] < A[ตำแหน่งของค่าน้อยสุด] then
	    ให้ตำแหน่งของค่าน้อยสุด คือ j
	 end if
      end for
      สลับ A[i] กับ A[ตำแหน่งของค่าน้อยสุด]
   end for
end

อ้างอิง[แก้]