ใบความรู้ที่ 2 ม.2

ใบความรู้ ม.2 การออกแบบอัลกอรทิ ึม อัลกอริทึม คอื การเขยี นวิธแี ก้ปัญหาท่ีมลี ำดับขนั้ ตอน การอธบิ ายอัลกอริทมึ แบ่งไดเ้ ป็น 1. การแสดงอัลกอริทึมดว้ ยขอ้ ความหรอื ภาษาธรรมชาติ (Natural Language) คือการใช้ข้อความแสดงขั้นตอนการทำงาน มีส่วนประกอบ 2 ส่วน คือลำดับ และ ขนั้ ตอนการทำงาน 2. การแสดงอลั กอริทึมดว้ ยรหสั จำลองหรือซูโดโคด้ (Pseudocode) คือการ อธบิ ายด้วยข้อความทลี ะขั้นตอน โดยภาษาที่ใช้จะมีความกำ้ ก่งึ กับภาษาคอมพิวเตอร์ 3. การแสดงอัลกอริทึมดว้ ยผงั งานหรือโฟลวชาร์ต (Flowchart) คือแผนผังแสดง ขนั้ ตอนการทำงาน ซ่ึงสามารถใชแ้ ผนผงั น้ีแสดงข้นั ตอนการทำงานของโปรแกรมได้ การแสดงอลั กอริทึมดว้ ยผังงาน มสี ญั ลักษณแ์ ละคำอธบิ ายดงั น้ี

การแสดงอัลกอรทิ มึ ดว้ ยผงั งาน แบง่ ไดเ้ ป็น 2 แบบคอื 1. ผงั งานแบบโครงสรา้ งเรยี งลำดับ (Sequential Structure) 2. ผังงานแบบโครงสรา้ งทางเลอื ก (Selection Structure) เปน็ ผงั งานที่ใชแ้ สดง ทางเลอื กในการตัดสนิ ใจ (Decision) โดยจะมีการใช้สัญลกั ษณ์ “การตดั สนิ ใจตาม เง่อื นไขท่ีกำหนดไว้ (Decision)” อยา่ งนอ้ ย 1 ครั้งในผงั งาน อลั กอรทิ ึมมีประโยชน์ คอื ทำใหไ้ ม่สับสนกบั ขัน้ ตอนทำงาน เพราะทุกอยา่ งจะถกู จัดเรยี งเป็นข้ันตอนวิธีการ และทางเลือกไว้ เม่ือนำขัน้ ตอนวิธีมาประยกุ ตใ์ ช้จะทำใหท้ ำงาน สำเร็จอย่างรวดเรว็ ปญั หาลดลง หรือสามารถคน้ หาต้นเหตขุ องปญั หาได้ เน่ืองจาก กระบวนการถูกแยกแยะกจิ กรรม ข้ันตอนและความสัมพนั ธ์ ออกมาใหเ้ หน็ ชดั เจน การออกแบบอัลกอริทึม (Algorithmic design) คือ การออกแบบข้ันตอนตา่ ง ๆ ใน การแก้ปัญหากอ่ นเขยี นโปรแกรมจริง ตัวอยา่ งการใช้อลั กอรทิ ึมแก้ปญั หา การเรียงลำดบั (Sorting) คือ การจัดเรยี ง ตามปริมาณเวกเตอร์ เช่น ความสูง นำ้ หนกั ขนาด ของคน สตั ว์ หรอื ส่ิงของ ทำไดห้ ลายวธิ ี แตล่ ะวิธใี ชเ้ วลาทีต่ า่ งกัน ดังนี้

เปรยี บเทยี บความเรว็ ในการเรยี งลำดับขอ้ มลู ชนดิ ของการเรียงลำดับ วิธีการโดยย่อ ความเรว็ 1. การเรียงลำดบั แบบเลอื ก n-1 (Selection sort) 2. การเรียงลำดับแบบฟอง สลับท่คี ร้ังละคจู่ ากซ้ายไปขวา เขา้ ใจงา่ ยแตใ่ ช้เวลาในการเรียง (Bubble sort) จนครบแล้ววนกลับมาสลับคา่ ลำดับมาก เหมาะกับขอ้ มลู 3. การเรยี งลำดบั แบบแทรก (Insertion sort) รอบตอ่ ไปจนครบทุกคู่ จำนวนไม่มาก 4. การเรียงลำดบั แบบเชลล์ เรียงจากนอ้ ยไปมาก หาค่าท่ี ใชเ้ วลาน้อย เหมาะกบั ขอ้ มูล (Shell sort) นอ้ ยกวา่ มาวางทางซา้ ยของ จำนวนมาก 5. การเรยี งลำดับแบบฮปี (Heap sort) ขอ้ มูลทม่ี ากกว่าแล้ว 6. การเรยี งลำดับแบบผสาน เปรยี บเทยี บขอ้ มลู รอบใหม่จน (Merge sort) 7. การเรยี งลำดับแบบเรว็ ครบ (Quick sort) แบง่ ขอ้ มลู ครั้งละครึ่งแล้วเรียง ใชเ้ วลานอ้ ยกวา่ แบบแทรก ลำดบั เช่น มขี อ้ มลู 10 ชุด เหมาะกบั ข้อมลู ขนาดใหญ่ ใหเ้ ร่มิ จาก 10/2 คือชดุ ที่ 5 แล้วเรียงลำดับ ใชโ้ ครงสรา้ งแบบตน้ ไม้ทวิภาค เขา้ ถึงขอ้ มูลสำคญั สูงได้งา่ ย (Binary heap) ในการ ใช้เวลาน้อย เปรยี บเทยี บข้อมูลและสลับที่ แบ่งขอ้ มลู เป็นสองส่วนคล้าย ใช้เวลานอ้ ย เหมาะกับขอ้ มลู กบั แบบเชลลแ์ ล้วเปรยี บเทยี บ ขนาดใหญ่ หาค่ากลางสำหรบั เทยี บตัวเลข ใชเ้ วลาน้อย เหมาะสำหรบั โดยนำเลขทมี่ คี า่ มากกว่าวาง ข้อมลู จำนวนมาก ทางขวาตวั เลขท่ีน้อยกวา่ วาง ทางซ้าย