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

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

การเรียงลำดับคืออะไร
หลักการคร่าวๆ ในการเรียงลำดับนั้น ก็คือ การนำข้อมูลในที่มีอยู่ในชุดสักชุดนึง มาจัดการเรียงให้มันเข้าที่เข้าทางมีลำดับ อย่างใดอย่างหนึ่ง เช่น เรียงจากมากไปน้อย (Decreasing Order), เรียงจากน้อยไปมาก (Increasing Order), เรียงตามลำดับตัวอักษร (Lexicograpical Order) เป็นต้น ตัวอย่างง่ายๆ ก็เช่น สมมติผมมีชุดข้อมูลคือ

{21, 3, 10, 25, 34, 14} (ขออนุญาตใช้สัญลักษณ์เซต แทนชุดข้อมูลนะครับ แม้มันจะไม่ได้มีคุณสมบัติเหมือนเซตก็ตาม)

และสมมติว่า ผมต้องการเรียงลำดับข้อมูลชุดนี้ จากน้อยไปมาก คำตอบก็คือ

{3, 10, 14, 21, 25, 34}

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

แต่ก่อนอื่น เรามาดูก่อนครับว่า ลักษณะคำตอบของปัญหาการเรียงลำดับนี้ มันต่างหรือเหมือนกับชุดข้อมูลที่เป็นโจทย์อย่างไร

เห็นชัดๆ ก็คือ ลำดับของข้อมูลแต่ละตัวระหว่างชุดโจทย์กับชุดคำตอบ มันต่างกัน (แต่ไม่จำเป็นเสมอไปนะครับ ถ้าโจทย์มันดันเรียงลำดับไว้อยู่แล้ว คำตอบก็คือโจทย์นั่นเอง) กล่าวคือชุดคำตอบจะเรียงลำดับจากน้อยไปมากแล้ว
ส่วนที่เหมือนกันคือจำนวนข้อมูลและข้อมูลแต่ละตัวในชุดข้อมูลของโจทย์กับคำตอบนั้นเหมือนกัน ถ้าพูดภาษาคณิตศาสตร์ก็คือ ชุดข้อมูลคำตอบนั้นเป็นการเรียงสับเปลี่ยน (permutation) แบบหนึ่งของข้อมูลในชุดนั่นเอง
สำหรับวันนี้จะขออธิบายอัลกอริทึมแบบต่างๆ โดยคร่าวๆ ก่อนครับ ขอเน้นตรงนี้ก่อนว่า แม้บางทีชื่อวิธีจะเหมือนกัน แต่ในหลายๆ ตำรา หลายๆ แหล่งข้อมูล ก็เขียนไว้ไม่เหมือนกันนะครับ เพราะฉะนั้นถ้าไปอ่านเจอที่อื่นแล้วไม่เหมือนก็อย่าว่ากันนะครับ แล้วก็ในที่นี้ ขอกล่าวเฉพาะเรียงจากน้อยไปมากนะครับ

อัลกอริทึมการเรียงลำดับแบบต่างๆ
     Bubble Sort
     Selection Sort
     Insertion Sort
     Merge Sort
     Quick Sort
     Bucket Sort
     Bubble Sort

วิธีเรียงลำดับแบบนี้ คิดค้นได้ในช่วงแรกๆ ของการเจริญก้าวหน้าของวิทยาการคอมพิวเตอร์ (แน่นอนว่าประสิทธิภาพมันย่อมไม่ดีที่สุดแน่ๆ) หลักการของมันก็คือการเอาข้อมูลที่ติดกันในชุดมาเปรียบเทียบกันทีละคู่ ถ้าตัวแรกมีค่ามากกว่าตัวหลัง ก็สลับที่ (ในทางวิทยาการคอมฯ เค้าใช้คำว่า swap) กันซะ ทำเช่นนี้ไปเรื่อยๆ ถ้าลองจินตนาการดู จะพบว่า ถ้าเริ่มจากข้อมูลตัวแรก ไปจนจบชุดข้อมูล ข้อมูลตัวที่มากที่สุดในบรรดาข้อมูลทั้งชุด จะถูกเลื่อนไปอยู่หลังสุด (นั่นแปลได้ว่าเราได้เรียงลำดับข้อมูลชุดนี้ไปหนึ่งตัวแล้ว) ทำแบบนี้ซ้ำไปเรื่อยๆ จนกว่าจะไม่มีการ swap อีกแล้ว ก็สรุปได้ว่ามันเรียงลำดับกันทั้งชุดแล้ว วิธีนี้เปรียบเสมือนการทำให้ “ฟอง” ข้อมูลลอยขึ้นๆ ไปเรื่อยๆ ในตำแหน่งที่ควรเป็น ซึ่งเป็นที่มาของชื่อของมันนั่นเอง จะเห็นว่าวิธีนี้ค่อนข้างตรงไปตรงมา แต่ค่อนข้างเสียเวลาทีเดียว ภายหลังจะมีวิธีที่มีประสิทธิภาพกว่านี้แนะนำให้ดูครับ

     Selection Sort
ส่วนตัวแล้ว ผมรู้สึกว่าวิธีเรียงลำดับแบบนี้ มันค่อนข้างจะธรรมชาติที่สุด (เท่าที่จำความได้ ถ้ามีคนบอกให้เรียง ไอ้นู่นไอ้นั่นให้หน่อย ผมก็ใช้วิธีนี้ก่อนนะครับ) ก็คือการเรียงแบบ “เลือก” นั่นเอง กล่าวคือ ให้เลือกตัวที่มีค่าน้อยที่สุดในชุด มาสลับกับข้อมูลตัวแรกในขณะนั้น ก็จะได้ว่าตอนนี้ข้อมูลค่าน้อยสุด อยู่ช่องแรกแล้ว ถัดมาเราก็ทำแบบเดิม แต่คราวนี้หาตัวน้อยที่สุดอันดับสอง มาสลับกันกับตัวที่สองในชุดขณะนั้นแทน เท่ากับว่าตอนนีน้ เราได้ชุดข้อมูลที่เรียงแล้ว สองตัว ทำไปเรื่อยๆ จนจบชุดข้อมูล จะได้ว่า ข้อมูลทั้งหมดเรียงลำดับตามต้องการ วิธีนี้ก็จะคล้ายๆ กับวิธีก่อน ประสิทธิภาพที่มีก็จะคล้ายๆ กันเช่นกันครับ

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

     Merge Sort
วิธีนี้เป็นวิธีแรกในบรรดาที่กล่าวมาทั้งหมดที่สามารถทำงานได้ดีกับข้อมูลที่มีจำนวนมากๆ (เป็นเหตุผลในเรื่องของประสิทธิภาพที่ผมกล่าวไว้ข้างต้นว่าจะไม่ขอยุ่งในตอนนี้) หลักการของมันมีพื้นฐานอยู่บนหลักการ “แบ่งแยกและเอาชนะ” (divide and conquer) กล่าวคือในเมื่อปัญหาขนาดใหญ่มันยากและยุ่ง เราก็แก้ปัญหาย่อยๆ เล็กๆ ซะก่อนแล้วนำคำตอบเหล่านั้นมารวมกันเป็นคำตอบของปัญหาใหญ่ เมื่อประยุกต์เข้ากับปัญหาของการเรียงลำดับ ถ้าเราเรียงลำดับชุดข้อมูลขนาดเล็กที่สุด (2 ตัว) ก่อน แล้วเอาชุดข้อมูล 2 ตัวมาเทียบกับชุดข้อมูล 2 ตัวข้างๆ แล้วเรียง จะได้ชุดข้อมูล 4 ตัวที่เรียงแล้ว ทำเช่นนี้ไปเรื่อยๆ (8 ตัว, 16 ตัว, ฯลฯ) ในที่สุดเราก็จะได้ชุดข้อมูลทั้งชุดที่เรียงลำดับเรียบร้อยแล้ว การเรียงแล้วรวมนั้นเป็นที่มาของชื่อของมันคือการ “ผสาน” นั่นเอง

     Quick Sort
เห็นชื่อนี้แล้ว หลายๆ คนคงคิดว่า มันจะต้องเร็วแน่เลย ซึ่งก็เป็นไปตามนั้นครับ มันเร็วจริงๆ แต่ถามว่าเร็วสุดหรือยัง อันนี้ขึ้นกับการประยุกต์ใช้งานซึ่งแตกต่างกันไปนะครับ ผมก็ไม่กล้าการันตีเหมือนกันว่ามันเร็วสุดในทุกสถานการณ์ แต่มันเร็วขนาดที่ นักสร้างภาษาโปรแกรมหลายๆ เจ้าเอาไปรวมเป็นไลบรารี่ให้คนเขียนใช้ (เช่น qsort() ของภาษา C) วิธีของมันนั้นก็มีพื้นฐานอยู่บนหลักการแบ่งแยกและเอาชนะคล้ายๆ กับ Merge Sort ครับ แต่วิธีการมองและแก้ปัญหาจะต่างกัน กล่าวคือ วิธีนี้จะเลือกข้อมูลจุดศูนย์กลาง (pivot) มาตัวหนึ่ง จากนั้นก็ไล่เทียบข้อมูลในชุดทั้งชุด ตัวไหนมีค่าน้อยกว่าข้อมูล pivot ที่ว่านี้ ก็ให้ไปอยู่ทางซ้าย ตัวไหนมากกว่าก็ให้ไปอยู่ทางขวา (เรียกได้อีกแบบว่าเป็นการแบ่ง (partition) นั่นเอง) เสร็จแล้วก็แก้ปัญหาย่อยๆ (นั่นคือการเรียงลำดับของชุดข้อมูลย่อยทางซ้าย และชุดข้อมูลย่อยทางขวา) จะเห็นว่า ถ้าชุดข้อมูลทางซ้ายและทางขวาเรียงเรียบร้อยแล้ว ถ้าเราเอาข้อมูลมาต่อกันตรงๆ ก็จะได้ชุดข้อมูลทั้งชุดที่เรียงลำดับเรียบร้อย วิธีนี้แม้จะเร็วในทางปฏิบัติแต่ก็มีประเด็นที่ต้องคิดคือเรื่องของการเลือก pivot ที่ดี เพราะถ้าเลือกไม่ดี อาจจะไปเลือกถูกตัวที่มีค่าน้อยสุด (กลายเป็นว่าไม่มีค่าที่น้อยกว่ามันแล้ว พอแบ่งข้อมูล ก็เลยมีแต่ข้อมูลที่อยู่ทางขวามัน แทนที่เราจะได้ปัญหาเล็กลงครึ่งหนึ่ง สองปัญหา กลายเป็นต้องแก้ปัญหาเล็กลงแค่ตัวเดียวปัญหาใหม่) ถ้าเป็นเช่นนั้น จะทำให้การเรียงแบบนี้ แย่ได้พอๆ กับการเรียงลำดับแบบต้นๆ ที่กล่าวมาเลยทีเดียว

     Bucket Sort
ตามชื่ออีกแล้วครับ วิธีนี้เราจะสมมติว่ามี “ตะกร้า” หรือ “กระบะ” แล้วแต่ใครจะเรียกครับ ข้อมูลในชุดที่จะมาเรียงโดยใช้วิธีนี้ต้องมีสมบัติอย่างหนึ่งครับ คือมันจะต้องสามารถแบ่งแยกและใส่ลงตะกร้าสมมติได้ เช่นต้องการจะเรียงข้อมูลที่มีแต่ตัวอักษรภาษาอังกฤษ a, b, …, z ตะกร้าพวกนั้นก็จะคือตะกร้าที่แทนตัวอักษรทั้ง 26 ตัวนั่งเอง หลักการก็คือนำข้อมูลที่มีในชุดใส่ลงไปในตะกร้าสมมติดังกล่าว จากนั้น ก็แค่อ่านข้อมูลจากแต่ละตะกร้า จากตัวแรก (ในที่นี้คือ a) ไปจนถึงตัวสุดท้าย (คือ z) ตะกร้าไหนมีข้อมูลอยู่ก็อ่านมันขึ้นมาแล้วใส่ในชุดข้อมูลคำตอบไปเรื่อยๆ สุดท้ายก็จะได้ชุดข้อมูลใหม่ที่เรียงลำดับเรียบร้อยครับ

ความจริงแล้ว ยังมีวิธีเรียงลำดับอีกหลายวิธีที่ไม่ได้กล่าวถึงในที่นี้เพราะเกี่ยวข้องกับหัวข้ออื่นๆ อีกมาก กลัวว่าใส่ลงมาในที่นี้ แล้วจะอ่านเข้าใจยากอยู่ดี เช่น shell sort, heap sort เป็นต้น ไว้โอกาสหน้าจะนำมาแบ่งปันเล่าสู่กันฟังอีกครับ