มันไม่ง่ายเลยที่จะเข้าใจ Sorting Algorithm ep.2
ความเดิมตอนที่แล้ว…
จากที่เราได้ทำความรู้จัก sorting algorithm เราก็ได้รู้ว่าการ sort หรือการเรียงลำดับข้อมูลมีอยู่หลายแบบ ซึ่งแต่ละแบบก็จะมีประสิทธิภาพที่ต่างกันออกไปตามรูปแบบข้อมูลที่มี
ซึ่งใน episode ที่สองนี้เราจะเริ่มจากวิธีการที่มีหลักการคิดง่าย ๆ ก่อน เหมือนกับเราหัดเดินตอนเด็ก ๆ นั่นแหละพอเริ่มเก่งแล้วค่อยกระโดดโลดเต้น คิดอะไรแผลง ๆ ได้ตามที่เราต้องการ
เจ้าตัวแรกนี้นั่นก็คือ Bubble sort นั่นเอง เป็นอย่างไร แง้มลงไปดูข้างล่างเลยครับ
Bubble sort
เจ้า Bubble sort ตัวนี้หนึ่งในวิธีที่เป็นพื้นฐานของการเรียงข้อมูลในหลาย ๆ แบบ เนื่องด้วยความที่เป็นวิธีที่มีแนวคิดที่ง่ายและไม่ซับซ้อนมาก จึงเป็นวิธีที่เราควรจะศึกษาเป็นตัวแรกเพื่อทำความคุ้นเคยกับวิถีชีวิตของแก๊ง sorting พวกนี้
โดย Bubble sort ถ้าแปลเป็นภาษาไทยเราก็คือ การเรียงลำดับแบบฟอง(bubble แปลกันตามตัวเลย ฟองสบู่) ซึ่งชื่อนี้ก็มีที่มาจากตัวฟองสบู่นี่แหละ (โอ หิวโค้ก…)
Bubble sort ก็มีแนวคิดที่ค่อยๆนำข้อมูลที่มีค่าน้อย ๆ ลอยขึ้นมาเรื่อย ๆ ตามลำดับเหมือนกับฟองสบู่ที่พยายามที่จะลอยขึ้นมาบนผิวน้ำยังไงล่ะ
บางทีก็อาจจะเรียก Bubble sort ว่า Sinking sort(การเรียงแบบจม) ก็ได้นะ พอมีส่วนลอยขึ้นมาก็ต้องมีส่วนจมแค่เรามองมุมกลับปรับมุมมองแค่นั้นเอง (ดูให้มึนทำไมก็ไม่รู้)
วิธีการคิดเจ้าฟองสบู่เจ้าปัญหา
ก่อนอื่นเราลองสมมติแถวข้อมูลขึ้นมาซักแถวหนึ่ง แล้วเราลองมองแบบแนวตั้งตามธรรมชาติฟองสบู่กัน(จะมองเป็นแนวนอนก็ได้ตามสะดวกครับ)
เราจะเริ่มทำการเรียงแบบ Bubble sort กัน
ขั้นแรก : เราจะเช็คกันไปทีละตัว โดยเราจะพิจารณาตัวปัจจุบันกับตัวถัดไป
ขั้นสอง : พิจารณาว่า ตัวปัจจุบันมีค่ามากกว่าตัวถัดไปหรือไม่ ถ้าใช่ให้สลับกัน
จากภาพด้านล่าง เราจะเห็นว่า ตัวปัจจบัน(2) ยังไม่ค่าน้อยกว่า ตัวถัดไป(5) เราจึงปล่อยไปตามยะถากรรมของมัน
ขั้นสาม : เลื่อนตัวปัจจุบันไปที่ตัวถัดไป แล้วขยับตัวถัดไปไปอีกแล้วทำขึ้นตอนที่ 1 และ 2 ต่อจนหมดแถว
จะเห็นว่าตัวปัจจุบัน(5) มีค่ามากกว่า ตัวถัดไป(4) จึงเกิดการสลับกัน
สลับ!!!
มาเช็คกันต่อ
พอเราทำจนหมดแถวถือว่าเสร็จ1รอบ เราจะเห็นว่าในแต่ละรอบตัวที่มากที่สุดก็จะถูกย้ายไปข้างล่างเรื่อย ๆ ดังนั้นถ้าเราจะทำให้เรียงกันให้หมดก็ต้องทำรอบอย่างมากที่สุดตามจำนวนข้อมูลในแถวนั้นจนเรียงกันอย่างสมบูรณ์
มาเขียนโปรแกรมสำหรับ Bubble sort กันเถอะ
ตัวอย่างการเขียนโปรแกรม (สำหรับภาษา C)
จาก code ด้านบนจะเห็นว่าใน function bubble_sort จะมีการวนลูปอยู่ 2 ลูปโดยลูป j จะทำการวนลูปสำหรับ 1 รอบการเรียง โดยมีจุดเริ่มต้นตั้งแต่ตัวแรกจนถึงตัวก่อนสุดท้ายตามขั้นตอนที่ 1–3 และลูป i ก็จะวนขั้นตอนที่ 1–3 จนข้อมูลมีการเรียงกันอย่างสมบูรณ์
ผลลัพธ์ที่ได้จะออกมาเป็น
Unsorted data : 5 3 4 6 2 7
Sorted data : 2 3 4 5 6 7เพื่อน ๆ พี่ ๆ น้อง ๆ ที่อยากจะทราบการทำงานเพิ่มเติมแนะนำให้ลอง แสดงผลการทำงานในแต่ละรอบ โดยสั่ง print ในลูป i เพื่อเพิ่มความเข้าใจได้ครับ
How good is Bubble sort? มันดียังไง
ก็ตั้งแต่ที่เราลากยาวมาถึงจุด ๆ นี้ก็คงจะเดาออกแล้ว(สปอยมาตั้งเยอะ) ก็คงรู้กันแล้วว่าวิธีการนี้เป็นวิธีการที่มีความซับซ้อนน้อยที่สุด เนื่องจากเรามีเพียงข้อมูลแถวเดียวและเปรียบเทียบทีละ2ตัวเรื่อย ๆ แต่ความง่ายก็ใช่ว่าจะดีเสมอไป
Bubble sort จะเป็นวิธีที่มีประสิทธิภาพสูงเมื่อข้อมูลที่เราได้มีการเรียงกันเกือบจะสมบูรณ์แล้ว การสลับกันของข้อมูลจึงต่ำทำให้การทำงานเร็วขึ้น แต่นรกจะเกิดขึ้นเมื่อข้อมูลของเราเรียงกันแบบสลับกันโดยสิ้นเชิง
ลองจินตนการดูว่าเรามีข้อมูลที่เราเรียงมากไปน้อย แล้วเราต้องการเรียงจากน้อยไปมากสิ แสดงว่ามันต้องมีการสลับกันทุก ๆ ครั้งแน่นอน ซึ่งจะส่งผลให้จำนวนการทำงานจะเพิ่มขึ้นเป็นเท่าตัวตามจำนวนของข้อมูลหรือประมาณ O(n²) (เดี๋ยวจะอธิบายเพิ่มเติมอีกทีครับ)
ถ้าข้อมูลมีจำนวนน้อยๆก็คงจะไม่มีผลรุนแรง แต่สมมติว่าเราต้องการให้เรียงอายุคนไทยทั้งประเทศด้วย bubble sort คงจะได้ผลอีกทีชาติหน้าแน่นอน
เอาให้พอปวดหัวกันเท่านี้ แล้วเราจะมาปวดหัวกันต่อด้วยวิธีอื่นที่ซับซ้อนกว่านี้ในครั้งหน้า
