วิทยาการคำนวณ

                                                                           

 2.5 การจัดเรียงและค้นหาข้อมูล

การจัดเรียงข้อมูลคือ การจัดเรียงข้อมูลเป็นสิ่งที่พบอยู่เสมอ เมื่อต้องประมวลผลข้อมูลจำนวนมาก ได้รู้เกี่ยวกับขั้นตอนพิธีพื้นฐานในก่รจัดเรียงข้อมูล (sort) และ การค้นหาข้อมูล (search)

 2.5.1) การจัดเรียงข้อมูลแบบ Bubble Sort เป็นการจัดเรียงล าดับข้อมูลประเภท Internal sorting โดยใช้การเปรียบเทียบคีย์ในต าแหน่งที่อยู่ ติดกันทีละคู่ ถ้าคีย์ที่เปรียบเทียบไม่อยู่ในต าแหน่งที่ต้องการแล้วให้ทำการสลับที่กันระหว่างข้อมูล 2 ตัวนั้น ทำ เช่นนี้จนกระทั่งเปรียบเทียบครบทุกตัว ซึ่งคือ N-1 ครั้ง ทิศทางการทำงานอาจจะทำจากคู่ซ้ายไปขวา หรือคู่ ขวาไปซ้าย หรือคู่บนลงล่าง หรือคู่ล่างขึ้นบน ก็ได้ ในแต่ละรอบของการเปรียบเทียบ คีย์ที่มีค่ามากจะถูกสลับที่ไปอยู่ในตำแหน่งตอนท้าย หรือคีย์ที่มีค่า น้อยจะถูกสลับไปอยู่ในตำแหน่งตอนบน สำหรับตัวอย่างนี้จะเริ่มเปรียบเทียบข้อมูลคู่ท้ายก่อน โดยให้ข้อมูลที่มี ค่ามากสลับไปอยู่ด้านท้ายของข้อมูล หรือข้อมูลที่มีค่าข้อมูลมากอยู่ทางด้านล่างของแถวนั่นเอง 

                                              

2.5.2) การจัดเรียงลำดับข้อมูลแบบ Insertion Sort เป็นการจัดเรียงล าดับข้อมูลประเภท Internal sorting โดยได้เทคนิคมาจากลักษณะการจัดไพ่ในมือ ของผู้เล่น คือ เมื่อผู้เล่นได้ไพ่ใบใหม่เพิ่มขึ้นมา จะนำไพ่ใบนั้นไปแทรกในตำแหน่งที่เหมาะสม ทำให้ไพ่ใน มือบางส่วนต้องขยับตำแหน่งออกไป ซึ่งการจัดเรียงล าดับข้อมูลแบบแทรกนี้ จะเริ่มพิจารณาคีย์ในตำแหน่งที่ 2 เป็นต้นไป โดยนำคีย์ที่พิจารณาไปแทรกในตำแหน่งที่ถูกต้อง และจะมีผลให้คีย์ในตำแหน่งที่อยู่หลัง ต าแหน่งที่แทรกขยับตำแหน่งออกไปเรื่อยๆ จากวิธีการดังกล่าว ถ้าการพิจารณาคีย์มาถึงตำแหน่งที่ I จะเห็นได้ว่าข้อมูลจะถูกแบ่งออกเป็นสอง ส่วน คือ ส่วนแรกจะเป็นส่วนที่ถูกจัดเรียงลำดับตามคีย์แล้ว อีกส่วนจะเป็นส่วนที่ยังไม่ได้ทำการจัดเรียง 

อ่านเพิ่มเติม