การจัดเรียงและการค้นหาข้อมูล

การจัดเรียงและค้นหาข้อมูล

ในบทเรียนนี้จะได้เรียนรู้กับขั้นตอนวิธีพื้นฐานในการจัดเรียงข้อมูล (Sort) และการค้นหาข้อมูล (Search) ซึ่งเป็นกิจกรรมที่สัมพันธ์กันที่ใช้ในการแก้ปัญหาที่พบบ่อยในชีวิตประจำวัน

การจัดเรียงข้อมูล

การจัดเรียงข้อมูลเป็นสิ่งที่พบอยู่เสมอ เมื่อต้องการประมวลผลข้อมูลเป็นจำนวนมาก เช่น ครูตรวจข้อสอบของนักเรียน และต้องการบันทึกคะแนนลงสมุดบันทึกคะแนนนักเรียนที่มีการเรียงเลขที่เอาไว้ การเรียงลำดับข้อมูลด้วยเงื่อนไขที่เหมาะสมจะทำให้การค้นหาข้อมูลทำได้อย่างมีประสิทธิภาพ

ตัวอย่างสถานการณ์

ให้เรียงลำดับตัวเลขในตารางด้านล่างนี้ จากน้อยไปหามาก

การจัดเรียงแบบเลือก (Selection sort)

การเรียงลำดับแบบเลือก เป็นขั้นตอนวิธีการเรียงลำดับอย่างง่ายโดยใช้วิธีการเปรียบเทียบ ทำงานโดยการหาค่าเหมาะสมที่สุด (ค่ามากสุดหรือน้อยสุด) ที่อยู่ในรายการส่วนที่ยังไม่เรียงและนำค่าเหมาะที่สุดนั้นมาต่อท้ายของส่วนที่เรียงแล้ว

2. การเรียงลำดับแบบแทรก (Insertion sort)

การเรียงลำดับแบบแทรก เป็นขั้นตอนวิธีการเรียงลำดับอย่างง่าย ทำงานโดยจะแบ่งข้อมูลในรายการเป็นสองส่วนคือส่วนที่เรียงแล้วและส่วนที่ยังไม่เรียง แน่นอนว่าในตอนเริ่มแรกส่วนที่เรียงแล้วก็จะมีอย่างน้อยหนึ่งตัว และจะเริ่มหยิบข้อมูลตัวหนึ่งของส่วนที่ยังไม่เรียงมาเปรียบเทียบเพื่อหาตำแหน่งที่เหมาะสมในการแทรกลงในข้อมูลส่วนที่เรียงแล้ว ลักษณะเดียวกับการเรียงไพ่ในมือ ดังนั้นการเรียงลำดับแบบแทรกจึงไม่เหมาะในการทำงาน ในรายการที่มีจำนวนสมาชิกมาก ๆ

การทำซ้ำ

 การทำซ้ำ

      ในการทำงานบางครั้งย่อมมีการทำงานรูปแบบเดียวกันซ้ำๆ หลายรอบ ซึ่งลักษณะการทำซ้ำ เช่น การทำซ้ำในรายการ การทำซ้ำด้วยเงื่อนไข

การทำซ้ำในรายการ

การทำซ้ำในรายการจะพิจารณาข้อมูลในรายการทีละตัวจนครบทุกรายการโดยมีรูปแบบการพิจารณาคือ

1. ให้ตัวแปร x แทนข้อมูลท่ีพิจารณาอยู่

2. ประมวลผลตัวแปร x

ตัวอย่างการทำซ้ำในรายการ

      ถ้านักเรียนมีเงิน M บาท และมีรายการราคาสินค้า A สามารถเขียน ขั้นตอนวิธีนับจําานวนสินค้าที่มีราคาไม่เกิน M บาทได้ดังนี้

ขั้นตอนวิธี : หาจํานวนสินค้าที่มีราคาไม่เกิน M บาท

ข้อมูลเข้า : ราคาสินค้าในรายการ A

ข้อมูลออก : จํานวนสินค้าที่มีราคาไม่เกิน M บาท

ให้ตัวแปร count ← 0

พิจารณาข้อมูลราคาสินค้าในรายการ A ทีละจําานวน จนครบ

2.1 ให้ x แทนข้อมูลราคาสินค้าที่พิจารณาอยู่

2.2 ถ้า x น้อยกว่าหรือเท่ากับ M แล้ว

              ให้ count ← count + 1

คืนค่าจําานวนสินค้าเท่ากับ count

การทำซ้ำด้วยเงื่อนไข

   การทำซ้ำแบบมีเงื่อนไขเป็นการทำซ้ำที่มีเงื่อนไขในการหยุดการทำซ้ำ ตัวอย่าง 

    ถ้าต้องการประมาณค่าของรากที่สองของ 10 ที่เป็นทศนิยม 3 ตําแหน่ง เขียนขั้นตอนวิธีได้ ดังนี้

ขั้นตอนวิธี : ประมาณค่ารากที่สองของ 10 ที่เป็นทศนิยม 3 ตําแหน่ง

ข้อมูลเข้า : -

ข้อมูลออก : ค่าประมาณของรากที่สองของ 10 ที่เป็นทศนิยม 3 ตําาแหน่ง

ให้ s ← 0

ให้ a ← 0 (เก็บค่าประมาณที่ดีที่สุด)

ทําซ้ำในขณะที่ s ≤ 10

3.1 ถ้า |s2 - 10| < |a2 - 10| แล้ว a ←s

3.2 s ← s + 0.001

คืนค่า a และจบการทําางาน

จากขั้นตอนวิธีข้างต้นเป็นการทําาซ้ำด้วยเงื่อนไข s ≤ 10 ดังนั้นจะมีการทําาซ้ำในข้อ 3.1 และ 3.2 จนกว่า s จะมีค่ามากกว่า 10

การออกแบบขั้นตอนวิธี

  ขั้นตอนวิธี (algorithm) คือ ขั้นตอนการแก้ปัญหาอย่างเป็นลำดับ โดยประกอบด้วยชุดคำสั่งการทำงานอย่างเป็นลำดับและชัดเจน 

        การออกแบบขั้นตอนวิธี (algorithm development) เป็นการออกแบบขั้นตอนในการแก้ปัญหา ซึ่งในปัญหาเดียวกันอาจมีการออกแบบคำสั่งที่ไม่เหมือนกัน ขึ้นอยู่กับประสบการณ์ของผู้แก้ไข แต่หากได้ผลลัพธ์ที่ถูกต้องแล้ว ก็ถือว่าขั้นตอนวิธีสามารถแก้ไขปัญหาได้ การออกแบบขั้นตอนวิธี มีเครื่องมือในการนำเสนอขั้นตอนวิธี ดังนี้

        1) การบรรยาย เป็นการเขียนบรรยายวิธีการแก้ปัญหาอย่างเป็นลำดับ แต่อาจยากต่อการนำไปใช้ เช่น วิธีการต้มบะหมี่กึ่งสำเร็จรูป

 2) การเขียนผังงาน (Flowchart) เป็นการนำเสนอวิธีการแก้ปัญหาโดยการนำขั้นตอนการประมวลผลมาเขียนเป็นรูปแบบของแผนภาพ ประกอบด้วยสัญลักษณ์ต่างๆ ที่มีการกำหนดไว้เป็นมาตรฐาน  ดังนั้น ผังงานโปรแกรมจึงเป็นผังงานที่แสดงลำดับขั้นตอนการทำงานในโปรแกรม
 

                          ตารางแสดงสัญลักษณ์ที่ใช้ในการเขียนผังงาน

ตัวอย่าง การถ่ายทอดความคิดโดยใช้ผังงาน

การระบุข้อมูลเข้า ข้อมูลออก และเงื่อนไขของปํญหา

การระบุข้อมูลเข้า ข้อมูลออก และเงื่อนไขของปัญหา 

1) การวิเคราะห์และกำหนดรายละเอียดของปัญหา   ข้อมูลเข้าคือข้อมูลตอนเริ่มต้นที่โจทย์กำหนดมาให้ตั้งแต่แรก ผู้แก้ปัญหาจะต้องใช้ข้อมูลเหล่านี้ในการประมวลผลเพื่อให้ได้ผลลัพธ์ที่ต้องการ เช่น การเบิกถอนเงินด้วยบัตรเอทีเอ็ม จำเป็นต้องใช้ข้อมูลคือ บัตรเอทีเอ็มและรหัส 4 หลัก

 1.1  การระบุข้อมูลเข้า  ได้แก่ การพิจารณาข้อมูลและเงื่อนไขที่กำหนดมากับปัญหา

  1.2  การระบุข้อมูลออก  ได้แก่ การพิจารณาเป้าหมายหรือสิ่งที่ต้องหาคำตอบหรือผลลัพธ์

 1.3  การกำหนดวิธีประมวลผล  ได้แก่ การพิจารณาวิธีหาคำตอบ หรือผลลัพธ์

2) การวางแผนในการแก้ปัญหา จากการทำความเข้าใจกับปัญหาจะช่วยให้เกิดการคาดคะเนว่าจะใช้วิธีการใดในการแก้ปัญหาเพื่อให้ได้มาซึ่งคำตอบ ประสบการณ์เดิมของผู้แก้ปัญหาจะมีส่วนช่วยอย่างมาก ฉะนั้นในการเริ่มต้นจึงควรจะเริ่มด้วยการถามตนเองว่า “เคยแก้ปัญหาในทำนองเดียวกันนี้มาก่อนหรือไม่” ในกรณีที่มีประสบการณ์มาก่อนควรจะใช้ประสบการณ์เป็นแนวทางในการแก้ปัญหา สิ่งที่จะช่วยให้เราเลือกใช้ประสบการณ์เดิมได้ดีขึ้นคือ การมองดูสิ่งที่ต้องการหา และพยายามเลือกปัญหาเดิมที่มีลักษณะคล้ายคลึงกัน เมื่อเลือกได้แล้วก็เท่ากับมีแนวทางว่าจะใช้ความรู้ใดในการหาคำตอบหรือแก้ปัญหา โดยพิจารณาว่าวิธีการแก้ปัญหาเดิมนั้นมีความเหมาะสมกับปัญหาหรือไม่ หรือต้องมีการปรับปรุงเพื่อให้ได้วิธีการแก้ปัญหาที่ดีขึ้น ในกรณีที่ไม่เคยมีประสบการณ์ในการแก้ปัญหาทำนองเดียวกันมาก่อน ควรเริ่มจากการมองดูสิ่งที่ต้องการหา แล้วพยายามหาวิธีการเพื่อให้ได้ความสัมพันธ์ระหว่างสิ่งที่ต้องการหากับข้อมูลที่มีอยู่ เมื่อได้ความสัมพันธ์แล้วต้องพิจารณาว่าความสัมพันธ์นั้นสามารถหาคำตอบได้หรือไม่ ถ้าไม่ได้ก็แสดงว่าต้องหาข้อมูลเพิ่มเติมหรืออาจจะต้องหาความสัมพันธ์ในรูปแบบอื่นต่อไป เมื่อได้แนวทางในการแก้ปัญหาแล้วจึงวางแผนในการแก้ปัญหาเป็นขั้นตอน

 3) การดำเนินการแก้ปัญหาตามแนวทางที่วางไว้ เมื่อได้วางแผนแล้วก็ดำเนินการแก้ปัญหา ระหว่างการดำเนินการแก้ปัญหาอาจทำให้เห็นแนวทางที่ดีกว่าวิธีที่คิดไว้ ก็สามารถนำมาปรับเปลี่ยนได้

 4) การตรวจสอบ เมื่อได้วิธีการแก้ปัญหาแล้วจำเป็นต้องตรวจสอบว่า วิธีการแก้ปัญหาได้ผลลัพธ์ถูกต้องหรือไม่

ตัวอย่างที่ 1  การวางแผนทำบะหมี่น้ำโดยใช้บะหมี่กึ่งสำเร็จรูป โดยสามารถจำลองความคิดเป็นข้อความได้ดังนี้

1) การวิเคราะห์และกำหนดรายละเอียดของปัญหา

    1.1 การระบุข้อมูลเข้า คือ บะหมี่กึ่งสำเร็จรูป
    1.2 การระบุข้อมูลออก คือ บะหมี่น้ำ
    1.3 การกำหนดวิธีประมวลผล คือ การต้ม

2) การวางแผนในการแก้ปัญหา

    1) เริ่มต้น
    2) ต้มน้ำให้เดือด
    3) ใส่บะหมีลงในน้ำเดือด
    4) รอ 2 นาที
    5)  ใส่เครื่องปรุงแล้วยกหม้อลงจากเตา
    6) จบ

3) การดำเนินการแก้ปัญหาตามแนวทางที่วางไว้ 

    ปฏิบัติตามขั้นตอนในข้อ 2

4) การตรวจสอบ

    บะหมี่น้ำที่ต้มสุก

การแก้ปัญหาด้วยคอมพิวเตอร์

 การทำงานของเครื่องคอมพิวเตอร์ จะทำตามโปรแกรมที่เขียนขึ้นมาทุกประการ

กระบวนการในการแก้ปัญหา  ซึ่งประกอบด้วย 4 ขั้นตอน

1. การวิเคราะห์และกำหนดรายละเอียดของปัญหา

ขั้นตอนนี้เป็นขั้นตอนแรกสุดก่อนที่จะลงมือแก้ปัญหา คือการทำความเข้าใจกับปัญหาเพื่อแยกให้ออกว่าข้อมูลที่กำหนดมาในปัญหาหรือเงื่อนไขของปัญหาคืออะไร และสิ่งที่ต้องการคืออะไร

1.1  การระบุข้อมูลเข้า  ได้แก่ การพิจารณาข้อมูลและเงื่อนไขที่กำหนดมาในปัญหา

1.2  การระบุข้อมูลออก  ได้แก่ การพิจารณาเป้าหมายหรือสิ่งที่ต้องหาคำตอบ

1.3  การกำหนดวิธีประมวลผล  ได้แก่ การพิจารณาขั้นตอนวิธีหาคำตอบหรือข้อมูลออก

2. การเลือกเครื่องมือและออกแบบขั้นตอนวิธี

 ขั้นตอนนี้เป็นขั้นตอนของการวางแผนในการแก้ปัญหาอย่างละเอียดถี่ถ้วน หลังจากที่เราทำความเข้าใจกับปัญหา พิจารณาข้อมูลและเงื่อนไขที่มีอยู่ขั้นตอนนี้จะเริ่มจากการเลือกเครื่องมือที่ใช้ในการแก้ปัญหา โดยพิจารณาความเหมาะสมระหว่างเครื่องมือกับเงื่อนไขต่างๆ ของปัญหาซึ่งหมายรวมถึงความสามารถของเครื่องมือในการแก้ปัญหาดังกล่าว และสิ่งที่สำคัญคือความคุ้นเคยในการใช้งานเครื่องมือนั้นๆ ของผู้แก้ปัญหา

              อีกสิ่งหนึ่งที่สำคัญในการแก้ปัญหา คือยุทธวิธีที่ใช้ในการแก้ปัญหาหรือที่เราเรียกว่า 

ขั้นตอนวิธี (algorithm) ในการแก้ปัญหา  หลังจากที่เราได้เครื่องมือช่วยแก้ปัญหาแล้ว ผู้แก้ปัญหาต้องวางแผนว่าจะใช้เครื่องมือดังกล่าวเพื่อให้ได้ผลลัพธ์ที่ถูกต้องและดีที่สุด การออกแบบขั้นตอนวิธีในการแก้ปัญหา

 3. การดำเนินการแก้ปัญหา

              การดำเนินการแก้ปัญหา (Implementation) หลังจากที่ได้ออกแบบขั้นตอนวิธีเรียบร้อยแล้ว ขั้นตอนนี้เป็นขั้นตอนที่ต้องลงมือแก้ปัญหาโดยใช้เครื่องมือที่ได้เลือกไว้ หากการแก้ปัญหาดังกล่าวใช้คอมพิวเตอร์เข้ามาช่วยง่าน ขั้นตอนนี้ก็เป็นการใช้โปรแกรมสำเร็จหรือใช้ภาษาคอมพิวเตอร์เขียนโปรแกรมแก้ปัญหา ขั้นตอนนี้ต้องอาศัยความรู้เกี่ยวกับเครื่องมือที่เลือกใช้ซึ่งผู้แก้ปัญหาต้องศึกษาให้เข้าใจและเชี่ยวชาญ

  4. การตรวจสอบและปรับปรุง

              การตรวจสอบและปรับปรุง (Refinement) หลังจากที่ลงมือแก้ปัญหาแล้ว ต้องตรวจสอบให้แน่ใจว่าวิธีการนี้ให้ผลลัพธ์ที่ถูกต้อง โดยผู้แก้ปัญหาต้องตรวจสอบว่าขั้นตอนวิธีที่สร้างขึ้นสอดคล้องกับรายละเอียดของปัญหา ซึ่งได้แก่ ข้อมูลเข้า และข้อมูลออก เพื่อให้มั่นใจว่าสามารถรองรับข้อมุเข้าได้ในทุกกรณีอย่างถูกต้องและสมบูรณ์ ในขณะเดียวกันก็ต้องปรับปรุงวิธีการเพื่อให้การแก้ปัญหานี้ได้ผลลัพธ์ที่ดีที่สุด