วิกิพีเดีย

ผลต่างระหว่างรุ่นของ "การเรียงลำดับแบบเลือก"

เรียกดูประวัติแบบโต้ตอบ
← การแก้ไขก่อนหน้าการแก้ไขถัดไป →
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
เห็นภาพข้อความวิกิ
ไม่มีความย่อการแก้ไข
แทนที่เนื้อหาด้วย " ก.ไก่ ข.ไข่"
ป้ายระบุ: ถูกแทน แก้ไขจากอุปกรณ์เคลื่อนที่ แก้ไขจากเว็บสำหรับอุปกรณ์เคลื่อนที่ blanking
บรรทัด 1:
{{รายละเอียดทางขั้นตอนวิธี
| ชื่อ = การเรียงลำดับแบบเลือก
| ประเภท = [[ขั้นตอนวิธีการเรียงลำดับ]]
| รูปภาพ = [[ไฟล์:Selection-Sort-Animation.gif]]
| คำอธิบาย = แสดงขั้นตอนการทำงานของการเรียงลำดับแบบเลือก; สีเหลือง คือ เรียงเรียบร้อยแล้ว ; สีแดง คือ ค่าที่น้อยที่สุดในปัจจุบัน ; สีฟ้า คือ ค่าที่กำลังพิจารณา
| ข้อมูล = [[รายการ (โครงสร้างข้อมูล)|รายการ]]
| เวลา = <math>O(n^2)</math>
| เวลาดีที่สุด = <math>O(n^2)</math>
| เวลาทั่วไป = <math>O(n^2)</math>
| พื้นที่ = ใช้พื่นที่ <math>O(1)</math> เพิ่มเติม
| optimal = No
}}
ในสาขา[[วิทยาการคอมพิวเตอร์]] '''การเรียงลำดับแบบเลือก''' ({{lang-en|selection sort}}) เป็น[[ขั้นตอนวิธีการเรียงลำดับ]]อย่างง่ายโดยใช้วิธีการเปรียบเทียบ ทำงานโดยการหาค่าเหมาะสมที่สุด (ค่ามากสุดหรือน้อยสุด) ที่อยู่ใน[[รายการ]]ส่วนที่ยังไม่เรียงและนำค่าเหมาะที่สุดนั้นมาต่อท้ายของส่วนที่เรียงแล้ว ก็จะทำให้ส่วนที่เรียงแล้วมีขนาดใหญ่ขึ้นทีละหนึ่งในแต่ละรอบการทำงาน ทำเช่นนี้จนไม่มีส่วนที่ยังไม่เรียงก็เสร็จ แต่ด้วยประสิทธิภาพเมื่อเกิดกรณีทั่วไปที่ O(n<sup>2</sup>) ทำให้ไม่เหมาะที่จะใช้ในกรณีที่มีข้อมูลในรายการเป็นจำนวนมาก แต่ถ้าหากปรับปรุงการหาค่าเหมาะสมที่สุดในรายการด้วย[[แถวคอยลำดับความสำคัญ]]ที่[[การทำให้เกิดผล|ทำให้เกิดผล]]ด้วยโครงสร้างข้อมูลแบบ[[ฮีปทวิภาค]]จะเรียกว่า[[การเรียงลำดับแบบฮีป]] ซึ่งมีประสิทธิภาพดีกว่าที่ O(n log n)
 
ก.ไก่ ข.ไข่
== การวิเคราะห์ ==
=== ประสิทธิภาพ ===
การเรียงลำดับแบบเลือกไม่เพียงง่ายต่อการเข้าใจแล้ว ก็ง่ายต่อการวิเคราะห์ด้วยเพราะว่าข้อมูลที่อยู่ในรายการนั้นแทบไม่มีผลต่อการทำงานของการเรียงลำดับแบบเลือกเลย เริ่มด้วยส่วนของการเลือกค่าที่เหมาะสมที่สุด (มากสุดหรือน้อยสุด) จากข้อมูลส่วนที่ยังไม่เรียงนั้นหากในส่วนนี้มีข้อมูลอยู่ n ตัว ก็จะเปรียบเทียบอย่างน้อย n-1 ครั้ง เมื่อได้ค่าเหมาะสมที่สุดแล้วก็สลับกับตัวแรกของส่วนที่ยังไม่เรียง แล้วลดขนาดของส่วนที่ยังไม่เรียงลงหนึ่ง แล้วก็หาค่าเหมาะสมที่สุดใหม่อีกครั้ง และแน่นอนส่วนที่ยังไม่เรียงก็จะเหลือข้อมูล n-1 ตัว (ก็ต้องเปรียบเทียบ n-2 ครั้ง) ทำเช่นนั้นไปเรื่อยๆ ดังนั้นจำนวนการเปรียบเทียบทั้งหมดเท่ากับ <math>(n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 \in \theta (n^2)</math>
 
=== ตัวอย่างทีละขั้นตอน ===
การเรียงลำดับข้อมูลในรายการดังนี้ 64 25 12 22 11 ด้วยขั้นตอนวิธีแบบเลือก เริ่มต้นถือว่าทุกตัวในรายการยังไม่เรียง<br>
'''ครั้งที่ 1''' หาตัวที่มีค่าน้อยที่สุดในรายการส่วนที่ยังไม่เรียงนั่นคือ 11 สลับกับตัวแรกของข้อมูลที่ยังไม่เรียงนั่นคือ 64<br>
('''64''' 25 12 22 '''11''') <math>\to</math> ('''11''' 25 12 22 '''64''')<br>
'''ครั้งที่ 2''' หาตัวที่มีค่าน้อยที่สุดนั่นคือ 12 สลับกับตัวแรกนั่นคือ 25<br>
(11 '''25''' '''12''' 22 64) <math>\to</math> (11 '''12''' '''25''' 22 64)<br>
'''ครั้งที่ 3''' หาตัวที่มีค่าน้อยที่สุดนั่นคือ 22 สลับกับตัวแรกนั่นคือ 25<br>
(11 12 '''25''' '''22''' 64) <math>\to</math> (11 12 '''22''' '''25''' 64) <br>
เรียงเสร็จเรียบร้อย<br>
 
== การนำมาใช้งาน ==
=== ตัวอย่าง[[รหัสเทียม]] ===
<source lang = "pascal">
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
</source>
 
== อ้างอิง... ==
[[หมวดหมู่:ขั้นตอนวิธีการเรียงลำดับ]]
[[หมวดหมู่:การเรียงแบบเปรียบเทียบ]]
{{โครงการเขียนโปรแกรม}}
เข้าถึงจาก "https://th.wikipedia.org/wiki/การเรียงลำดับแบบเลือก"