Sorting ถ้าเราจำเป็นต้องเก็บและค้นหาข้อมูลอยู่เป็นประจำ การเก็บข้อมูลเราก็ต้องจัดเก็บให้เป็นระเบียบและง่ายในกระบวนการค้นหาข้อมูลเพื่อนำมาใช้ใหม่ เช่นการจัดเรียงหมวดหมู่ของหนังสือในห้องสมุดต้องมีการจัดการรายละเอียดของหนังสื่อต่างๆ ให้เป็นแฟ้มข้อมูลที่เรียงลำดับตามอักษร เป็นต้น และในการประกอบการต่างๆ ที่เกี่ยวข้องกับการใช้งานด้านคอมพิวเตอร์ก็มีการจัดเรียงลำดับของข้อมูลโดยวิธีใดวิธีหนึ่งแล้วแต่เรากำหนดทำไมเราจึงต้องศึกษาการเรียงลำดับข้อมูล (Sorting) เพื่อช่วยในการออกแบบอัลกอรึทึม เพราะการเรียงลำดับข้อมูล เป็นงานพื้นฐานที่ใช้ในโปรแกรมประยุกต์ต่างๆ ช่วยทำให้การเรียกใช้งานข้อมูลนั้นๆ มีความสะดวก รวดเร็ว ในการค้นหา มากกว่าการเรียกใช้ข้อมูลที่ไม่มีการลำดับ และทำให้เกิดเทคนิคใหม่ๆ ที่น่าสนใจและสำคัญอันได้แก่ Partial ,order ,recursion ,merge ,lists การจัดเก็บ
binary tree ในอาเรย์เป็นต้น อีกทั้ง อัลกอรึทึมที่ใช้เพื่อการเรียงลำดับข้อมูลแต่ละตัวมีข้อดีและข้อเสียแตกต่างกันขึ้นอยู่กับจำนวนชนิดของข้อมูล การกำหนดค่าเริ่มต้น ขนาด และค่าของข้อมูลที่จะทำการเรียงลำดับสิ่งสำคัญก็คือ เราต้องรุ้ว่าเรามีความต้องการอย่างไรเพื่อที่สามารถจะเลือก อัลกอรึทึมที่มีความเหมาะสมและสอดคล้องกับงานของเราได้
การเรียงข้อมูล สามารถแบ่งได้เป็น 2 ประเภทด้วยกันคือ
1. การเรียงข้อมูลแบบภายใจ (Intemal sorting) คือการเรียงลำดับข้อมูลโดยทั้งหมดต้องจัดเก็บอยู่ในหน่วยความจำหลัก (main memory) ที่มีการเข้าถึงข้อมูลได้เร็วโดยไม่จำเป็นต้องใช้หน่วยความจำสำรอง เช่นดิสก์ หรือเทปสำหรับการจัดเก็บชั่วคราว ใช้ในกรณีที่ข้อมูลไม่มากเกินกว่าพื้นที่ความจำเป็นกำหนดให้กับผู้ใช้
แต่ละราย
2. การเรียงข้อมูลแบบภายนอก (Extermal sorting) คือการเรียงลำดับข้อมูลที่มีขนาดใหญ่เกินกว่าที่จะสามารถเก็บไว้ใน พื้นที่ความจำหลักที่กำหนดให้ได้ในคราวเดียว ดังนั้นข้อมูลส่วนมากต้องเก็บไว้ในไฟล์ข้อมูลที่อยู่บนดิสก์ เทป เป็นต้น สำหรับการเรียงข้อมูลแบบภายนอกจะต้องคิดถึงเวลาที่ใช้ในการถ่ายเทข้อมูลจากหน่วยความจำชั่วคราวกับหน่วยความหลัก ด้วยเช่นกัน
อัลกอรึทึมสำหรับการเรียงข้อมูล จัดได้ 3 ประเภทใหญ่ๆ คือ
1. การเรียงลำดับแบบแลกเปลี่ยน (Exchange sort)
2. การเรียงลำดับแบบแทรก (Insertion sort)
3. การเรียงลำดับแบบเลือก (Selection sort)
Sorting Algorithms
Bubble sort
หลักของการเรียงแบบนี้คือ จะเปรียบเทียบและแลกแปลี่ยนข้อมูล 2 ค่าที่อยู่ติดกันในลักษณะที่เรากำหนดเช่นจากน้อยไปหามาก หรือ จากมากไปหาน้อย โดยจะทำการเปรียบเทียบข้อมูลทั้งชุดจนกว่าจะมีการเรียงลำดับทั้งหมดของขั้นตอนการทำงานของอัลกอรึทึม
Quick Sort
การเรียงลำดับในลักษณะนี้เป็นการปรับปรุงมาจากการเรียงลำดับแบบ Bubble เพื่อให้การเรียงลำดับนั้นเร็วขึ้นวิธีนี้เหมาะกับการเรียงข้อมูลที่มีจำนวนมาก หรือมีขนาดใหญ่ และเป็นวิธีการเรียงข้อมูลที่ให้ค่าเฉลี่ยของเวลาน้อยที่สุดเท่าที่ค้นพบวิธีหนึ่ง การเรียงลำดับแบบ Quick sort จะเป็นการเปรียบเทียบสมาชิกที่ไม่อยู่ติดกันโดยกำหนดข้อมูลค่าหนึ่ง เพื่อแบ่งชุดข้อมูลที่ต้องการเรียงลำดับออกเป็น 2 ส่วน จากนั้นจะทำการแบ่งย่อยชุดข้อมูล 2 ส่วนนั้นลงไปอีกทำแบบนี้ไปเรื่อยๆ จนข้อมูลแต่ละชุดมีสมาชิกเหลือเพียงตัวเดียงและทำให้ชุดข้อมูลทั้งหมดมีการเรียงลำดับ
Insertion Sort
insertion sort การเรียงลำดับที่ง่ายไม่ซับซ้อน เป็นการนำข้อมูลใหม่เพิ่มเข้าไปในชุดข้อมูลที่มีการเรียงลำดับอยู่แล้ว โดยข้อมูลใหม่ที่นำเข้ามาจะแทรกอยู่ใจตำแหน่งทางขวาของชุดข้อมูลเดิมและยังคงให้ข้อมูลทั้งหมดมีการเรียงลำดับ วิธีนี้เริ่มต้นโดยการเรียงลำดับ 2 ตัวแรกของชุดข้อมูล หลังจากนั้นเพิ่มข้อมูลตัวที่3เข้ามาจะมีการเปรียบเทียบค่ากับข้อมูล 2 ตัวแรก และแทรกอยู่ในตำแหน่งที่เหมาะสมและสำหรับการเพิ่มข้อมูลตัวต่อๆไปก็จะทำเหมือนเดิมจนข้อมูลทุกตัวมีการเรียงลำดับขั้นตอนการทำงาน
ไม่มีความคิดเห็น:
แสดงความคิดเห็น