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

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

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

รูป1-1

ประสิทธิภาพการทำงานของ การเรียงลำดับแบบ bubble

ประสิทธิภาพการทำงานเมื่อเกิดกรณีแย่สุด O(n²)

ประสิทธิภาพการทำงานเมื่อเกิดกรณีทั่วไป O(n²)

ประสิทธิภาพการทำงานเมื่อเกิดกรณีดีที่สุด O(n)

Bubble sort source code

รูป1-2

บรรทัดที่ 6 : สร้างเมท็อดชื่อ bubbleSort รับพารามิเตอร์เป็น อาร์เรย์หนึ่งมิติ (สร้างเป็นเมท็อดเดี๋ยวไวเรียก

ทดสอบทีหลัง)

บรรทัดที่ 8 : วนลูปที่หนึ่ง ลูปนี้จะคอยควบคุมให้การวนลูปเริ่มตั้งแต่ตัวแรกไปจนถึงตัวสุดท้าย โดยมีค่าเท่ากับ

ขนาดของอาร์เรย์ที่รับเป็นอินพุท

บรรทัดที่ 10 : วนลูปที่สอง ให้ลูปวนไปสุดที่ a.length-i-1 คือถ้าไม่มีการสลับให้ j ขยับได้แต่ต้องไม่เกิน i

บรรทัดที่ 12 : สร้างเงื่อนไข ถ้าตัวทางซ้าย a[j] มีค่ามากกว่าตัวทางขวา a[j+1] ให้สลับ

บรรทัดที่ 14 : การสลับสร้างตัวแปร t ขึ้นมา เอาข้อมูล a[j] ไปเก็บไว้ใน t ก่อน

บรรทัดที่ 15 : ทำการสลับโดยเอาข้อมูลของ a[j+1] มาใส่ a[j]

บรรทัดที่ 16 : เอาข้อมูลเดิมของ a[j] ที่อยู่ใน t มาใส่ a[j+1] เท่านี้การสลับก็เรียบร้อย

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

Selection sort พัฒนามาจาก Bubble sort แต่การสลับจะเป็นการเลือกและสลับเอาค่าที่มากที่สุดไปไว้ทางขวาของตาราง หรืออาจเลือกเอาค่าที่น้อยสุดมาไว้ทางซ้ายก็ได้ ถ้าเลือกเอาค่าที่มากที่สุดไปไว้ทางขวา ครั้งแรกตัวที่มากที่สุดจะไปอยู่ทางขวาสุด ครั้งที่สองตัวที่มากสุดรองลงมาก็จะไปอยู่ทางซ้ายของค่ามากสุด ครั้งต่อ ๆ ไปค่าที่มากอันดับต่อไปก็จะไปเรียงต่อของที่เรียงไว้แล้ว วนลูปทำไปเรื่อย ๆ จนกว่าจะหมดข้อมูล ถ้ามีข้อมูล n ตัว จะต้องทำการตรวจสอบ n-1 ครั้ง ดังนั้นจึงไม่เหมาะกับข้อมูลจำนวนมาก ๆ ๆ

รูป1-3

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

ประสิทธิภาพการทำงานของ การเรียงลำดับแบบ selection sort

ประสิทธิภาพการทำงานเมื่อเกิดกรณีแย่สุด O(n²)

ประสิทธิภาพการทำงานเมื่อเกิดกรณีทั่วไป O(n²)

ประสิทธิภาพการทำงานเมื่อเกิดกรณีดีที่สุด O(n²)

Selection sort source code

รูป1-4

บรรทัดที่ 22 : สร้างเมท็อด selectionSort รับพารามิเตอร์เป็นอาร์เรย์ a

บรรทัดที่ 24 : สร้างลูปสำหรับตรวจสอบตามขนาดของอาร์เรย์ที่รับเข้ามา

บรรทัดที่ 26 : สร้างตัวแปร last ไว้เก็บค่าตำแหน่งสุดท้าย โดยตำแหน่งสุดท้ายของ selection sort คือตำแหน่ง

ที่ต่อจากตำแหน่งของอันที่เรียงแล้วเลยต้องลบออกด้วย –i-1

บรรทัดที่ 27 : สร้างตัวแปร max_index ไว้เก็บค่าตำแหน่งของข้อมูลที่มีค่ามากที่สุด

บรรทัดที่ 28 : สร้างตัวแปร max เพื่อหาค่าที่มากที่สุด ตั้งค่าเป็น Integer.MIN_VALUE เพราะเผื่อไว้ไม่ว่าตัว

แรกที่เอาไปเทียบจะมีค่าเป็นอะไรก็จะได้มากกว่าตัวแปร max

บรรทัดที่ 29 : สร้างลูปอีกอันเพื่อให้วนตรวจหาค่าที่มากที่สุดในอาร์เรย์ที่รับเข้ามา

บรรทัดที่ 31-34 : ถ้าเจอ a ตำแหน่งที่ j ที่มีค่ามากกว่า max ให้ max เก็บ a[j] ส่วน max_index ก็เก็บตำแหน่งj

บรรทัดที่ 38-40 : ทำการสลับ max กับตำแหน่ง last

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

            Insertion Sort จะแบ่งส่วนของข้อมูลเป็นส่วนที่เรียงแล้วกับยังไม่เรียง หลังจากนั้นจะสุ่มหาข้อมูลหนึ่งตัวมาเปรียบเทียบในกลุ่มของข้อมูลที่เรียงแล้วว่าใส่ตัวที่ถูกสุ่มมาไว้ตรงไหนได้บ้าง

รูป1-5

            Insertion จะแบ่งส่วนของข้อมูลเป็นส่วนที่เรียงแล้วกับยังไม่เรียง ตัวอย่างในรูป บรรทัดแรกที่เรียงแล้วก็คือ 40 ต่อมา มาพิจารณา 15 น้อยกว่า 40 ก็เอาไปไว้ทางซ้าย ต่อมา พิจารณา 30 น้อยกว่า 40 แต่มากกว่า 15 ก็เอาไว้ตรงกลาง พิจารณาไปเรื่อย ๆ จนหมดจะได้ข้อมูลที่เรียงลำดับ

ประสิทธิภาพการทำงานของ การเรียงลำดับแบบ insertion

ประสิทธิภาพการทำงานเมื่อเกิดกรณีแย่สุด O(n²)

ประสิทธิภาพการทำงานเมื่อเกิดกรณีทั่วไป O(n²)

ประสิทธิภาพการทำงานเมื่อเกิดกรณีดีที่สุด O(n)

Insertion sort source code

รูป1-6

บรรทัดที่ 44 : สร้างเมท็อดชื่อ insertionSort รับอินพุทเป็นอาร์เรย์หนึ่งมิติ

บรรทัดที่ 46 : วนลูปตามขนาดของอาร์เรย์ โดยให้ i เริ่มที่ 1 ไปเรื่อยๆจนขวาสุด

บรรทัดที่ 48 : สร้างตัวแปร temp เก็บเป็นอาร์เรย์ในตำแหน่งของรอบที่วนลูป ซึ่งเป็นตัวที่เราสนใจ เพราะเราอยากรู้ว่าไอ่ตัวนี้มันจะอยู่ตำแหน่งไหนทางซ้ายมือที่เรียงแล้ว

บรรทัดที่ 50 : สร้างลูปอีกอันไว้โดยเริ่มจากตำแหน่งที่ก่อน i แล้วไล่ลดลงไปเรื่อยๆ เพื่อหาว่ามีตำแหน่งที่ temp จะไปแทรก

บรรทัดที่ 52 : (ลองนึกภาพว่ามีอาร์เรย์หนึ่ง  temp อยู่ทางขวามือของ j เสมอเพราะกำหนดให้ j อยู่หน้า temp หนึ่งตำแหน่ง แล้วไล่ลงไปทางซ้าย)ถ้าตำแหน่งที่ j มีค่าน้อยกว่า temp(ตัวที่เราต้องการว่ามันอยู่ตรงไหน) ก็ไม่ต้องทำอะไรเพราะอยู่ตำแหน่งที่ถูกต้องแล้ว break ออกจากลูป         

บรรทัดที่ 53 : แต่ถ้าหาไปเรื่อยๆแล้วเจอว่าตำแหน่งที่ j มีค่ามากกว่า temp แสดงว่า temp ต้องไปอยู่ก่อนหน้า j ก็ให้เลื่อน j ออกไป 1ตำแหน่ง ไปใส่ไว้ใน a[j+1] เป็นการดันข้อมูลไปทางขวา ถ้ายังน้อยกว่าก็ดันออกไปอีก จนได้ตำแหน่ง a[j+1] สำหรับแทรกลงไป

บรรทัดที่ 55 : ให้            a[j+1] เก็บ temp ข้อมูลก็จะไปอยู่ในตำแหน่งของมัน

จากตัวอย่างในรูป 5 15 30 40 25 รับอินพุทมา 5 ตัว อยากรู้ว่า 25 อยู่ตรงไหน 25 = a[4] เอาไปเก็บใน temp ต่อมาตรวจสอบข้อมูล (บรรทัดที่ 50) i =4 ดังนั้นต้องเริ่มจาก j ที่น้อยกว่า i อยู่1 ก็เริ่มจาก i=3 คือ 40 พบว่า25 น้อยกว่า40 ดัน 40ออกไป 1 ช่อง(บรรทัดที่ 53) ลดลงทีละ 1 ไล่มา 30 ไล่มา 15 พบว่า temp มากกว่า 15 เท่ากับว่า j ตอนนี้เป็น 1(ตอนที่จะ break บรรทัดที่ 52)  j[1]=15 ดังนั้นก็เอา temp ไปใส่  a[j+1] เท่านี้ 25 ก็จะอยู่ถัดจาก 15