งานใหม่

การจัดเรียงข้อมูล

            การค้นหาข้อมูล (Searching)                    การค้นหาข้อมูลถือว่าเป็น Algorithm ที่สำคัญที่สุดเรื่องหนึ่ง ในการนำคอมพิวเตอร์ไปใช้งาน เพราะการเรียกข้อมูลจากหน่วยความจำ หรือจาก File เพื่อนำมาใช้งาน ส่วนใหญ่แล้วการค้นหาข้อมูลจะถูกประกอบเข้าเป็นส่วนหนึ่งของขบวนการทำงานด้วยคอมพิวเตอร์                                                                                                        การค้นหาข้อมูลแบ่งตามลักษณะการจัดเก็บได้ 2 อย่างคือ   1.การค้นหาข้อมูลภายใน     (Internal Search) 2. การค้นหาข้อมูลภายนอก     (External Search)  การค้นหาข้อมูลแบ่งตามลักษณะการค้นหาได้ 2 อย่างคือ 1. การค้นหาข้อมูลตามลำดับ (Linear Search)      ซึ่งการค้นหาแบบนี้มีเทคนิค 2 อย่างคือ     1.1 Unsorted Linear Search      1.2 Sorted Linear Search 2. การค้นหาข้อมูลทวิภาค (Binary Search)      2.1 Binary Search in Array      2.2 Binary Search Tree               หลักการUnsorted Linear Search เป็นการค้นหาข้อมูลแบบเรียงลำดับทีละตัว เริ่มตั้งแต่ข้อมูลตัวแรก ไปเรื่อย ๆ จนกระทั่งพบข้อมูลที่ต้องการ หรือจนหมดทุกตัว                      AlgorithmUnsorted Linear Search 1. กำหนดให้ ตัวนับเริ่มต้นเป็นตัวแรกของข้อมูล2. เปรียบเทียบข้อมูล ถ้า- พบข้อมูล ทำข้อ 5- ไม่พบข้อมูล ทำข้อ 33. เพิ่มค่า ตัวนับ4. ทำซ้ำข้อ 25. จบ                     Complexity Unsorted Linear Searchครั้งที่ 1 เปรียบเทียบ 1 ครั้งครั้งที่ 2 เปรียบเทียบ 1 ครั้งครั้งที่ 3 เปรียบเทียบ 1 ครั้งครั้งที่ 4 เปรียบเทียบ 1 ครั้งครั้งที่ 5 เปรียบเทียบ 1 ครั้งครั้งที่ 6 เปรียบเทียบ 1 ครั้งรวม 6 ครั้ง ถ้าให้ข้อมูลมี n จำนวนจะได้1+ 1+1+1+1+1=6 หรือ n ครั้ง นั่นเองดังนั้น Complexity หรือ Big-Oh ของ Unsorted Linear Search จึงมีค่าเป็น O(n) -         Best case O(1) -         Worse case O(n)          

ถ้าให้ข้อมูลมี n จำนวนจะได้

1+ 1+1+1+1+1=6 หรือ n ครั้ง นั่นเองดังนั้น Complexity หรือ Big-Oh ของ Unsorted Linear Search จึงมีค่าเป็น O(n) -        Best case O(1) -        Worse case O(n)

        

 

หลักการSorted Linear Search เป็นการค้นหาข้อมูลแบบเรียงลำดับทีละตัว เริ่มตั้งแต่ข้อมูลตัวแรก ไปเรื่อย ๆ จนกระทั่งพบข้อมูลที่ต้องการ หรือจนค่าของข้อมูลตัวถัดไปมีค่ามากกว่า ซึ่งมีเงื่อนไขว่า ข้อมูลนั้นต้องมีการจัดเรียงแล้วเท่านั้น            Algorithm

Sorted Linear Search

  

 

1. กำหนดให้ ตัวนับเริ่มต้นเป็นตัวแรกของข้อมูล2. เปรียบเทียบข้อมูล ถ้า-พบข้อมูล ทำข้อ  5-ค่าของข้อมูลที่ต้องการค้นหา < ค่าของข้อมูลที่ตำแหน่ง ตัวนับ   ทำข้อ  53. เพิ่มค่า ตัวนับ4. ทำซ้ำข้อ 25. จบ