Sorting
ถ้าเราจำเป็นต้องเก็บและค้นหาข้อมูลอยู่เป็นประจำ การเก็บข้อมูลเราก็ต้องจัดเก็บให้เป็นระเบียบ และง่ายในกระบวนการค้นหาข้อมูลเพื่อนำมาใช้ใหม่เช่นการจัดเรียงหมวดหมู่ของหนังสือในห้องสมุด ต้องมีการจัดการกับรายละเอียดของหนังสือต่างๆ ให้เป็นแฟ้มข้อมูลที่เรียงลำดับตามตัวอักษร เป็นต้น
การเรียงข้อมูล สามารถแบ่งได้เป็น 2 ประเภทด้วยกันคือ
1.การเรียงข้อมูลแบบภายใน (Internal Sorting) คือ การเรียงลำดับข้อมูล โดยทั้งหมดต้องจัดเก็บอยู่ในหน่วยความจำหลัก (main memory) ที่มีการเข้าถึงข้อมูลได้เร็ว โดยไม่จำเป็นต้องใช้หน่วยความจำสำรอง เช่น ดิสค์ หรือเทปสำหรับการจัดเก็บชั่วคราว ใช้ในกรณีที่ข้อมูลไม่มากเกินกว่าพื้นที่ความจำที่กำหนดให้กับผู้ใช้แต่ละราย
2.การเรียงข้อมูลแบบภายนอก (External Sorting) คือ การ เรียงลำดับข้อมูลที่มีขนาดใหญ่เกินกว่าที่จะสามารถเก็บไว้ใน พื้นที่ความจำหลักที่กำหนดให้ได้ในคราวเดียว ดังนั้นข้อมูล ส่วนมากต้องเก็บไว้ในไฟล์ข้อมูลที่อยู่บนดิสค์ เทป เป็นต้น สำหรับการเรียงข้อมูลแบบภายนอกจะต้องคิดถึงเวลาที่ใช้ใน การถ่ายเทข้อมูลจากหน่วยความจำชั่วคราวกับหน่วยความจำหลัก ด้วยเช่นกัน
การเรียงลำดับแบบตัวเลือก
หลักการดังนี้ คือ การเลือกข้อมูลที่มีค่าที่น้อยที่สุดในแถวลำดับ และนำค่านั้นไปเปลี่ยนที่กับข้อมูลที่บรรจุ อยู่ในแถวลำดับช่องแรก ต่อมามีการเลือกค่าที่มากกว่า และนำค่านั้นไปแลกกับข้อมูลในแถวลำดับช่องที่สอง ขั้นตอนนี้เหมือนกันกับขั้นตอนแรก ยกเว้นจะไม่มีการเปรียบเทียบกับ ข้อมูลในแถวลำดับช่องแรก เพราะรู้แล้วว่าเป็นค่าที่น้อยที่สุด ต่อจากนั้นจะมีการดำเนินงานแบบเดิม คือ เลือกตัวที่มีค่าน้อยที่สุดในบรรดา ข้อมูลที่เหลือแล้วมีการสลับที่ จนกระทั่งค่าทั้งหมดที่อยู่ในแถวลำดับมีการเรียงลำดับ และจะพบว่าที่ ส่วนแรกของแถวลำดับ ประกอบด้วยค่าน้อยที่สุด และที่ปลายสุดของแถวลำดับมีค่ามากที่สุด
การเรียงลำดับแบบฟอง
มีหลักการแตกต่างไปจาก การเรียงลำดับแบบเลือก โดยปกติวิธีการนี้จะมีการเปรียบเทียบน้อยกว่าวิธีที่กล่าวมาแล้ว แต่วิธีนี้จะมีการสลับที่มากกว่า การเรียงลำดับแบบเลือก และใช้เวลาในการทำงานมากกว่า
การเรียงลำดับวิธีนี้เริ่มโดย จะมีการเปรียบเทียบข้อมูลในแถวลำดับ ช่องแรกกับช่องถัดไป ถ้าช่องหลังมีข้อมูลขนาดใหญ่กว่า จึงเปลี่ยนที่ระหว่างช่องแรกและช่องที่สอง ต่อมามีการเปรียบเทียบระหว่างช่องที่สองกับช่องที่ 3 ถ้าช่องที่ 3 ข้อมูลมีค่ามากกว่าช่องที่ 2 มีการสลับที่ แล้วมีการเปรียบเทียบระหว่างช่องที่ 3 กับช่องที่ 4 และช่องที่ 4 กับช่องที่ 5 และมีการสลับที่นำตัวที่มีค่ามากกว่า ไว้ทางซ้ายมือ จนกระทั่งการเปรียบเทียบเกิดกับ ทุกตัวในแถวลำดับ ขั้นต่อไปมีการเปรียบเทียบอีก แล้วมีการสลับค่าจนครบทุกค่าของแถวลำดับ แต่อย่างไรก็ตามหลังจากที่มีการเปรียบเทียบ และสลับค่าครบรอบแล้วพบว่าค่าที่น้อยที่สุด จะไปอยู่ที่แถวลำดับช่อง ขวาสุด ดังนั้นจึงไม่จำเป็นต้องมีการเปรียบเทียบ กับแถวลำดับช่องนี้ในการเรียงลำดับค่ารอบต่อไป ต่อมาการเปรียบเทียบ และการเปลี่ยนค่าก็ดำเนินงานอีก โดยเว้นการเปรียบเทียบกับสองค่าสุดท้ายทาง ขวาสุดของแถวลำดับ แล้วมีการเปรียบเทียบและสลับที่เกิดขึ้นอีก โดยเว้นสามค่าสุดท้าย จะมีการเปรียบ เทียบและสลับที่ไปเรื่อย ๆ และท้ายที่สุดก็จะได้ข้อมูลในแถวลำดับ เรียงลำดับจากค่ามากสุดไปน้อยสุด
การเรียงลำดับแบบเร็ว
การเรียงลำดับแบบเร็ว (quick sort) เป็นวิธีการเรียงลำดับที่ใช้เวลาน้อยเหมาะสำหรับข้อมูลที่มีจำนวนมากที่ต้องการความรวดเร็วในการทำงาน วิธีนี้จะเลือกข้อมูลจากกลุ่มข้อมูลขึ้นมาหนึ่งค่าเป็นค่าหลัก แล้วหาตำแหน่งที่ถูกต้องให้กับค่าหลักนี้ เมื่อได้ตำแหน่งที่ถูกต้องแล้วใช้ค่าหลักนี้เป็นหลักในการแบ่งข้อมูลออกเป็น สองส่วน ถ้าเป็นการเรียงลำดับจากน้อยไปมาก ส่วนแรกอยู่ในตอนหน้าข้อมูลทั้งหมดจะมีค่าน้อยกว่าค่าหลักที่เป็นตัวแบ่งส่วน และอีกส่วนหนึ่งจะอยู่ในตำแหน่งตอนหลังข้อมูลทั้งหมดจะมีค่ามากกว่าค่าหลัก แล้วนำแต่ละส่วนย่อยไปแบ่งย่อยในลักษณะเดียวกันต่อไป จนกระทั่งแต่ละส่วนไม่สามารถแบ่งย่อยได้อีกต่อไปจะได้ข้อมูลที่มีการเรียงลำดับตามที่ต้องการ
การเรียงลำดับแบบแทรก
เป็นวิธีการเรียงลำดับที่ทำการเพิ่มสมาชิกเข้าไปใหม่ในเซต ที่มีสมาชิกทุกตังเรียงลำดับอยู่แล้ว และทำให้เซตใหม่ที่ได้นี้มีสมาชิกทุกตัวเรียงลำดับอยู่แล้วด้วย วิธีการเรียงลำดับ
1. เริ่มต้นเปรียบเทียบจากข้อมูลในตำแหน่งที่1 กับ 2 หรือข้อมูลในตำแหน่งสุดท้ายและรองสุดท้ายก็ได้ถ้าเป็นการเรียงลำดับจากน้อยไปหามาก
2. จะต้องจัดให้ข้อมูลที่มีค่าน้อยอยู่ในตำแหน่งก่อนข้อมูลที่มีค่ามาก และถ้าเรียงจากมากไปน้อยก็จะจัดให้ข้อมูลที่มีค่ามากอยู่ในตัวแหน่งก่อน
การเรียงลำดับแบบฐาน
การเรียงลำดับแบบฐาน (radix sort) เป็นการเรียงลำดับโดยการพิจารณาข้อมูลทีละหลัก เริ่มพิจารณาจากหลักที่มีค่าน้อยที่สุดก่อน นั่นคือถ้าข้อมูลเป็นเลขจำนวนเต็มจะพิจารณาหลักหน่วยก่อน การจัดเรียงจะนำข้อมูลเข้ามาทีละตัว แล้วนำไปเก็บไว้ที่ซึ่งจัดไว้สำหรับค่านั้น เป็นกลุ่ม ๆ ตามลำดับการเข้ามา ในแต่ละรอบเมื่อจัดกลุ่มเรียบร้อยแล้ว ให้รวบรวมข้อมูลจากทุกกลุ่มเข้าด้วยกัน โดยเริ่มเรียงจากกลุ่มที่มีค่าน้อยที่สุดก่อนแล้วเรียงไปเรื่อย ๆ จนหมดทุกกลุ่ม ในรอบต่อไปนำข้อมูลทั้งหมดที่ได้จัดเรียงในหลักหน่วยเรียบร้อยแล้วมาพิจารณาจัดเรียงในหลักสิบต่อไป ทำเช่นนี้ไปเรื่อย ๆ จนกระทั่งครบทุกหลักจะได้ข้อมูลที่เรียงลำดับจากน้อยไปมากตามต้องการ
ไม่มีความคิดเห็น:
แสดงความคิดเห็น