Sorting

การเรียงลำดับ ( Sorting)

   Input 7 8 5 4 2 1 3 9  →   Output 1 2 3 4 5 7 8 9

มีอยู่ด้วยกันหลายประเภทเช่น
-เลือก Selection sort
-ฟอง : Bubble sort
-แทรก : Insertion sort
-เชลล : Shell sort
-ผสาน : Merge sort
-เร็ว : Quick sort

การเรียงลำดับแบบเลือก (selection sort)
   ทำการเลือกข้อมูลมาเก็บในตำแหน่งที่ ข้อมูลนั้นควรจะอยู่ทีละตัว โดยทำการค้นหาข้อมูลนั้นในแต่ละรอบแบบเรียงลำดับถ้าเป็นการเรียงลำดับจากน้อยไปมาก
1. ในรอบแรกจะทำการค้นหาข้อมูลตัวที่มีค่าน้อยที่สุดมาเก็บไว้ที่ตำแหน่งที่ 1
2. ในรอบที่สองนำข้อมูลตัวที่มีค่าน้อยรองลงมาไปเก็บไว้ที่ตำแหน่งที่สอง
3. ทำเช่นนี้ไปเรื่อย ๆ จนกระทั่งครบทุกค่าในที่สุดจะได้ข้อมูลเรียงลำดับจากน้อยไปมากตามที่ต้องการ

การเรียงลำดับแบบฟอง (Bubble Sort)

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

การเรียงลำดับแบบแทรก (insertion sort)

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

การเรียงลำดับแบบเชลล ( Shell sort )

   Shell Sort มันใช้วิธีการแบ่งออกเป็นกลุ่ม ๆ ตามจำนวนที่กำหนด แล้วเรียงข้อมูลในแต่ละกลุ่มนั้น เมื่อเรียงเสร็จก็นำแต่ละกลุ่มมา recombined กันเหมือนเดิม จากนั้นก็ลดขนาดจำนวนที่แบ่งกลุ่มลง เช่น ตอนแรกแบ่งเป็น 5 กลุ่ม พอ recombined เสร็จแล้วก็สั่งให้แบ่งเป็น 3 กลุ่ม ซึ่งสุดท้ายแล้วจะต้องแบ่งเป็น 1 กลุ่ม (ซึ่งหมายถึงเรียงตาม individual data element) เราเรียกการแบ่งกลุ่มพวกนี้ว่า increment โดยการที่เราจะเลือกว่าจะใช้ increment เท่าไหร่นั้น หลักการของมันก็คือเลขที่เราเลือกควรจะเป็นจำวนเฉพาะ เช่น 7, 5, โดยที่ลำดับ increment สุดท้ายจะต้องเป็น 1 เสมอ และการ sort เมื่อแยกกลุ่มออกมาใช้จะใช้วิธี insertion sort เช่นให้เรียงข้อมูล 81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15 จากน้อยไปมาก โดยที่กำหนดให้ใช้ increment 5, 3 และ 1
ครั้งแรกเราจะทำการแบ่ง increment 5 เมื่อแบ่งเสร็จแล้วให้เราเรียงข้อมูลในแต่ละกลุ่มนั้น ๆ (5 sorted) หลังจากเรียงข้อมูลในแต่ละกลุ่มเสร็จแล้วให้เรา recombined มันกลับมาเหมือนเดิม จะได้ดังรูปนี้

เมื่อทำ increment 5 เสร็จแล้ว เราก็ต้องมาทำ increment 3 ต่อ ซึ่งก็คือแบ่งตัวเลขออกเป็น 3 กลุ่มแล้วก็เรียงข้อมูลในแต่ละกลุ่ม (3 sorted) เสร็จแล้วก็ทำการ recombined มันเหมือนเดิม จะได้รูปนี้

เสร็จแล้วเราก็ทำ increment 1 ซึ่งก็คือการเรียงกันแบบ individual element จะได้ดังนี้

การเรียงลำดับแบบผสาน ( Merge sort )

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

การเรียงลำดับแบบเร็ว (quick sort)
   เป็นวิธีการเรียงลำดับที่ใช้เวลาน้อยเหมาะสำหรับข้อมูลที่มีจำนวนมากที่ต้องการความรวดเร็วในการทำงาน วิธีนี้จะเลือกข้อมูลจากกลุ่มข้อมูลขึ้นมาหนึ่งค่าเป็นค่าหลัก แล้วหาตำแหน่งที่ถูกต้องให้กับค่าหลักนี้ เมื่อได้ตำแหน่งที่ถูกต้องแล้ว ใช้ค่าหลักนี้เป็นหลักในการแบ่งข้อมูลออกเป็นสองส่วนถ้าเป็นการเรียงลำดับจากน้อยไปมาก ส่วนแรกอยู่ในตอนหน้าข้อมูล ทั้งหมดจะมีค่าน้อยกว่าค่าหลักที่เป็นตัวแบ่งส่วนอีกส่วนหนึ่งจะอยู่ในตำแหน่งตอนหลังข้อมูลทั้งหมด จะมีค่ามากกว่าค่าหลัก แล้วนำแต่ละส่วนย่อยไปแบ่งย่อยในลักษณะเดียวกันต่อไปจนกระทั่งแต่ละส่วนไม่สามารถแบ่งย่อยได้อีกต่อไปจะได้ข้อมูลที่มีการเรียงลำดับตามที่ต้องการถ้าเป็นการเรียงลำดับจากน้อยไปมากการเปรียบเทียบเพื่อหาตำแหน่งให้กับค่าหลักตัวแรกเริ่มจากข้อมูลในตำแหน่งแรกหรือสุดท้ายก็ได้ ถ้าเริ่มจากข้อมูลที่ตำแหน่งที่ 1เป็นค่าหลัก พิจารณาเปรียบเทียบค่าหลักกับข้อมูลในตำแหน่งสุดท้าย ถ้าค่าหลักมีค่าน้อยกว่าให้เปรียบเทียบกับข้อมูลในตำแหน่งรองสุดท้ายไปเรื่อย ๆ จนกว่าจะพบค่าที่น้อยกว่าค่าหลักแล้วให้สลับตำแหน่งกันหลังจากสลับตำแหน่งแล้วนำค่าหลักมาเปรียบเทียบกับข้อมูล ในตำแหน่งที่ 2, 3,ไปเรื่อย ๆ จนกว่าจะพบค่าที่มากกว่าค่าหลักสลับตำแหน่งเมื่อเจอข้อมูลที่มากกว่าค่าหลัก ทำเช่นนี้ไปเรื่อย ๆ จนกระทั่งได้ตำแหน่งที่ถูกต้องของค่าหลักนั้น ก็จะแบ่งกลุ่มข้อมูลออกเป็นสองส่วน ส่วนแรกข้อมูลทั้งหมดมีค่าน้อยกว่าค่าหลักและส่วนที่สองข้อมูลทั้งหมดมีค่ามากกว่าค่า