มันไม่ง่ายเลยที่จะเข้าใจ Sorting Algorithm ep.3
ความเดิมตอนที่แล้ว
จากตอนที่แล้วเรารู้จักวิธี Sorting ไปหนึ่งแบบแล้ว(ง่ายที่สุดแล้วด้วย) ตอนนี้เราจะลองดูตัวง่ายๆอีกสักตัวนึงซึ่งเราจะมาเจาะลึกเจ้า Sorting ที่มีชื่อว่า Selection sort นั่นเอง
ไม่ต้องพูดพร่ำทำเพลงให้มากความ ลองก้มลงไปดูเลยครับ
Selection Sort
เป็นอีกหนึ่งวิธีของการเรียงลำดับข้อมูลที่มีวิธีการคิดที่ไม่ซับซ้อนมาก คล้ายๆกับ Bubble sort นั่นแหละ
ซึ่ง Selection sort ก็แปลมาจากคำว่า Selection หรือก็คือ การเลือกนั่นเอง แสดงว่าการเรียงแบบนี้จะมีวิธีคิดหลักคือเลือกข้อมูลมาเรียงทีละตัวยังไงล่ะ
วิธีการคิดแบบ Selection ๆ
ก่อนจะทำอาหารก็ต้องมีวัตถุดิบ การเรียงข้อมูลก็เหมือนกันก็ต้องมีข้อมูลดิบ(กำลังหิว nugget พอดิบพอดี)
มาเริ่มคิดกันเถอะ
ขั้นแรก : หาข้อมูลที่มีค่าน้อยที่สุดในแถวก่อน โดยเปรียบเทียบทีละตัว
วิธีการหาค่าที่น้อยที่สุดหลาย ๆ ท่านหลาย ๆ คนคงจะคุ้นเคยกันมาบ้าง แต่จะขออธิบายซักเล็กน้อย เป็น extra สำหรับจอมยุทธฝึกหัด
เราจะมีป้ายๆหนึ่ง ที่จะบอกตัวที่มีค่าที่น้อยที่สุด แล้วเราก็จะเอาแต่ละตัวของแถวข้อมูลมาเปรียบเทียบกับป้าย หากค่าไหนที่มีค่าน้อยกว่าป้ายแล้ว ป้ายก็จะเอาค่านั้นมาแทน
จะเห็นว่าเราให้ป้ายนี้เก็บค่าตัวแรก(ตัวที่ 0)ไว้ก่อนเป็นค่าเริ่มต้น
แล้วเราจะมาเริ่มเทียบกันไปเรื่อยๆ
จากภาพด้านบนเราจะเห็นว่า ตัวที่ 1(มีค่า 5) ไม่ได้น้อยกว่าตัวที่ 0(มีค่า2) ป้ายจึงยังคงค่า 2 ไว้
เมื่อเราเทียบๆไปเรื่อยๆจะเห็นว่า มีตัวที่ 5 (มีค่า 1 ) มีค่าน้อยกว่า ค่าตัวที่ 0 จริงป้ายจึงนำค่าจองตัวที่ 5 เข้าไปใส่ในป้ายแทน
ใส่เข้าไป!!
ดังนั้นแล้วเราจะได้ค่าที่น้อยที่สุดในแถว นั่นก็คือ 1 นั่นเอง
ขั้นที่สอง : เมื่อเราได้ค่าที่น้อยที่สุดในแถวเราก็เอามันไปใส่ในตัวแรกสุดของแถวเลย เพราะมันตัวที่น้อยที่สุดของแถวไง โดยการสลับตัวที่มีค่าน้อยที่สุดกับ ตัวแรกซะ
เราก็จะถือว่าเสร็จ 1 รอบการสลับ แล้วเราก็จะตัดตัวแรกออกไปเพราะมันอยู่ถูกที่ถูกทางแล้ว
ขั้นที่สาม : ทำซ้ำจนกว่าจะเสร็จสมบูรณ์
ทำความเข้าใจเสร็จแล้วก็มาดูการเขียนโปรแกรมกันต่อ
จะเห็นว่า ป้ายที่เราสมมติขึ้นมานั่นคือ ตัวแปร min_index ด้วยเป้าหมายให้เราพยายามเก็บตำแหน่งของตัวที่น้อยที่สุดเอาไว้ แทนที่จะเก็บค่ามันแทน เพื่อทำให้การสลับข้อมูลของเรามีความสะดวกยิ่งขึ้น
ผลการทำงานก็จะได้ดังนี้
Unsorted data : 5 3 4 6 2 7
Sorted data : 2 3 4 5 6 7จากที่เห็นการเรียงแบบนี้จะเห็นว่า มีวิธีคิดที่ยังไม่ยากมาก และอาจจะเป็นวิธีคิดที่เราจินตนาการง่ายด้วย (ส่วนตัวผู้เขียนคิดว่าวิธีนี้มีพื้นฐานการคิดง่ายกว่าแบบฟองด้วย)แต่วิธีนี้ก็ยังไม่ใช่วิธีที่มีประสิทธิภาพพออีก
เนื่องจากเราต้องมีการเปรียบเทียบค่าที่น้อยที่สุดซึ่ง เราจะต้องเปรียบเทียบเป็นเท่าตัวอีกหากมีข้อมูลเยอะๆ ก็ยิ่งทำให้ตัวคอมพิวเตอร์ที่ใช้การเรียงแบบนี้ทำงานนานและหนักเข้าไปอีก
สำหรับตอนนี้เราเพิ่มความปวดหัวเล็กน้อย ด้วยวิธีการง่ายๆ ตอนหน้าอาจจะมีวิธีหฤโหดรอเราอยู่ ติดตามต่อตอนหน้าครับ
