Park-Kachen
15 กันยายน 2552
DTS10-09-09-2552
Sorting
ถ้าเราจำเป็นต้องเก็บและค้นหาข้อมูลอยู่เป็นประจำ การเก็บข้อมูลเราก็ต้องจัดเก็บให้เป็นระเบียบ และง่ายในกระบวนการค้นหาข้อมูลเพื่อนำมาใช้ใหม่ เช่นการจัดเรียงหมวดหมู่ของหนังสือในห้องสมุด ต้องมีการจัดการกับรายละเอียดของหนังสือต่างๆ ให้เป็นแฟ้มข้อมูลที่เรียงลำดับตามตัวอักษร เป็นต้น
และในการประกอบการต่างๆ ที่เกี่ยวข้องกับการใช้งานด้านคอมพิวเตอร์ ก็มีการจัดเรียงลำดับของข้อมูล โดยวิธีใดวิธีหนึ่งแล้วแต่กำหนดทำไมเราจึงต้องศึกษาการเรียงลำดับข้อมูล (Sorting) เพื่อช่วยในการออกแบบอัลกอรึทึม ?
เพราะการเรียงลำดับข้อมูล เป็นงานพื้นฐานที่ใช้ในโปรแกรมประยุกต์ต่างๆ ช่วยทำให้การเรียกใช้งานข้อมูลนั้นๆ มีความสะดวก รวดเร็ว ในการค้นหา มากกว่าการเรียกใช้ข้อมูลที่ไม่มีการลำดับ และทำให้เกิดเทคนิคใหม่ๆที่น่าสนใจและสำคัญอันได้แก่ partial order , recursion , merge , lists , การจัดเก็บ binary tree ในอาร์เรย์ เป็นต้น
อีกทั้ง อัลกอรึทึมที่ใช้เพื่อการเรียงลำดับข้อมูลแต่ละตัวมีข้อดีและข้อเสียแตกต่างกัน ขึ้นอยู่กับจำนวน ชนิดของข้อมูล การกำหนดค่าเริ่มต้น ขนาด และค่าของข้อมูลที่จะทำการเรียงลำดับ สิ่งสำคัญก็คือ เราต้องรู้ว่าเรามีความต้องการอย่างไรเพื่อที่สามารถจะเลือก อัลกิรึทึมที่มีความเหมาะสม และสอดคล้องกับงานของเราได้...
การเรียงข้อมูล สามารถแบ่งได้เป็น 2 ประเภทด้วยกันคือ
1. การเรียงข้อมูลแบบภายใน (Internal Sorting) คือ การเรียงลำดับข้อมูล โดยทั้งหมดต้องจัดเก็บอยู่ในหน่วยความจำหลัก (main memory) ที่มีการเข้าถึงข้อมูลได้เร็ว โดยไม่จำเป็นต้องใช้หน่วยความจำสำรอง เช่น ดิสค์ หรือเทปสำหรับการจัดเก็บชั่วคราว ใช้ในกรณีที่ข้อมูลไม่มากเกินกว่าพื้นที่ความจำที่กำหนดให้กับผู้ใช้แต่ละราย
2. การเรียงข้อมูลแบบภายนอก (External Sorting) คือ การ เรียงลำดับข้อมูลที่มีขนาดใหญ่เกินกว่าที่จะสามารถเก็บไว้ใน พื้นที่ความจำหลักที่กำหนดให้ได้ในคราวเดียว ดังนั้นข้อมูล ส่วนมากต้องเก็บไว้ในไฟล์ข้อมูลที่อยู่บนดิสค์ เทป เป็นต้น สำหรับการเรียงข้อมูลแบบภายนอกจะต้องคิดถึงเวลาที่ใช้ใน การถ่ายเทข้อมูลจากหน่วยความจำชั่วคราวกับหน่วยความจำหลัก ด้วยเช่นกัน
อัลกอรึทึมสำหรับการเรียงข้อมูล จัดได้ 3 ประเภทใหญ่ๆ ดังนี้
1. การเรียงลำดับแบบแลกเปลี่ยน (Exchange Sort)
2. การเรียนลำดับแบบแทรก (Insertion Sort)
3. การเรียงลำดับแบบเลือก (Selection Sort)
Sorting Algorithms
Bubble Sort หลักของการเรียงแบบนี้คือ จะเปรียบเทียบและแลกเปลี่ยนข้อมูล 2 ค่าที่อยู่ติดกันในลักษณะที่เรากำหนด เช่น จากน้อยไปมาก หรือจากมากไปน้อย โดยจะทำการเปรียบเทียบข้อมูลทั้งชุดจนกว่าจะมีการเรียงตามลำดับทั้งหมดขั้นตอนการทำงานของอัลกอริทึม
Quick Sort การเรียงลำดับในลักษณะนี้ เป็นการปรับปรุงมาจากการเรียงลำดับแบบ Bubble เพื่อให้การเรียงลำดับเร็วขึ้น วีธีนี้เหมาะกับการเรียงข้อมูลที่มีจำนวนมาก หรือมีขนาดใหญ่ และเป็นวิธีการเรียงข้อมูลที่ให้ค่าเฉลี่ยของเวลาน้อยที่สุดเท่าที่ค้นพบวิธีหนึ่งการเรียงลำดับแบบ Quick Sortจะเป็นการเปรียบเทียบสมาชิกที่ไม่อยู่ติดกัน โดยกำหนดข้อมูลค่าหนึ่ง เพื่อแบ่งชุดข้อมูลที่ต้องการเรียงลำดับออกเป้น 2 ส่วน จากนั้นก็จะทำการแบ่งย่อยชุดข้อมูล 2 ส่วนนั้นลงไปอีก ทำแบบนี้ไปเรื่อยๆจนข้อมูลแต่ละชุดมีสมาชิกเหลือเพียงตัวเดียวและทำให้ชุดข้อมูลทั้งหมดมีการเรียงลำดับ
Insertion SortInsertion Sort การเรียงลำดับที่ง่ายไม่ซับซ้อน เป็นการนำข้อมูลใหม่เพิ่มเข้าไปในชุดข้อมูลที่มีการเรียงลำดับอยู่แล้ว โดยข้อมูลใหม่ที่นำเข้ามาจะแทรกอยู่ในตำแหน่งทางขวาของชุดข้อมูลเดิม และยังคงทำให้ข้อมูลทั้งหมดมีการเรียงลำดับวิธีนี้เริ่มต้นโดยการเรียงลำดับข้อมูล 2 ตัวแรกของชุดข้อมูล หลังจากนั้นเพิ่มข้อมูลตัวที่ 3 เข้ามา จะมีการเปรียบเทียบค่ากับข้อมูล 2 ตัวแรก และแทรกอยู่ในตำแหน่งที่เหมาะสม และสำหรับการเพิ่มข้อมูลตัวต่อๆไปก็จะทำเหมือนเดิมจนข้อมูลทุกตัวมีการเรียงลำดับขั้นตอนการทำงานของอัลกอริทึม
posted by Park-Kachen at 08:45
0 Comments:
แสดงความคิดเห็น
<< Home