Casio fx-5800P - การเรียงลำดับข้อมูลใน Array

ประโยชน์อีกอย่างหนึ่งของ Array คือ เราสามารถเขียนโปรแกรมเพื่อเรียงลำดับข้อมูลจากมากไปหาน้อยหรือจากน้อยไปหามากได้ เรียกอีกอย่างว่าการ Sorting

การ Sorting นั้นมีหลากหลายวิธี ส่วนวิธีที่นำมาแสดงเป็นตัวอย่างในบทนี้จะใช้วิธีที่เรียกว่า "Selection Sort" เพียงวิธีเดียวซึ่งเป็นวิธีการเรียงลำดับข้อมูลที่ง่ายที่สุดวิธีหนึ่งในบรรดาทั้งหมด สำหรับท่านที่สนใจการเรียงลำดับข้อมูลวิธีอื่นๆ ก็สามารถค้นหาใน google ด้วยคำว่า "Sorting Algorithm"

 Selection Sort 

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

จะขออธิบายขั้นตอนการทำงานไปพร้อมกับตัวอย่างเพื่อให้เห็นภาพ

ตัวอย่าง ต้องการเรียงลำดับข้อมูลจาก น้อยไปหามาก จากตัวเลขชุดนี้ 2, 5, 1, 4, 3

กำหนดให้สีสัญลักษณ์

   แทนตำแหน่งที่ต้องการนำตัวเลขที่เรียงลำดับมาวาง

   แทนตัวเลขที่มีค่าน้อยที่สุดที่พบ

วิธีการ 

ตัวเลขเริ่มต้นคือ 2  5  1  4  3

รอบที่ 1 ให้เอาตัวเลขตำแหน่งที่ 1 ซ้ายสุดเป็นหลัก(ในตัวอย่างคือ 2)นำไปเทียบกับตัวเลขทางขวามือที่เหลืออีก 4 ตัวที่เหลือเพื่อหาตัวเลขที่มีค่าน้อยสุดคือตำแหน่งที่ 3(เลข 1) ทำการสลับค่าตำแหน่งที่ 1 กับตำแหน่งที่ 3

ได้ตัวเลขชุดใหม่คือ  1  5  2  4  3

รอบที่ 2 เอาตัวเลขถัดมาคือตำแหน่งที่ 2 เป็นหลัก(เลข 5) นำไปเปรียบเทียบหาค่าน้อยสุดกับสามตัวทางขวาที่เหลือ ได้ตำแหน่งที่ 3(เลข 2) ทำการสลับค่าตำแหน่งที่ 2 กับตำแหน่งที่ 3

ได้ตัวเลขชุดใหม่คือ  1  2  5  4  3

รอบที่ 3 เอาตัวเลขตำแหน่งที่ 3 เป็นหลัก(เลข 5) นำไปเปรียบเทียบหาค่าน้อยสุดกับสองตัวที่เหลือ ได้ตำแหน่งที่ 5(เลข 3) ทำการสลับค่าตำแหน่งที่ 3 กับตำแหน่งที่ 5

ได้ตัวเลขชุดใหม่คือ  1  2  3  4  5

รอบที่ 4 เอาตัวเลขตำแหน่งที่ 4 เป็นหลัก(เลข 4) นำไปเปรียบเทียบกับค่าที่เหลืออีกหนึ่งตัว ซึ่งค่าที่เหลือไม่มีค่าน้อยกว่าตัวเลขตำแหน่งที่ 4 ก็ไม่ต้องมีการสลับตำแหน่ง

ผลลัพธ์ที่ได้จากการเรียงลำดับใหม่คือ  1  2  3  4  5

เขียนใหม่เพื่อให้ดูต่อเนื่องดังนี้

2  5  1  4  3        // เริ่มต้น

1  5  2  4  3        // หลังจากผ่านรอบที่ 1

1  2  5  4  3        // หลังจากผ่านรอบที่ 2

1  2  3  4  5        // หลังจากผ่านรอบที่ 3

1  2  3  4  5        // หลังจากผ่านรอบที่ 4

โปรแกรม Selection Sort เพื่อเรียงลำดับจาก น้อยไปหามาก สำหรับเครื่องคิดเลข Casio Fx-5800P

*****************************************

แต่ถ้าต้องการเรียงลำดับจาก มากไปหาน้อย ให้แก้บรรทัดที่ 18 จาก

If Z[K]<Z[M]↵

แก้ไขเป็น

If Z[K]>Z[M]↵

*****************************************

ก่อนจะอธิบายการทำงานของโปรแกรมขออธิบายเรื่องการสลับค่าตัวแปรก่อน 

การสลับค่าตัวแปร (Swapping)

เราสามารถสลับค่าตัวแปรสองตัวได้ด้วยวิธีการ Swap โดยใช้ตัวแปรอื่นเพื่อพักข้อมูลก่อน เช่น 

ให้ทำการสลับค่าตัวแปร A=25 และ B=42 

ในที่นี้เราจะใช้ตัวแปร X ในการพักข้อมูล โดยวิธีดังนี้

เริ่มต้น A=25, B=42, X=ยังไม่กำหนดค่า

ให้ X=A        // A=25, B=42, X=25

ให้ A=B        // A=42, B=42, X=25

ให้ B=X        // A=42, B=25, X=25


เท่านี้ก็สามารถสลับค่าตัวแปร  A กับ B ได้แล้ว ส่วน X เป็นแค่ตัวแปรพักข้อมูล

การทำงานของโปรแกรม

การทำงานหลักๆ ของโปรแกรมอยู่ที่บรรทัดที่ 15 ถึง 27 ซึ่งเป็นการเรียงลำดับชุดตัวเลขที่ป้อนเข้ามา โปรแกรมเป็นลักษณะลูปซ้อนลูป โดยมี

- ลูป J อยู่ด้านนอกเพื่อเข้าถึงตำแหน่งที่ใช้เป็นตัวตั้งในการเรียงลำดับ(จากตัวอย่างคือตำแหน่งที่ 1, 2, 3, 4)

- ลูป K อยู่ด้านในเพื่อเข้าถึงตัวเลขในตำแหน่งที่เหลือเพื่อนำมาเปรียบเทียบหาตำแหน่งที่มีค่าน้อยที่สุด

สองลูปนี้ทำงานสอดคล้องกันโดย

รอบ J=1, K จะเข้าถึงข้อมูลตำแหน่งที่ 2 ถึง 5 เพื่อเปรียบเทียบหาค่าน้อยที่สุด

รอบ J=2, K จะเข้าถึงข้อมูลตำแหน่งที่ 3 ถึง 5 เพื่อเปรียบเทียบหาค่าน้อยที่สุด

รอบ J=3, K จะเข้าถึงข้อมูลตำแหน่งที่ 4 ถึง 5 เพื่อเปรียบเทียบหาค่าน้อยที่สุด

รอบ J=4, K จะเข้าถึงข้อมูลตำแหน่งที่ 5 เพื่อเปรียบเทียบหาค่าน้อยที่สุด

หลังจากครบสี่รอบนี้ชุดข้อมูลก็จะถูกเรียงลำดับโดยสมบูรณ์

- ตัวแปร N คือจำนวนชุดข้อมูลทั้งหมดเพื่อใช้ประกาศ Array

- ตัวแปร M ใช้สำหรับเก็บค่าตำแหน่ง(ค่า index ของ Array)ของตัวเลขที่มีค่าน้อยที่สุดในแต่ละรอบ

- ตัวแปร X ใช้เป็นตัวแปรสำหรับพักเพื่อสลับค่าตัวเลข

ตัวอย่างทดสอบโปรแกรม

ต้องการเรียงลำดับข้อมูลจากตัวเลขชุด 10 จำนวนดังนี้  7, 19, 51, 40, 23, 2, 69, 33, 105, 19

ป้อนข้อมูล

NUMBER = 10

Z[1] = 7

Z[2] = 19

Z[3] = 51

Z[4] = 40

Z[5] = 23

Z[6] = 2

Z[7] = 69

Z[8] = 33

Z[9] = 105

Z[10] = 19

 

ตามภาพ

ผลลัพธ์

Z[1] = 2

Z[2] = 7

Z[3] = 19

Z[4] = 19

Z[5] = 23

Z[6] = 33

Z[7] = 40

Z[8] = 51

Z[9] = 69

Z[10] = 105

 

ตามภาพ

จบบท