การจัดเรียงแบบเลือก (selection sort)

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

การจัดเรียงแบบเลือก (selection sort) เป็นวิธีการจัดเรียงข้อมูล ที่เข้าใจง่าย โดยมีหลักการคือการเลือกข้อมูลตามเงื่อนไข ออกมาจัดเรียงไว้ทีละตัว ไปจนครบ

ตัวอย่างที่ 1 การเรียงลำดับข้อมูลจากน้อยไปหามาก

ขั้นตอนวิธี : การเรียงข้อมูลแบบเลือก
ข้อมูลเข้า : รายการข้อมูล L
ข้อมูลออก : รายการคำตอบ S ที่เรียงลำดับแล้ว

ขั้นตอนวิธี
1. ให้ S แทนรายการคำตอบ โดยเมื่อเริ่มต้น S จะเป็นรายการว่าง
2. ให้ N = จำนวนข้อมูลในรายการ L
3. ทำซ้ำ N รอบ
3.1 เลือกข้อมูลที่น้อยที่สุดจาก รายการ L ที่ยังไม่ถูกขีดทับ และแทนที่ข้อมูลนั้นด้วย M
3.2 ขีดทับข้อมูล M ในรายการ L
3.3 เพิ่ม M ต่อท้ายรายการคำตอบของ S

กำหนดให้ L = {25, 27, 30, 21, 22, 28, 20, 23} และ S = {…}

รอบที่LMS
1L = {25, 27, 30, 21, 22, 28, 20, 23}20S = {20}
2L = {25, 27, 30, 21, 22, 28, 20, 23}21S = {20, 21}
3L = {25, 27, 30, 21, 22, 28, 20, 23}22S = {20, 21, 22}
4L = {25, 27, 30, 21, 22, 28, 20, 23}23S = {20, 21, 22, 23}
5L = {25, 27, 30, 21, 22, 28, 20, 23}25S = {20, 21, 22, 23, 25}
6L = {25, 27, 30, 21, 22, 28, 20, 23}27S = {20, 21, 22, 23, 25, 27}
7L = {25, 27, 30, 21, 22, 28, 20, 23}28S = {20, 21, 22, 23, 25, 27, 28}
8L = {25, 27, 30, 21, 22, 28, 20, 23}30S = {20, 21, 22, 23, 25, 27, 28, 30}

ถาม – ตอบ
ข้อ 1 การทำงานมีทั้งหมดกี่รอบ
ข้อ 2 รอบที่ 3 ข้อมูลที่ได้มีอะไรบ้าง
ข้อ 3 รอบที่ 5 ข้อมูลที่เหลือมีอะไรบ้าง
ข้อ 4 รอบที่ 6 ข้อมูลที่ได้มีอะไรบ้าง
ข้อ 5 รอบที่ 7 ข้อมูลที่เหลือมีอะไรบ้าง

ตัวอย่างที่ 2 การเรียงลำดับข้อมูลจากมากไปหาน้อย

ขั้นตอนวิธี : การเรียงข้อมูลแบบเลือก
ข้อมูลเข้า : รายการข้อมูล L
ข้อมูลออก : รายการคำตอบ S ที่เรียงลำดับแล้ว

ขั้นตอนวิธี
1. ให้ S แทนรายการคำตอบ โดยเมื่อเริ่มต้น S จะเป็นรายการว่าง
2. ให้ N = จำนวนข้อมูลในรายการ L
3. ทำซ้ำ N รอบ
3.1 เลือกข้อมูลที่มากที่สุดจาก รายการ L ที่ยังไม่ถูกขีดทับ และแทนที่ข้อมูลนั้นด้วย M
3.2 ขีดทับข้อมูล M ในรายการ L
3.3 เพิ่ม M ต่อท้ายรายการคำตอบของ S

กำหนดให้ L = {25, 27, 30, 21, 22, 28, 20, 23} และ S = {…}

รอบที่LMS
1L = {25, 27, 30, 21, 22, 28, 20, 23}30S = {30}
2L = {25, 27, 30, 21, 22, 28, 20, 23}28S = {30, 28}
3L = {25, 27, 30, 21, 22, 28, 20, 23}27S = {30, 28, 27}
4L = {25, 27, 30, 21, 22, 28, 20, 23}25S = {30, 28, 27, 25}
5L = {25, 27, 30, 21, 22, 28, 20, 23}23S = {30, 28, 27, 25, 23}
6L = {25, 27, 30, 21, 22, 28, 20, 23}22S = {30, 28, 27, 25, 23, 22}
7L = {25, 27, 30, 21, 22, 28, 20, 23}21S = {30, 28, 27, 25, 23, 22, 21}
8L = {25, 27, 30, 21, 22, 28, 20, 23}20S = {30, 28, 27, 25, 23, 22, 21, 20}

ถาม – ตอบ
ข้อ 1 การทำงานมีทั้งหมดกี่รอบ
ข้อ 2 รอบที่ 2 ข้อมูลที่ได้มีอะไรบ้าง
ข้อ 3 รอบที่ 4 ข้อมูลที่เหลือมีอะไรบ้าง
ข้อ 4 รอบที่ 5 ข้อมูลที่ได้มีอะไรบ้าง
ข้อ 5 รอบที่ 6 ข้อมูลที่เหลือมีอะไรบ้าง

การจัดเรียงแบบเลือก จะมีจำนวนรอบการทำงาน เท่ากับจำนวนข้อมูลทั้งหมด การทำงานแต่ละรอบจะส่งผลต่อข้อมูลในรอบถัดไป ดังนั้น จะต้องทำงานด้วยความรอบคอบ