| ||||
| ||||
| ||||
| ||||
| ||||
|
วันอังคารที่ 12 มิถุนายน พ.ศ. 2555
Stack and Queue Algorithm
Sorting and Searching Algorithm
Introduction:
| |
การจัดเรียงข้อมูล (Sorting)
หมายถึง
การจัดเรียงข้อมูลให้มีการเรียงลำดับตามคีย์ที่ต้องการ
โดยจะทำการเรียงข้อมูลจากค่าที่น้อยไปมาก หรือเรียงข้อมูลจากมากไปน้อยก็ได้ เช่น
รายนามผู้ใช้โทรศัพท์ในสมุดโทรศัพท์ ซึ่งจะทำการเรียงลำดับข้อมูลตามตัวอักษร
ส่วนรายชื่อของนักศึกษา จะทำการเรียงลำดับข้อมูลตามรหัสประจำตัว เป็นต้น
การจัดเรียงลำดับข้อมูลนี้ แม้ว่าจะทำให้เสียเวลาในการจัดเรียง แต่จะมีผลช่วยทำให้การจัดการข้อมูลบางอย่างได้สะดวกและรวดเร็วขึ้น เช่น การค้นหาข้อมูล ดังนั้นการจัดเรียงลำดับข้อมูลจึงเป็นงานที่สำคัญอีกอย่างหนึ่งในระบบงานคอมพิวเตอร์ สแตกเป็นโครงสร้างแบบเชิงเส้น ที่มีลักษณะที่ว่า การนำข้อมูลเข้าสู่สแตก (insertion) และการนำข้อมูลออกจากสแตก (deletion) สามารถจะทำได้ที่ปลายด้านหนึ่งของลิสท์ที่แทนสแตกเท่านั้น ดังนั้นอันดับของการนำสมาชิกเข้าและออกจากสแตกมีความสำคัญ คือ สมาชิกที่เข้าไปอยู่ในสแตกก่อนจะออกจากสแตกหลังสมาชิกที่เข้าไปใน สแตกทีหลัง นั่นคือ การเข้าทีหลังออกก่อน จึงเรียกลักษณะแบบนี้ว่า LIFO (Last In First Out)
ประเภทของการจัดเรียงลำดับข้อมูล
การจัดเรียงลำดับข้อมูลในระบบคอมพิวเตอร์ สามารถแบ่งออกได้เป็น 2 ประเภทใหญ่ๆ คือ 1. การจัดเรียงลำดับภายใน (Internal Sorting) ซึ่งมีวิธีการจัดเรียงลำดับข้อมูลภายในหลายวิธี ได้แก่ 1) Bubble Sort 2) Selection Sort 3) Insertion Sort 4) Quick Sort 5) Shell Sort 6) Heap Sort 7) Radix Sort 2. การจัดเรียงลำดับภายนอก (External Sorting) ซึ่งมีวิธีการจัดเรียงลำดับข้อมูลภายนอกหลายวิธี ได้แก่ 1) Merge Sort 2) Run List 3) การเรียงข้อมูลบนดิสก์ 4) การเรียงข้อมูลบนเทป
การค้นหาข้อมูล (Searching)
ในความต้องการการประมวลผลข้อมูลที่ได้มีการจัดเก็บไว้ในคอมพิวเตอร์นั้น อาจจะจำเป็นจะต้องปรับปรุงข้อมูลให้เกิดความเป็นปัจจุบัน สิ่งแรกที่เราจะต้องทำก่อนคือ ต้องทำการค้นหาข้อมูลนั้นให้ได้เสียก่อน
แล้วจึงนำไปประมวลผลตามความต้องการต่อไป
วิธีการในการค้นหาข้อมูลนั้นมีอยู่มากมายหลายวิธีซึ่งแต่ละวิธีก็มีวิธีการในการทำงานหรือเทคนิคที่แตกต่างกันออกไป ตามแต่คุณสมบัติของแต่ละวิธีนั้น
ผู้ใช้จึงจำเป็นต้องศึกษาและเลือกใช้วิธีการในการค้นหาข้อมูลให้ถูกต้องเหมาะสมกับข้อมูลและควรคำนึงถึงการใช้วเลาในการปฏิบัติการให้น้อยที่สุด
จากตัวอย่างข้อเท็จจริงที่ว่า "ความเร็วในการค้นหาข้อมูลที่เก็บในโครงสร้างอาร์เรย์จะเร็วกว่าการค้นหาข้อมูลที่จัดเก็บใน
linked list แต่ความเร็วของการปรับปรุงข้อมูลใน
linked list จะเร็วกว่าโครงสร้างอาร์เรย์ " ดังนั้นการเลือกใช้โครงสร้างข้อมูลและอัลกอริทึ่มที่เหมาะสมจึงเป็นสิ่งสำคัญในการพัฒนาโปรแกรม
ประเภทของการค้นหาข้อมูล 1. การค้นหาข้อมูลแบบซีเควนเซียล (Sequential Search) 2. การค้นหาข้อมูลแบบไบนารี (Binary Search) 3. การค้นหาแบบ Hashing |
Task:
| |
ให้ค้นหาความหมาย รายละเอียด กระบวนการทำงานของการเรียงลำดับข้อมูล(Sorting) แต่ละประเภท และการค้นหาข้อมูล(Searching) แต่ละประเภทตามแนวทางที่ได้กำหนดไว้ แล้วให้นักศึกษาแต่ละกลุ่มจัดทำรายงานทั้ง 2 เรื่อง โดยให้มีรายละเอียดในรายงานดังต่อไปนี้เป็นอย่างน้อย
- กระบวนการดำเนินงานของการเรียงลำดับข้อมูล(Sorting) และการค้นหาข้อมูล(Searching) ในแต่ละประเภทต่างๆ - การประยุกต์นำเอาการเรียงลำดับและการค้นหาข้อมูลไปใช้ในการทำงาน โดยให้อธิบายถึงรายละเอียดการประยุกต์นั้นลงในรายงาน - ตัวอย่าง Source Code พร้อมทั้งอธิบายประกอบความเข้าใจ |
Process:
| |
- ค้นหาแหล่งข้อมูลจาก Internet ตามแหล่งข้อมูลที่ได้ระบุไว้ หรือเพิ่มเติมไปจากนั้น
- ค้นคว้าจากหนังสือตำราต่างๆ ในห้องสมุด - ประชุมกลุ่มทำงานของนักศึกษา และสรุปแนวความคิดรวมของกลุ่ม - ทำการสรุปแล้วจัดทำเป็นเอกสาร จัดทำเป็นรูปเล่มให้เรียบร้อยและนำส่งในห้องเรียน และให้ส่งไฟล์ไปยัง e-mail ของผู้สอนล่วงหน้า |
Resources
| |
รายชื่อหนังสือประกอบการค้นคว้า
1. ขนิษฐา นามี (๒๕๔๘). โครงสร้างข้อมูลและอัลกอริธึม. นนทบุรี : ไอดีซีฯ. 2. เนรมิต ชุมสาย ณ อยุธยา (๒๕๔๙). เรียนรู้โครงสร้างข้อมูลและอัลกอริธึมด้วย Java. กรุงเทพฯ : ซีเอ็ด ยูเคชั่น. 3. จินดา ยาปนเวช (๒๕๔๕). คู่มือเรียนภาษา Pascal. กรุงเทพฯ : โปรวิชั่น. 4. วรเศรษฐ สุวรรณิก (๒๕๔๙). เขียนโปรแกรม Java เบื้องต้น. กรุงเทพฯ : ซีเอ็ดยูเคชั่น. 5. Clifford A. Shaffer. (2001). A Practical Introduction to Data Structures and Algorithm Analysis, New Jersey : Prentice-Hall. Internet และ YouTube http://www.cp.eng.chula.ac.th/~somchai/ULearn/DataStructures/menu/index.html http://www.sorting-algorithms.com/ http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html http://video.franklin.edu/Franklin/Math/170/common/mod01/binarySearchAlg.html http://www.cosc.canterbury.ac.nz/mukundan/dsal/appldsal.html http://epaperpress.com/sortsearch/index.html http://www.youtube.com/watch?v=INHF_5RIxTE&feature=related และสื่อด้านอื่นๆ |
Evaluation:
| |
เกณฑ์การประเมิน (แบ่งเป็น 3 ระดับ ระดับต่ำ กลาง และสูง)
แยกประเมินผลตามกระบวนการ ในขั้นภาระงาน (task) (ต่ำ)ทำได้ไม่ถึงร้อยละ70 ของหัวข้อทั้งหมด (กลาง)ทำได้ไม่ถึงร้อยละ80 ของหัวข้อทั้งหมด (สูง)ทำได้มากกว่าร้อยละ80ของหัวข้อทั้งหมด ในขั้นกระบวนการ (process) (ต่ำ)สามารถสรุปได้น้อยกว่า5หน้า (กลาง)สามารถสรุปได้มากกว่า5หน้าแต่น้อยกว่า8หน้า (สูง)สามารถสรุปได้มากกว่า8หน้า ในขั้นการประเมินผล (evaluation) (ต่ำ)สอบได้ร้อยละ50ขึ้นไป (กลาง)สอบได้ร้อยละ70ขึ้นไป (สูง)สอบได้ร้อยละ90ขึ้นไป ในขั้นการสรุป (conclusion) (ต่ำ)ผู้เรียนไม่ได้ร่วมสรุป (กลาง)ผู้เรียนร่วมสรุป (สูง)ผู้เรียนสรุป |
Conclusion:
| |
จากการศึกษาตามกระบวนการศึกษา และการสรุปภาพรวมของผู้สอน นักศึกษาจะทราบถึงรายละเอียดในด้านต่างๆ ของการเรียงลำดับข้อมูล (Sorting) และการค้นหาข้อมูล (Searching) ในแต่ละประเภท พร้อมทั้งเข้าใจถึงลักษณะตัวอย่างการนำไปใช้ประกอบการทำงานต่างๆ
|
วันอังคารที่ 25 พฤษภาคม พ.ศ. 2553
Introduction of Data Structure
| ||||
| ||||
| ||||
| ||||
| ||||
|
สมัครสมาชิก:
บทความ (Atom)