การจัดเรียงลำดับข้อมูล (Sorting)
เป็นกระบวนการเพื่อจัดการข้อมูลให้จัดเรียงตามลำดับซึ่งเป็นเทคนิคในการค้นหาข้อมูลให้มีประสิทธ์ภาพมากขึ้น โดยสามารถแบ่งเป็น 2 ประเภทๆ หลักคือ
1. การเรียงลำดับภายใน(Internal Sorting) เป็นการเรียงลำดับข้อมูลภายในหน่วยความจำหลัก (Primary Memory) ซึ่งจะเหมาะสมกับข้อมูลทีมีปริมณไม่มาก เนื่องจากหน่วยความจำหลักมีขนาดจำกัด ซึ่งมีวิธีการเรียงลำดับข้อมูล โดยสมารถแบ่งประเภทย่อยได้ดังนี้
1.1 วิธีเรียงลำดับแบบแทรก (Insertion )
- วิธีเรียงลำดับข้อมูลแบบ Insertion Sort
- วิธีเรียงลำดับข้อมูลแบบ Shell Sort
1.2 วิธีเรียงลำดับแบบเลือก (Selection)
- วิธีเรียงลำดับข้อมูลแบบ Selection Sort
- วิธีเรียงลำดับข้อมูลแบบ Heap Sort
1.3 วิธีเรียงลำดับแบบแลกเปลี่ยน (Exchange)
- วิธีเรียงลำดับข้อมูลแบบ Bubble Sort
- วิธีเรียงลำดับข้อมูลแบบ Quick Sort
2. การเรียงลำดับภายนอก (External Sorting) เป็นการเรียงลำดับข้อมูลด้วยการใช้หน่วยความจำเฉพาะส่วนข้อมูลที่ต้องการจัดเรียง เหมาะสมกับการใช้กับข้อมูลทีมีปริมาณมาก เนื่องจากจะไม่สามารถนำไปใส่ไว้ในหน่วยความจำหลักเพื่อประมวลผลพร้อมกันได้ ซึ่งมีวิธีการเรียงลำดับข้อมูล ได้แก่
- วิธีเรียงลำดับข้อมูลแบบ Merge Sort
การจัดเรียงลำดับข้อมูลแบบ ฺQuick Sort
การจัดเรียงลำดับข้อมูลแบบ ฺMerge Sort
Sequential Search คืออะไร
Sequential Search หรือ Linear Search คือ การหาข้อมูลแบบเป็นลำดับขั้นตอน โดยจะค้นหาตั้งแต่ตัวแรกเรียงลำดับไปทีละตัวจนกว่าจะพบข้อมูลที่ต้องการ หรือเปรียบเทียบไปจนถึงตัวสุดท้าย การค้นหาวิธีนี้เป็นวิธีที่ง่ายที่สุด อัลกอริทึ่มในการค้นหาไม่ซับซ้อนสามารถใช้กับข้อมูลที่เรียงลำดับแล้วหรือข้อมูลที่ยังไม่ได้เรียงลำดับก็ได้ โดยผลลัพธ์จากการค้นหาข้อมูลจะมีความเป็นไปได้อยู่ 2 แบบ คือ
1.พบตำแหน่งข้อมูลที่ต้องการภายในลิสต์(Successful Search)
ตัวอย่างการค้นหา
 |
2. ไม่พบตำแหน่งข้อมูลที่ต้องการภายในลิสต์ (Unsuccessful Search)
ตัวอย่างการค้นหา
Binary Search คืออะไร
Binary Search คือ การค้นหาที่ใช้ได้กับชุดข้อมูลที่มีการเรียงลำดับไว้แล้วเท่านั้น หลักการค้นหาเริ่มด้วยการนำคีย์ไปเปรียบเทียบกับค่ากลางของข้อมูลชุดนั้นถ้าคีย์ไปเปรียบเทียบกับค่ากลางของครึ่งชุดข้อมูลที่มีค่าน้อย ถ้าค่าคีย์มากกว่าก็ให้นำไปเปรียบเทียบกับค่ากลางของครึ่งชุดข้อมูลที่มีค่ามาก ทำเช่นนี้เรื่อยไปจนพบข้อมูลที่เท่ากับคีย์หรือจนกระทั่งหมดข้อมูลที่จะเปรียบเทียบ
เทคนิคการค้นหาข้อมูลด้วยวิธีนี้
1. กำหนดข้อมูลที่ต้องการค้นหาและทำการเรียงข้อมูลตามความต้องการ เรียงจากมากไปน้อย หรือจากน้อยไปมากก็ได้
2. ทำการแบ่งข้อมูลออกเป็น 2 ส่วน แล้วทำการหาค่ากลาง
3. เมื่อทราบแล้วว่าค่าของคีย์ฟิลด์อยู่ครึ่งแรกหรือครึ่งหลังแล้ว ก็จะนำข้อมูลในครึ่งดังกล่าวทำการหาค่ากลางอีก ทำแบบนี้ไปเรื่อย ๆ จนกระทั้งได้ข้อมูลที่ต้องการ หรือจนกระทั่งไม่สามารถแบ่งข้อมูลได้อีก
เทคนิคการค้นหาข้อมูลด้วยวิธีนี้
1. กำหนดข้อมูลที่ต้องการค้นหาและทำการเรียงข้อมูลตามความต้องการ เรียงจากมากไปน้อย หรือจากน้อยไปมากก็ได้
2. ทำการแบ่งข้อมูลออกเป็น 2 ส่วน แล้วทำการหาค่ากลาง
3. เมื่อทราบแล้วว่าค่าของคีย์ฟิลด์อยู่ครึ่งแรกหรือครึ่งหลังแล้ว ก็จะนำข้อมูลในครึ่งดังกล่าวทำการหาค่ากลางอีก ทำแบบนี้ไปเรื่อย ๆ จนกระทั้งได้ข้อมูลที่ต้องการ หรือจนกระทั่งไม่สามารถแบ่งข้อมูลได้อีก
ตัวอย่างการค้นหา
เปรียบเทียบระหว่าง Sequential Search และ Binary Search
การเปรียบเทียบครั้งนี้ จะใช้ Binary Search เป็นตัวอ้างอิง ซึ่งเราจะแบ่งออกเป็น 2 ประเภท คือ
1. Best Case Binary Search
2.Worst Case Binary Search
จะเห็นได้ว่า Binary Search สามารถหาข้อมูลที่ต้องการได้เร็วกว่า Sequential Search เมื่อมีจำนวนข้อมูลจำนวนมาก แต่ถ้าหากมีข้อมูลน้อยๆ และสิ่งที่ต้องการหานั้นอยู่เป็นต้นๆก็จำทำให้การหาแบบ Sequential Search เร็วกว่า ดังกราฟ
 |
| โดยที่ n = Sequential Search log(n) = Binary Search |
แหล่งเรียนรู้ Sorting
https://visualgo.net/en/sorting
https://www.toptal.com/developers/sorting-algorithms
แหล่งอ้างอิง
https://www.tutorialspoint.com/data_structures_algorithms/linear_search_algorithm.htm
http://web.yru.ac.th/~jeerawoot/searching.htm
http://marborojung.blogspot.com/2013/02/searching.html
https://blog.penjee.com/binary-vs-linear-search-animated-gifs/
http://slideplayer.com/slide/8706635/
http://www.equestionanswers.com/c/c-binary-search.php
https://mohtashims.wordpress.com/2010/07/02/searching/
