ลูกแรดเตรียมพร้อมล่าเหยื่อ

สิ่งที่ได้รับจากการฝึกประสบการณ์วิชาชีพ3
1.มีความรู้รอบตัวมาขึ้นในการทำงาน
2.มีความตรงต่อเวลาในการทำงาน
3.มีความรับผิดชอบในการทำงาน
4.มีความรอบคอบในการทำงาน
5.ได้รู้จักระเบียบวินัยในการทำงาน
6.รู้จักอดทนในเวลาระหว่างการทำงาน
7.รู้จักการทำงานเป็นทีมกับบุคคลรอบข้าง

DTS 12-15/09/2009

สรุป Sorting
การเรียงลำดับแบบเร็ว (Quick sort) เป็นการเรียงลำดับที่ใช้วเลาน้อยเหมาะสำรับข้อมูลที่มีจำนวนมากที่ต้องการความรวดเร็วในการทำงาน
การเรียงลำดับแบบแทรก (insertion sort) เป็นวิธีที่ทำการเพิ่มสมาชิกใหม่เข้าไปในเซต ที่มีสมาชิกทุกตัวเรียงลำดับอยู่แล้ว และทำให้เซตใหม่
มีสมาชิกทุกตัวเรียงลำดับด้วย วิธีการเรียงลำดับ
1.เริ่มต้นเปรียบเทียบจากข้อมูลในตำแหน่งที่ 1 กับ 2 หรือข้อมูลในตำแหน่งสุดท้ายและรองสุดท้ายก็ได้
ถ้าเป็นการเรียงลำดับจากน้อยไปมาก
2.จะต้องจัดให้ข้อมูลที่มีค่าน้อยอยู่ในตำแหน่งก่อนข้อมูลที่มีค่ามาก และถ้าเรียงจากมากไปน้อยก็จะจัดให้ข้อมูลที่มีค่ามากอยู่ในตำแหน่งก่อน
การเรียงลำดับแบบฐาน (radix sort)เป็นการเรียงลำดับโดยการพิจารณาข้อมูลทีละหลัก
1.เริ่มพิจารณาจากหลักที่มีค่าน้อยที่สุดก่อน คือ ถ้าเป็นข้อมูลเป็นเลขจำนวนเต็มจะพิจารณาหลักหน่อยก่อน
2.การจัดเรียงจะนำข้อมูลเข้ามาทีละตัว และนำไปเก็บไว้ที่ซึ่งจัดไว้สำหรับค่านั้น เป็นกลุ่มๆ ตามลำดับการเข้ามา
3.ในแต่ละรอบเมื่อจัดกลุ่มเรียบร้อยแล้ว ให้รวบรวมข้อมูลจากทุกกลุ่มเข้าด้วยกัน โดยเริ่มเรียงจากกลุ่มที่มีค่าน้อยที่สุดก่อนแล้วเรียงไปเรื่อยๆ จนหมดทุกกลุ่ม
4.ในรอบต่อไปนำข้อมูลทั้งหมดที่ได้จัดเรียงในหลักหน่วยเรียบร้อยแล้วมาพิจารณาจัดเรียงในหลักสิบต่อไป ทำไปเรื่อยๆ จนครบทุกหลักจะได้ข้อมูลที่เรียงลำดับจากน้อยไปมากตามต้องการ
การเรียงลำดับแบบฐานมีวิธีการที่ไม่ซับซ้อนแต่ค่อนข้างใช้เนื้อที่ในหน่วยความจำมาก เนื่องจากการจัดเรียงแต่ละรอบจะต้องเตรียมเนื้อที่สำหรับสร้างที่เก็บข้อมูลในแต่ละกลุ่ม

ตารางแฮช (Hash Table)
ฟังก์ชั่น แฮช จะทำงานแบบสุ่ม การที่แทรกคีย์ในตาราง ที่จัดเก็บนั้นมีโอกาสที่คีย์ที่ถูกสร้างจากฟังก์ชั่น ในช่องเดียวกันตามการเกิดการชนกันก็ยังคงต้องมีอย่างน้อยหนึ่งครั้ง
วิธีการในการรองรับกรชนกันของตารางแฮช คือ
-การทำแบ่งห่วงโซ่ (Chaining)
-แบบการเปิดที่อยู่ (Open Addressing)
การแก้ไขปัญหาชนกันของข้อมูลแบบห่วงโซ่ (Chaining)
1.กรณีที่เลวร้ายที่สุด ในการแทรกข้อมูลคือ o(1)
2.การลบสมาชิก สามารถทำได้ด้วยเวลาที่น้อยที่สุดของ o(1)
ทางปฏิบัติ ใช้เทคนิค ฮิวริสติก (Heuristic) ในการสร้างฟังก์ชั่นแฮช แนวทางหนึ่งที่ดี คือ การแปลงค่าของข้อมูลที่มีอยู่แล้วด้วยข้อมูลที่มีอยู่ (วิธีการหาร : Division method)
วิธีการสร้างฟังก์ชั่นแฮช
1.วิธีการหาร (The Division Method)
2.วิธีการคูณ (The Multiplication Method)
3.วิธีทั่วไป (Universal hsahing)
เทคนิคลำดับการตรวจสอบ
1.การตรวจสอบเชิงเส้น (Linear Probing)
2.การตรวจสอบด้วยสมการกำลังสอง (Quadratic Probing)
3.การสร้างฟังก์ชันแฮชแบบสองเท่า (Double Hashing)

DTS 11-08/09/2009

เรื่อง การเรียงลำดับ(sorting)
การเรียงลำดับ (sorting) เป็นการจัดให้เป็นระเบียบ มีแบบแผน ช่วยให้การค้นหาสิ่งของหรือข้อมูล ซึ่งจะสามารถกระทำได้รวดเร็วและมีประสิทธิภาพ เช่น การค้นหาความหมายของคำในพจนานุกรม ทำได้ค่อนข้างง่ายและรวดเร็วเนื่องจากมีการเรียงลำดับคำตามตัวอักษรไว้อย่างมีระบบและเป็นระเบียบ หรือ การค้นหาหมายเลขโทรศัพท์ในสมุดโทรศัพท์ ซึ่งมีการเรียงลำดับ ตามชื่อและชื่อสกุลของเจ้าของโทรศัพท์ไว้ ทำให้สามารถค้นหา หมายเลขโทรศัพท์ของคนที่ต้องการได้อย่างรวดเร็ว เป็นต้น
วิธีการเรียงลำดับ
วิธีการเรียงลำดับสามารถแบ่งออกเป็น 2 ประเภท คือ
(1)การเรียงลำดับแบบภายใน (internal sorting) เป็นการเรียงลำดับที่ข้อมูลทั้งหมดต้องอยู่ในหน่วยความจำหลัก เวลาที่ใช้ในการเรียงลำดับจะคำนึงถึงเวลาที่ใช้ในการเปรียบเทียบและเลื่อนข้อมูลภายในความจำหลัก
(2) การเรียงลำดับแบบภายนอก(external sorting) เป็นการเรียงลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำสำรอง ซึ่งเป็นการเรียงลำดับข้อมูลในแฟ้มข้อมูล (file) เวลาที่ใช้ในการเรียงลำดับต้องคำนึงถึงเวลาที่เสียไประหว่างการถ่ายเทข้อมูลจากหน่วยความจำหลัก
การเรียงลำดับแบบเลือก (selection sort)
ทำการเลือกข้อมูลมาเก็บในตำแหน่งที่ ข้อมูลนั้นควรจะอยู่ทีละตัว โดยทำการค้นหาข้อมูลนั้นในแต่ละรอบแบบเรียงลำดับถ้าเป็นการเรียงลำดับ
การจัดเรียงลำดับแบบเลือกเป็นวิธีที่ง่ายและตรงไปตรงมา แต่มีข้อเสียตรงที่ใช้เวลาในการจัดเรียงนาน
เพราะแต่ละรอบต้องเปรียบเทียบกับข้อมูลทุกตัว ถ้ามีจำนวนข้อมูลทั้งหมด n ตัว ต้องทำการเปรียบเทียบทั้งหมด
การเรียงลำดับแบบฟอง (Bubble Sort)
1. ถ้าข้อมูลทั้งสองไม่อยู่ในลำดับที่ถูกต้องให้สลับตำแหน่งที่อยู่กัน
2. ถ้าเป็นการเรียงลำดับจากน้อยไปมากให้นำข้อมูลตัวที่มีค่าน้อยกว่าอยู่ในตำแหน่งก่อนข้อมูลที่มีค่ามาก ถ้าเป็นการเรียงลำดับจากมากไปน้อยให้นำข้อมูล ตัวที่มีค่ามากกว่าอยู่ในตำแหน่งก่อนข้อมูลที่มีค่าน้อย
การเรียงลำดับแบบแทรก (insertion sort)
เป็นวิธีการเรียงลำดับที่ทำการเพิ่มสมาชิกใหม่เข้าไปในเซต ที่มีสมาชิกทุกตัวเรียงลำดับอยู่แล้ว และทำให้เซตใหม่ที่ได้นี้มีสมาชิกทุกตัวเรียงลำดับด้วย วิธีการเรียงลำดับจะ
1. เริ่มต้นเปรียบเทียบจากข้อมูลในตำแหน่งที่ 1 กับ 2 หรือข้อมูลในตำแหน่งสุดท้ายและรองสุดท้ายก็ได้
ถ้าเป็นการเรียงลำดับจากน้อยไปมาก
2. จะต้องจัดให้ข้อมูลที่มีค่าน้อยอยู่ในตำแหน่งก่อนข้อมูลที่มีค่ามาก และถ้าเรียงจากมากไปน้อยจะก็จะ
การเรียงลำดับแบบฐาน (radix sort)
เป็นการเรียงลำดับโดยการพิจารณาข้อมูลทีละหลัก
1. เริ่มพิจารณาจากหลักที่มีค่าน้อยที่สุดก่อน นั่นคือถ้าข้อมูลเป็นเลขจำนวนเต็มจะพิจารณาหลักหน่วยก่อน
2. การจัดเรียงจะนำข้อมูลเข้ามาทีละตัว แล้วนำไปเก็บไว้ที่ซึ่งจัดไว้สำหรับค่านั้น เป็นกลุ่ม ๆ ตามลำดับการเข้ามา
3. ในแต่ละรอบเมื่อจัดกลุ่มเรียบร้อยแล้ว ให้รวบรวมข้อมูลจากทุกกลุ่มเข้าด้วยกัน โดยเริ่มเรียงจากกลุ่มที่มีค่าน้อยที่สุดก่อนแล้วเรียงไปเรื่อย ๆ จนหมดทุกกลุ่ม
4. ในรอบต่อไปนำข้อมูลทั้งหมดที่ได้จัดเรียงในหลักหน่วยเรียบร้อยแล้วมาพิจารณาจัดเรียงในหลักสิบต่อไป ทำเช่นนี้ไปเรื่อย ๆ จนกระทั่งครบทุกหลักจะได้ข้อมูลที่เรียงลำดับจากน้อยไปมากตามต้องการ