Part of 10306103 หลักการเขียนโปรแกรมเบื้องต้น (Fundamentals of Programming)

บทที่ 10 เทคนิคการแก้ปัญหา: การเรียงลำดับและการค้นหา

แผนบริหารการสอนประจำบทที่ 10

บทนี้ว่าด้วยเทคนิคการแก้ปัญหาด้วยการเรียงลำดับและการค้นหาข้อมูลในอาร์เรย์จำนวนเต็ม ต่อยอดจากอาร์เรย์ในบทที่ 7 ฟังก์ชันในบทที่ 6 และลูปกับเงื่อนไขในบทที่ 4–5 โดยอธิบายการเรียงลำดับแบบ selection sort ที่หาสมาชิกน้อยที่สุดในส่วนที่เหลือแล้วสลับมาไว้ตำแหน่งปัจจุบัน การค้นหาเชิงเส้น (linear search) ที่ตรวจทีละสมาชิก การค้นหาแบบทวิภาค (binary search) ที่ตัดช่วงค้นหาครึ่งหนึ่งทุกรอบบนอาร์เรย์ที่เรียงแล้ว และแนวคิดประสิทธิภาพเบื้องต้นด้วยการนับจำนวนรอบการเปรียบเทียบ เพื่อให้เลือกวิธีแก้ปัญหาที่เหมาะสมกับสถานการณ์ได้อย่างมีเหตุผล

CLO ที่เกี่ยวข้อง (ข้อความจากหลักสูตร):

• CLO2 อธิบายขั้นตอนการทำงาน (Logic) ของภาษาโปรแกรมและเลือกใช้โครงสร้างควบคุม (Control Structure) ให้สอดคล้องกับโจทย์ที่กำหนดได้
• CLO3 สามารถเขียนโค้ดได้ถูกต้องตามหลักไวยากรณ์ (Syntax) และมีประสิทธิภาพ (Efficiency)

บทที่ 10 เป็นจุดที่นำอาร์เรย์จากบทที่ 7 ฟังก์ชันจากบทที่ 6 และลูปกับเงื่อนไขจากบทที่ 4–5 มาประกอบกันเป็นขั้นตอนวิธี (algorithm) สำหรับเรียงลำดับและค้นหาข้อมูล จึงเป็นสะพานเชื่อมไปสู่การวัดประสิทธิภาพเบื้องต้นและคุณภาพโค้ดในบทที่ 12 และโครงงานบูรณาการในบทที่ 15 งานทั้งสามข้อในบทนี้สะสมหลักฐานของ CLO2 และ CLO3 ต่อเนื่องจากบทก่อน งานของบทนี้อยู่ในหมวดงานท้ายบทตามแผนคะแนนที่ผู้สอนยืนยันไว้ ดูรายละเอียดในบันทึกสำหรับผู้สอนท้ายบท

วิธีสอน

1. ทบทวนอาร์เรย์และการส่งอาร์เรย์เข้าฟังก์ชันจากบทที่ 7 การออกแบบฟังก์ชันคืนค่าจากบทที่ 6 และลูปกับเงื่อนไขจากบทที่ 4–5 แล้วตั้งโจทย์ที่ต้องจัดเรียงและค้นหาข้อมูล เช่น เรียงคะแนนจากน้อยไปมากแล้วค้นหาค่าหนึ่ง เพื่อชี้ให้เห็นความจำเป็นของขั้นตอนวิธีที่เป็นระบบ
2. แนะนำการเรียงลำดับแบบ selection sort โดยสาธิตบนเครื่องจริงทีละรอบ ย้ำการหาสมาชิกน้อยที่สุดในส่วนที่เหลือและการสลับค่าสองตัวด้วยตัวแปรชั่วคราว
3. สาธิตการค้นหาเชิงเส้นที่ตรวจทีละสมาชิกจนพบและคืนดัชนี หรือคืน -1 เมื่อไม่พบ และชี้ว่าใช้ได้กับอาร์เรย์ที่ยังไม่เรียง
4. สาธิตการค้นหาแบบทวิภาคบนอาร์เรย์ที่เรียงแล้วด้วยตัวแปร low, mid, high และย้ำว่าต้องเรียงข้อมูลก่อนเสมอ พร้อมชี้กับดักเงื่อนไขลูปที่ทำให้วนไม่รู้จบ
5. อธิบายประสิทธิภาพเบื้องต้นด้วยการนับจำนวนรอบการเปรียบเทียบ แล้วให้ลงมือปฏิบัติตามใบงาน โดยกำหนดจุดตรวจระหว่างทางเพื่อให้ข้อมูลป้อนกลับทันที

สื่อการเรียนการสอน

• เครื่องคอมพิวเตอร์ที่เข้าถึงแพลตฟอร์มการเรียนของรายวิชาสำหรับเขียน คอมไพล์ และรันโปรแกรมภาษา C (มาตรฐาน C11) บนเว็บ
• เอกสารประกอบบทที่ 10 และสไลด์สรุป selection sort การค้นหาเชิงเส้น การค้นหาแบบทวิภาค และการนับจำนวนรอบการเปรียบเทียบ
• ไฟล์โปรแกรมตัวอย่าง ch10_sortsearch.c

การวัดผลและการประเมินผล

กำหนดส่ง: งานข้อ 1–3 ภายใน 23:59 น. ของวันก่อนวันปฏิบัติการในสัปดาห์ที่ 11 ส่วนชุดฝึกท้ายบทและแบบฝึกหัดวัดความเข้าใจของบทนี้ ภายใน 23:59 น. ของวันก่อนวันบรรยายในสัปดาห์ที่ 11 ดูวันที่จริงของตอนเรียนได้ในห้องเรียนออนไลน์ (มติผู้สอน 28 ต.ค. 2569)

เงื่อนไขผ่าน: งานข้อ 2 ส่วนการค้นหาแบบทวิภาคประเมินจากไฟล์เดียวกับงานข้อ 1 ที่เรียงอาร์เรย์ก่อน เพราะการค้นหาแบบทวิภาคใช้ได้เฉพาะอาร์เรย์ที่เรียงแล้ว ดังนั้นงานข้อ 1 ต้องเรียงอาร์เรย์ถูกต้องและคอมไพล์ผ่านก่อนจึงจะประเมินการค้นหาแบบทวิภาคในงานข้อ 2 ได้

คะแนนใบงาน (10 คะแนน)

ใบงานบทที่ 1–13 รวมกันคิดเป็น 15% ของคะแนนรายวิชา ชิ้นละเท่ากัน ส่งช้าหัก 10% ของคะแนนงานต่อสัปดาห์ที่ช้า สูงสุด 50% และรับงานถึงสิ้นสัปดาห์ที่ 15 งานที่ผู้สอนส่งกลับให้แก้นับเวลาจากการส่งครั้งแรก ดูคะแนนของตนเองได้ที่หน้า “คะแนนของฉัน” ในห้องเรียนออนไลน์ของรายวิชา

เกณฑ์ให้คะแนน

งานข้อ 1 ใช้เกณฑ์ผ่าน/ไม่ผ่าน:

งานข้อ 2 ใช้เกณฑ์ผ่าน/ไม่ผ่าน ร่วมกับรายการตรวจ (checklist): การค้นหาเชิงเส้นและการค้นหาแบบทวิภาคคืนดัชนีที่พบหรือ -1 ถูกต้อง, การค้นหาแบบทวิภาคใช้กับอาร์เรย์ที่เรียงแล้วเท่านั้น, เงื่อนไขลูปของการค้นหาแบบทวิภาคถูกต้องไม่วนไม่รู้จบ, จัดย่อหน้า 4 ช่องว่างและมีคอมเมนต์ส่วนหัว

งานข้อ 3 ใช้เกณฑ์ผ่าน/ไม่ผ่าน ร่วมกับรายการตรวจ: นับจำนวนรอบการเปรียบเทียบของแต่ละวิธีได้ถูกต้อง, อธิบายได้ว่าการค้นหาแบบทวิภาคใช้รอบน้อยกว่าเมื่อข้อมูลเรียงแล้วและมีจำนวนมาก, ระบุเงื่อนไขการเลือกวิธีให้เหมาะกับสถานการณ์

เฉลยจะเปิดในชั้นเรียนหลังทุกคนทำเสร็จ

บทนำ

โปรแกรมจำนวนมากต้องจัดเรียงข้อมูลให้เป็นระเบียบและค้นหาค่าที่ต้องการจากข้อมูลชุดหนึ่ง เช่น เรียงคะแนนของนักศึกษาจากน้อยไปมากแล้วค้นหาว่ามีคะแนนค่าหนึ่งอยู่ที่ตำแหน่งใด การเรียงลำดับและการค้นหาจึงเป็นเทคนิคการแก้ปัญหาพื้นฐานที่ใช้ได้กับงานหลากหลาย บทที่ 7 ได้แนะนำอาร์เรย์และการส่งอาร์เรย์เข้าฟังก์ชัน บทที่ 6 ได้แนะนำฟังก์ชันคืนค่า และบทที่ 4–5 ได้แนะนำเงื่อนไขและลูปไปแล้ว บทนี้นำทั้งหมดมาประกอบเป็นขั้นตอนวิธีสำหรับเรียงลำดับด้วย selection sort และค้นหาด้วยการค้นหาเชิงเส้นและการค้นหาแบบทวิภาค พร้อมอธิบายประสิทธิภาพเบื้องต้นเพื่อเลือกวิธีที่เหมาะสม

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

ความรู้พื้นฐาน เครื่องมือ และรุ่นซอฟต์แวร์

บทนี้ต้องใช้คอมไพเลอร์ภาษา C และโปรแกรมแก้ไขข้อความหรือ IDE และต้องมีความรู้เรื่องอาร์เรย์และการส่งอาร์เรย์เข้าฟังก์ชันจากบทที่ 7 การออกแบบฟังก์ชันคืนค่าจากบทที่ 6 และลูปกับเงื่อนไขจากบทที่ 4–5 ตารางด้านล่างเป็นรุ่นเครื่องมือที่ใช้ทดสอบโค้ดตัวอย่างในบทนี้จริง

วิธีใช้บทเรียนและใบงานในหน้านี้

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

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

ข้อมูลทั้งหมดเป็นข้อมูลสมมติ กติกาจัดอันดับในตัวอย่างไม่ใช่อันดับทางการของรายวิชา กิจกรรมเพิ่มไม่เปลี่ยน LLO10.1–10.3 งานส่ง หรือสัดส่วนคะแนน เวลาและแนวคำตอบอยู่เฉพาะส่วนผู้สอน

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

10.1 แนวคิดการเรียงลำดับและ selection sort

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

ระดับที่ 2: selection sort ทำงานโดยไล่ตำแหน่งปัจจุบัน i ตั้งแต่ตัวแรก ในแต่ละรอบจะกำหนดให้ตำแหน่ง i เป็นตำแหน่งของค่าน้อยที่สุดไว้ก่อน แล้ววนหาสมาชิกที่น้อยกว่าในส่วนที่เหลือด้วยลูปซ้อนจากบทที่ 5 เมื่อพบตำแหน่งของค่าน้อยที่สุดจริงจึงสลับค่าของสองตำแหน่งนั้น การสลับค่าสองตัวต้องใช้ตัวแปรชั่วคราวเพื่อไม่ให้ค่าหนึ่งทับอีกค่าหนึ่ง ดังรูปแบบ temp = a; a = b; b = temp;

void selection_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
}

ระดับที่ 3: ประเด็นที่ต้องไล่ให้เห็นทีละรอบคือ ลูปนอกเลื่อนตำแหน่งปัจจุบัน i ไปทีละหนึ่ง ส่วนลูปในเริ่มที่ j เท่ากับ i + 1 เพื่อเทียบเฉพาะส่วนที่ยังไม่เรียง เมื่อครบหนึ่งรอบ สมาชิกตั้งแต่ตำแหน่ง 0 ถึง i จะเรียงเรียบร้อยแล้ว กับดักที่พบบ่อยคือการสลับค่าผิดตำแหน่งหรือลืมใช้ตัวแปรชั่วคราว ถ้าเขียน arr[i] = arr[min_idx]; ก่อนเก็บค่าเดิมของ arr[i] ไว้ ค่าเดิมจะสูญหายและข้อมูลจะผิด การใช้ตัวแปร temp เก็บค่าเดิมไว้ก่อนจึงจำเป็น

คำถามตรวจความเข้าใจ 10.1: ในแต่ละรอบของ selection sort สมาชิกใดที่ถูกเลือกมาไว้ที่ตำแหน่งปัจจุบัน และเหตุใดการสลับค่าสองตัวจึงต้องใช้ตัวแปรชั่วคราว

ใบงาน 1: เลือกตำแหน่งต่ำสุดให้ครบก่อนสลับ

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

ทำซ้ำกับ 1 2 3 4 และ 4 3 2 1 โดยแยกจำนวนเปรียบเทียบจากจำนวนสลับจริง โค้ดที่ยังค้นต่ำสุดครบทุกช่วงไม่ลดจำนวนเปรียบเทียบเพียงเพราะข้อมูลดูเรียงแล้ว

สำหรับ selection sort ฉบับในบท เมื่อ n ไม่ติดลบ จำนวนเปรียบเทียบค่าคือ n * (n - 1) / 2 ครั้ง กรณี n เป็น 0 หรือ 1 ไม่มีรอบเปรียบเทียบ สูตรนี้ใช้กับรูปแบบลูปนี้ ไม่ใช่จำนวนคำสั่งทั้งหมดของโปรแกรม

ตัวอย่างพร้อมใช้: แสดงแต่ละรอบและนับงานสองชนิด

สร้างไฟล์ selection_trace.c รับ n ช่วง 0–8 ตามด้วยจำนวนเต็ม n ค่าในช่วง -100 ถึง 100 นับเฉพาะการเทียบสมาชิกเพื่อเลือกค่าต่ำสุด และนับสลับเมื่อเป็นคนละตำแหน่ง

/* selection_trace.c : comparisons and real swaps are different counts */
#include <stdio.h>
 
void selection_trace(int values[], int count);
 
int main(void)
{
    int values[8];
    int count;
    if (scanf("%d", &count) != 1) {
        puts("Input error");
        return 1;
    }
    if (count < 0 || count > 8) {
        puts("Range error");
        return 1;
    }
    for (int i = 0; i < count; ++i) {
        if (scanf("%d", &values[i]) != 1) {
            puts("Input error");
            return 1;
        }
        if (values[i] < -100 || values[i] > 100) {
            puts("Range error");
            return 1;
        }
    }
    selection_trace(values, count);
    printf("sorted:");
    for (int i = 0; i < count; ++i) {
        printf(" %d", values[i]);
    }
    puts("");
    return 0;
}
 
void selection_trace(int values[], int count)
{
    int comparisons = 0;
    int swaps = 0;
    for (int i = 0; i < count - 1; ++i) {
        int minimum = i;
        for (int j = i + 1; j < count; ++j) {
            ++comparisons;
            if (values[j] < values[minimum]) {
                minimum = j;
            }
        }
        if (minimum != i) {
            int temporary = values[i];
            values[i] = values[minimum];
            values[minimum] = temporary;
            ++swaps;
        }
        printf("pass=%d:", i);
        for (int k = 0; k < count; ++k) {
            printf(" %d", values[k]);
        }
        puts("");
    }
    printf("comparisons=%d swaps=%d\n", comparisons, swaps);
}

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

10.2 การค้นหาเชิงเส้น

ระดับที่ 1: การค้นหาเชิงเส้น (linear search) คือการค้นหาค่าที่ต้องการโดยตรวจสมาชิกทีละตัวจากต้นอาร์เรย์ไปจนพบ วิธีนี้ตรงไปตรงมาและใช้ได้กับอาร์เรย์ที่ยังไม่เรียง

ระดับที่ 2: linear_search วนอาร์เรย์ด้วยลูป for จากบทที่ 5 แล้วเทียบสมาชิกแต่ละตัวกับค่าที่ค้นหาด้วยตัวดำเนินการ == จากบทที่ 4 เมื่อพบจะคืนดัชนีของตำแหน่งนั้นทันทีด้วย return จากบทที่ 6 ถ้าวนครบทุกสมาชิกแล้วยังไม่พบจะคืนค่า -1 เพื่อสื่อว่าไม่พบ

int linear_search(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

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

คำถามตรวจความเข้าใจ 10.2: การค้นหาเชิงเส้นคืนค่าใดเมื่อพบค่าที่ต้องการ และคืนค่าใดเมื่อค้นหาจนครบแล้วไม่พบ

ใบงาน 2: การพบตัวแรกกับตำแหน่งหลังเรียง

ใช้ข้อมูล 4 1 4 2 ค้นหา 4 ด้วย linear search ก่อนเรียง แล้วเรียงและค้นหาใหม่ ตอบว่าค่าคืนเป็นตำแหน่งของข้อมูลชุดใด ไม่ใช้ดัชนีหลังเรียงไปอ้างลำดับรับเข้าเดิม

linear_search ในบทเริ่มจากดัชนี 0 และ return ทันทีเมื่อพบ จึงคืนตัวแรกในลำดับปัจจุบัน หากไม่พบให้ -1 และผู้เรียกต้องตรวจค่านี้ก่อนอ่านสมาชิก ห้ามใช้ if (index) แทนสัญญานี้

10.3 การค้นหาแบบทวิภาค

ระดับที่ 1: การค้นหาแบบทวิภาค (binary search) คือการค้นหาที่ตัดช่วงค้นหาให้เหลือครึ่งหนึ่งในทุกรอบ จึงค้นหาได้เร็วกว่าการค้นหาเชิงเส้นมากเมื่อข้อมูลมีจำนวนมาก แต่ใช้ได้เฉพาะอาร์เรย์ที่เรียงแล้วเท่านั้น

ระดับที่ 2: binary_search ใช้ตัวแปรขอบเขตสามตัวคือ low (ขอบล่าง), high (ขอบบน) และ mid (ตำแหน่งกลาง) โดยเริ่มจาก low เท่ากับ 0 และ high เท่ากับ n - 1 ในแต่ละรอบจะคำนวณตำแหน่งกลาง mid แล้วเทียบ arr[mid] กับค่าที่ค้นหา ถ้าเท่ากันก็คืนดัชนี mid ถ้าค่ากลางน้อยกว่าค่าที่ค้นหาแสดงว่าค่าที่ต้องการอยู่ครึ่งขวา จึงเลื่อน low เป็น mid + 1 ถ้าค่ากลางมากกว่าแสดงว่าอยู่ครึ่งซ้าย จึงเลื่อน high เป็น mid - 1 ลูปทำงานต่อขณะที่ low <= high และคืน -1 เมื่อไม่พบ

int binary_search(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

ระดับที่ 3: เงื่อนไขลูป low <= high ต้องใช้เครื่องหมาย <= ไม่ใช่ < เพราะเมื่อช่วงค้นหาเหลือสมาชิกตัวเดียว low จะเท่ากับ high และยังต้องตรวจสมาชิกตัวนั้น การปรับ low และ high ต้องขยับพ้นตำแหน่ง mid เสมอด้วย mid + 1 และ mid - 1 มิฉะนั้นช่วงค้นหาจะไม่แคบลงและเกิดลูปไม่รู้จบ กับดักสำคัญอีกข้อคือการนำการค้นหาแบบทวิภาคไปใช้กับอาร์เรย์ที่ยังไม่เรียง ซึ่งจะให้ผลผิด เพราะการตัดครึ่งช่วงอาศัยสมมติฐานว่าข้อมูลเรียงแล้ว จึงต้องเรียงข้อมูลก่อนเสมอ

คำถามตรวจความเข้าใจ 10.3: การค้นหาแบบทวิภาคใช้กับอาร์เรย์ที่ยังไม่เรียงได้หรือไม่ เพราะเหตุใด

ใบงาน 3: ขอบเขตต้องหดและยังตรวจตำแหน่งสุดท้าย

ใช้ชุดเรียง 10 20 30 40 50 60 70 กรอกหนึ่งตารางสำหรับเป้าหมาย 60 และอีกตารางสำหรับ 65 บันทึก low/high หลังเลือกช่วงใหม่ให้ครบถึงกรณีพบหรือช่วงว่าง

เพิ่มชุดหนึ่งสมาชิกและสองสมาชิก เพื่อดูว่าถ้าใช้ low < high แทน low <= high ในรูปแบบขอบเขตรวมปลายทั้งสอง จะพลาดสมาชิกสุดท้ายได้ การใช้เงื่อนไขผิดนี้ไม่ใช่เหตุเดียวกับการปรับขอบเขตไม่พ้น mid จนวนค้าง

สูตรกลาง low + (high - low) / 2 ใช้เมื่อขอบเขตเป็นดัชนีไม่ติดลบและ low ไม่เกิน high ภายในลูป ช่วยเลี่ยงการบวกดัชนีสองค่าที่อาจเกินช่วง ไม่ได้ทำให้การส่ง count ผิดพื้นที่กลายเป็นปลอดภัย

10.4 ประสิทธิภาพเบื้องต้น

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

ระดับที่ 2: selection sort ต้องเทียบสมาชิกในส่วนที่เหลือทุกรอบ จำนวนการเปรียบเทียบจึงประมาณ n·n/2 ครั้ง ซึ่งเป็นประสิทธิภาพระดับกำลังสองและโตเร็วเมื่อ n เพิ่มขึ้น การค้นหาเชิงเส้นในกรณีแย่สุดตรวจทุกสมาชิกจึงใช้รอบประมาณ n ครั้ง ส่วนการค้นหาแบบทวิภาคตัดช่วงเหลือครึ่งหนึ่งทุกรอบจึงใช้รอบประมาณ log2(n) ครั้ง ตัวอย่างเชิงเปรียบเทียบคือ เมื่อ n เท่ากับ 1000 การค้นหาเชิงเส้นอาจใช้ถึงประมาณ 1000 รอบ แต่การค้นหาแบบทวิภาคใช้เพียงประมาณ 10 รอบ

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

คำถามตรวจความเข้าใจ 10.4: เมื่อข้อมูลมีจำนวนมากและเรียงแล้ว เหตุใดการค้นหาแบบทวิภาคจึงใช้รอบการเปรียบเทียบน้อยกว่าการค้นหาเชิงเส้น

ตัวอย่างนับรอบค้นหา: กำหนดหน่วยให้เหมือนกันก่อนเทียบ

สร้างไฟล์ search_probes.c รับ n ช่วง 0–10 จำนวนเต็มที่เรียงจากน้อยไปมากหรือเท่ากัน n ค่า และเป้าหมายหนึ่งค่า ทุกค่าช่วง -100 ถึง 100 โปรแกรมตรวจลำดับก่อนเรียก binary search

/* search_probes.c : count examined elements, not CPU time */
#include <stdio.h>
 
struct SearchResult {
    int index;
    int probes;
};
 
struct SearchResult linear_probe(const int values[], int count, int target);
struct SearchResult binary_probe(const int values[], int count, int target);
 
int main(void)
{
    int values[10];
    int count;
    int target;
    if (scanf("%d", &count) != 1) {
        puts("Input error");
        return 1;
    }
    if (count < 0 || count > 10) {
        puts("Range error");
        return 1;
    }
    for (int i = 0; i < count; ++i) {
        if (scanf("%d", &values[i]) != 1) {
            puts("Input error");
            return 1;
        }
        if (values[i] < -100 || values[i] > 100) {
            puts("Range error");
            return 1;
        }
    }
    if (scanf("%d", &target) != 1) {
        puts("Input error");
        return 1;
    }
    if (target < -100 || target > 100) {
        puts("Range error");
        return 1;
    }
    for (int i = 1; i < count; ++i) {
        if (values[i - 1] > values[i]) {
            puts("Not sorted");
            return 1;
        }
    }
    struct SearchResult linear = linear_probe(values, count, target);
    struct SearchResult binary = binary_probe(values, count, target);
    printf("linear index=%d probes=%d\n", linear.index, linear.probes);
    printf("binary index=%d probes=%d\n", binary.index, binary.probes);
    return 0;
}
 
struct SearchResult linear_probe(const int values[], int count, int target)
{
    struct SearchResult result = {-1, 0};
    for (int i = 0; i < count; ++i) {
        ++result.probes;
        if (values[i] == target) {
            result.index = i;
            return result;
        }
    }
    return result;
}
 
struct SearchResult binary_probe(const int values[], int count, int target)
{
    struct SearchResult result = {-1, 0};
    int low = 0;
    int high = count - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        ++result.probes;
        if (values[mid] == target) {
            result.index = mid;
            return result;
        }
        if (values[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

หนึ่ง probe หมายถึงนำสมาชิกหนึ่งตำแหน่งมาตรวจ ไม่ใช่นับทุกตัวดำเนินการ == หรือ < ไม่รวมการตรวจข้อมูลเรียงและไม่รวมการรับข้อมูล จึงเปรียบเทียบหน่วยเดียวกันได้ แต่ยังไม่ใช่เวลารันจริง

ใช้ชุดเจ็ดค่าของใบงาน 3 ทดลองเป้าหมาย 10, 40, 60, 70 และ 65 แล้วเพิ่มชุดว่างกับชุดค่า 20 ซ้ำ หากสัญญา binary คือพบสักตำแหน่ง ผลดัชนีของสองวิธีอาจต่างกันโดยทั้งคู่ยังถูก

10.5 กรณีศึกษาต่อเนื่อง: ค้นหารหัสกับจัดอันดับคะแนนเป็นคนละงาน

ข้อมูลระเบียนชุดเดียวอาจต้องค้นหาตามรหัสและแสดงอันดับตามคะแนน ถ้าเรียงตามคะแนนแล้วนำ binary search ที่เปรียบเทียบรหัสมาใช้ จะขาดเงื่อนไขพื้นฐานของวิธีค้นหา เพราะข้อมูลไม่ได้เรียงตามกุญแจเดียวกับที่ค้นหา การพูดว่า “อาร์เรย์เรียงแล้ว” จึงยังไม่ครบ ต้องบอกว่าเรียงตามอะไรและทิศทางใด

10.5.1 ไล่ selection sort โดยแยกตำแหน่งที่เสร็จกับส่วนที่เหลือ

เริ่มข้อมูล 29, 10, 14, 10 ต้องการเรียงจากน้อยไปมาก รอบแรกหาค่าน้อยสุดในช่วงดัชนี 0–3 พบ 10 ที่ดัชนี 1 แล้วสลับกับตำแหน่ง 0 ได้ 10, 29, 14, 10 ตำแหน่ง 0 เสร็จแล้ว รอบต่อไปค้นเฉพาะช่วง 1–3 ไม่ย้อนกลับไปรื้อส่วนที่เสร็จ

จำนวนครั้งที่เปรียบเทียบในตัวอย่างนี้เป็น 3 + 2 + 1 รวม 6 ครั้ง แม้ข้อมูลหลังรอบสองจะดูเรียงแล้ว อัลกอริทึมแบบพื้นฐานยังทำรอบที่เหลือตามโครงสร้าง การมีข้อมูลเรียงอยู่ก่อนจึงไม่ได้ลดจำนวนเปรียบเทียบของ selection sort แบบนี้เหมือนบางวิธีอื่น

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

10.5.2 ไล่ binary search ด้วยขอบเขตที่หดลง

ใช้ข้อมูลเรียง 10, 20, 30, 40, 50, 60, 70 และค้นหา 60 เริ่ม low=0, high=6 ได้กลาง 3 ค่า 40 เพราะเป้าหมายมากกว่า 40 จึงตัดช่วง 0–3 ทิ้ง แล้วตั้ง low=4 รอบถัดไปกลาง 5 พบ 60

ถ้าค้นหา 65 รอบแรกตัดครึ่งล่างเหมือนเดิม รอบสองพบ 60 จึงเหลือดัชนี 6 ซึ่งมี 70 จากนั้นเป้าหมายน้อยกว่า 70 ทำให้ high=5 เมื่อ low=6 มากกว่า high=5 จึงจบโดยไม่พบ ช่วงว่างเป็นหลักฐานว่าพื้นที่ที่เป็นไปได้ถูกตรวจครบตามการตัดช่วงแล้ว

#include <stdio.h>
 
int binary_search(const int values[], int count, int target)
{
    int low = 0;
    int high = count - 1;
 
    while (low <= high) {
        int middle = low + (high - low) / 2;
        if (values[middle] == target) {
            return middle;
        }
        if (values[middle] < target) {
            low = middle + 1;
        } else {
            high = middle - 1;
        }
    }
    return -1;
}
 
int main(void)
{
    const int values[] = {10, 20, 30, 40, 50, 60, 70};
 
    printf("%d %d %d\n",
           binary_search(values, 7, 60),
           binary_search(values, 7, 65),
           binary_search(values, 0, 60));
    return 0;
}

ผลคือ 5 -1 -1 ฟังก์ชันสมมติว่า count ไม่ติดลบ ข้อมูลที่ใช้มีจำนวนเพียงพอ และเรียงจากน้อยไปมากแล้ว กรณี count=0 ไม่เข้าสู่ลูปจึงไม่อ่านสมาชิกใด ส่วน middle + 1 กับ middle - 1 ทำให้ตำแหน่งที่ตรวจไปแล้วถูกตัดออกจริง หากใช้ low = middle บางช่วงอาจไม่หดจนเกิดลูปไม่จบ

รูปแบบหาตำแหน่งกลางช่วยหลีกเลี่ยงผลรวมดัชนีที่ใหญ่เกินช่วงเมื่อขอบเขตเป็นดัชนีไม่ติดลบ อ่านเหตุผลและเงื่อนไขอาร์เรย์เรียงได้จาก NIST: Binary Search

10.6 คำตอบที่ถูกต้องขึ้นอยู่กับสัญญาการค้นหา

10.6.1 พบหนึ่งตำแหน่งไม่เท่ากับพบตัวแรกเสมอ

สำหรับข้อมูล 10, 20, 20, 20, 30 ฟังก์ชันข้างต้นอาจพบ 20 ที่กลางได้ทันที นั่นเป็นคำตอบถูกของคำถามว่า “มีค่าหรือไม่และอยู่สักตำแหน่งใด” แต่ยังไม่ตอบคำถามว่า “20 ตัวแรกอยู่ที่ใด” หรือ “มีทั้งหมดกี่ตัว” ต้องเปลี่ยนอัลกอริทึมหรือค้นต่อภายใต้สัญญาใหม่

การออกแบบค่าคืนควรแยกดัชนี 0 ซึ่งเป็นตำแหน่งปกติออกจาก -1 ที่หมายถึงไม่พบ หากเขียน if (position) จะตีความตำแหน่งศูนย์ว่าเท็จและ -1 ว่าจริง จึงผิดทั้งสองแบบ ต้องตรวจ position >= 0 ก่อนนำไปใช้เป็นดัชนี

10.6.2 รวมต้นทุนเตรียมข้อมูลเมื่อเลือกวิธี

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

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

ตัวอย่างเปลี่ยนสัญญา: ค้นหาตำแหน่งแรกของค่าซ้ำ

สร้างไฟล์ binary_first.c เมื่อพบค่าเท่ากันให้จำตำแหน่งไว้แล้วค้นต่อทางซ้าย วิธีนี้เพิ่มงานให้ตรงคำถาม “ตัวแรกอยู่ที่ใด” แทนการ return ทันทีเหมือน binary search แบบเดิม

/* binary_first.c : first matching index in a sorted array */
#include <stdio.h>
 
int binary_first(const int values[], int count, int target);
 
int main(void)
{
    const int values[5] = {10, 20, 20, 20, 30};
    int target;
    if (scanf("%d", &target) != 1) {
        puts("Input error");
        return 1;
    }
    printf("first=%d\n", binary_first(values, 5, target));
    return 0;
}
 
int binary_first(const int values[], int count, int target)
{
    int answer = -1;
    int low = 0;
    int high = count - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (values[mid] >= target) {
            if (values[mid] == target) {
                answer = mid;
            }
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return answer;
}

ทำนายเมื่อค้นหา 10, 20, 30 และ 25 แล้วชี้ว่ารอบที่พบ 20 กลางกลุ่มยังไม่จบ ในการส่ง count เป็น 0 ฟังก์ชันต้องคืน -1 โดยไม่อ่านสมาชิก ส่วน count ปกติต้องไม่เกินพื้นที่จริงและข้อมูลต้องเรียงแล้ว

10.7 เวิร์กช็อปขยาย: นับ เปรียบเทียบ และอธิบายข้อจำกัด

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

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

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

10.8 ตัวอย่างเปรียบเทียบ: เรียงแล้วต้องไม่ทำข้อมูลหาย

หลัง sort ตัวเลข 4, 1, 4, 2 ควรได้ 1, 2, 4, 4 เงื่อนไขว่าค่าไม่ลดลงเมื่อเดินจากซ้ายไปขวายังไม่พอ เพราะผลผิดอย่าง 1, 2, 4, 4, 4 ดูเรียงได้แต่มีข้อมูลเกิน และ 1, 2, 4 ก็เรียงได้แต่ข้อมูลหาย ต้องตรวจทั้งลำดับ จำนวน และสมาชิกเดิม

สำหรับระเบียนรหัส A คะแนน 80 รหัส B คะแนน 60 และรหัส C คะแนน 80 ให้ติดตามคู่รหัสกับคะแนนตลอดการสลับ ถ้าสลับคะแนนอย่างเดียวอาจได้แถวรหัส A คะแนน 60 ซึ่งไม่เคยมีอยู่เดิม ข้อผิดพลาดนี้ไม่ถูกจับด้วยการตรวจว่าคะแนนเรียงแล้วเพียงอย่างเดียว

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

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

ตัวอย่างระเบียน: เรียงตามคะแนนแล้วค้นหารหัสอย่างมีเหตุผล

สร้างไฟล์ rank_records.c เรียงคะแนนสมมติจากมากไปน้อย ถ้าคะแนนเท่ากันเรียงรหัสจากน้อยไปมาก การตัดสินรหัสรองเป็นกติกาฝึก ไม่ใช่ข้อสรุปว่า selection sort รักษาลำดับเดิมของค่าที่เท่ากัน

/* rank_records.c : explicit secondary key and whole-record swaps */
#include <stdio.h>
#include <string.h>
 
struct Student {
    char code[5];
    char name[16];
    int score;
};
 
int comes_before(struct Student a, struct Student b);
void rank_records(struct Student room[], int count);
int find_code(const struct Student room[], int count, const char code[]);
 
int main(void)
{
    struct Student room[4] = {
        {"0017", "Sample-A", 80},
        {"0018", "Sample-B", 60},
        {"0019", "Sample-C", 80},
        {"0020", "Sample-D", 90}
    };
    rank_records(room, 4);
    for (int i = 0; i < 4; ++i) {
        printf("%s %s %d\n", room[i].code, room[i].name, room[i].score);
    }
    printf("code 0018 index=%d\n", find_code(room, 4, "0018"));
    return 0;
}
 
int comes_before(struct Student a, struct Student b)
{
    if (a.score != b.score) {
        return a.score > b.score;
    }
    return strcmp(a.code, b.code) < 0;
}
 
void rank_records(struct Student room[], int count)
{
    for (int i = 0; i < count - 1; ++i) {
        int best = i;
        for (int j = i + 1; j < count; ++j) {
            if (comes_before(room[j], room[best])) {
                best = j;
            }
        }
        struct Student temporary = room[i];
        room[i] = room[best];
        room[best] = temporary;
    }
}
 
int find_code(const struct Student room[], int count, const char code[])
{
    for (int i = 0; i < count; ++i) {
        if (strcmp(room[i].code, code) == 0) {
            return i;
        }
    }
    return -1;
}

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

ใบงานเลือกวิธี: รวมงานเตรียมข้อมูลด้วย

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

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

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

10.9 อ่านโค้ดที่ผิดและทำความเข้าใจข้อความวินิจฉัย

ตัวอย่างต่อไปนี้เป็นโค้ดฝึกแยกจากงานที่ต้องส่ง แสดงข้อผิดพลาดที่สัมพันธ์กับเนื้อหาบท พร้อมข้อความวินิจฉัยจริง วิธีอ่าน และฉบับแก้ คำว่า diagnostic ใช้รวมข้อความ error, warning และ note จึงไม่ควรเรียกทุกบรรทัดว่า error หรือถือว่าการไม่มี error แปลว่าโปรแกรมถูกตามโจทย์

ที่มาของ log: ผู้เขียนทดสอบด้วย GCC 11.4.0 บน Ubuntu ผ่าน Linux environment เมื่อ 24 ตุลาคม 2569 ใช้ C11 และตัวเลือกดังนี้ ชื่อไฟล์ เลขบรรทัด คอลัมน์ ถ้อยคำ และคำเตือนที่เปิดใช้อาจต่างจากแพลตฟอร์มการเรียน นักศึกษาไม่จำเป็นต้องเปลี่ยนเครื่องมือหรือการติดตั้งตามชุดทดสอบของผู้เขียน

-std=c11 -O0 -Wall -Wextra -Wpedantic -Wformat=2 -fdiagnostics-color=never -fmessage-length=0

ข้อความรูปแบบ bad.c:5:17 อ่านว่าไฟล์ bad.c บรรทัด 5 คอลัมน์ 17 ส่วน ^ และ ~ ช่วยชี้บริเวณที่ตรวจพบ จุดนี้อาจเป็นปลายเหตุจากบรรทัดก่อนหน้า error ทำให้การสร้างโปรแกรมล้มในกรณีนั้น warning เตือนความเสี่ยงแม้คำสั่งสร้างอาจจบสำเร็จ และ note ให้บริบท เช่น declaration เดิม ต้องอ่านคู่กัน (GCC: Diagnostics)

ตัวอย่างที่ผิด 1: ค้นหาแบบทวิภาคบนข้อมูลที่ยังไม่เรียง

ประเภท: ข้อผิดพลาดเชิงตรรกะที่ compiler อาจไม่เตือน

ข้อมูลยังไม่เรียงแต่ใช้เงื่อนไขตัดช่วงของ binary search ซึ่งต้องอาศัยลำดับที่สอดคล้องกัน ที่ middle พบ 5 น้อยกว่า 9 แล้วตัดช่วงซ้ายซึ่งมี 9 อยู่จริง จึงอาจรายงานไม่พบทั้งที่มีข้อมูล

โค้ดที่ผิด — ไม่ใช้แทนฉบับแก้

#include <stdio.h>
int binary_find(const int values[], int count, int target)
{
    int low = 0;
    int high = count - 1;
    while (low <= high) {
        int middle = low + (high - low) / 2;
        if (values[middle] == target) return middle;
        if (values[middle] < target) low = middle + 1;
        else high = middle - 1;
    }
    return -1;
}
int main(void)
{
    int values[] = {9, 1, 5, 3, 7};
    printf("index=%d\n", binary_find(values, 5, 9));
    return 0;
}

คำสั่งสร้างและข้อความที่ได้จริง

gcc -std=c11 -O0 -Wall -Wextra -Wpedantic -Wformat=2 -fdiagnostics-color=never -fmessage-length=0 bad.c -o bad

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

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

ผลจากการรันฉบับผิด

stdout:

index=-1

stderr ว่าง ไม่มี runtime diagnostic จากระบบในการทดลองนี้ ต้องใช้การเทียบผลกับข้อกำหนดเป็นหลักฐาน

สถานะจบที่ตัวเก็บผลอ่านได้: 0

ผลตามข้อกำหนดที่ใช้เทียบ:

index=0

อ่านข้อความว่าแจ้งอะไรและผิดอย่างไร

compiler ไม่ทราบสัญญาว่าข้อมูลต้องเรียง จึงไม่ต้องมี error หรือ warning ใช้ trace low, high, middle และค่าที่อ่านในแต่ละรอบเพื่อเห็นข้อมูลที่ถูกตัดทิ้ง ไม่สรุปว่า algorithm ถูกทุก input เพราะเคยค้นค่าบางตัวพบ

โค้ดที่แก้แล้ว

#include <stdio.h>
int linear_find(const int values[], int count, int target)
{
    for (int i = 0; i < count; ++i) {
        if (values[i] == target) return i;
    }
    return -1;
}
int main(void)
{
    int values[] = {9, 1, 5, 3, 7};
    printf("index=%d\n", linear_find(values, 5, 9));
    return 0;
}

เหตุผลของการแก้และสิ่งที่ต้องตรวจซ้ำ

สำหรับ input ที่ยังไม่เรียงและต้องคืนดัชนีเดิม เลือก linear search ดังฉบับแก้ ถ้าจะใช้ binary search ต้องเรียงข้อมูลก่อนและกำหนดความหมายของดัชนีหลังเรียงใหม่ การเพียงเปลี่ยนชื่อฟังก์ชันไม่แก้เงื่อนไขก่อนใช้งาน

ผลตรวจฉบับแก้จริง: คอมไพล์ด้วยตัวเลือกเดิมและเพิ่ม -Werror เพื่อให้ชุดทดสอบผู้เขียนไม่ยอมรับ warning ไม่มีข้อความวินิจฉัยและคำสั่งสร้างจบด้วยสถานะ 0 จากนั้นรันได้ stdout ดังนี้ และ stderr ว่าง

index=0

ตัวอย่างที่ผิด 2: เรียงไม่ครบเพราะข้ามสมาชิกสุดท้าย

ประเภท: ข้อผิดพลาดเชิงตรรกะที่ compiler อาจไม่เตือน

ลูปนอกของ selection sort ไม่ต้องเลือกตำแหน่งสุดท้ายซ้ำ แต่ลูปในต้องตรวจถึงสมาชิกสุดท้าย การใช้ count-1 กับลูปทั้งสองจึงข้ามค่า 1 ที่อยู่ปลายอาร์เรย์ ข้อมูลซึ่งเรียงอยู่แล้วอาจไม่เปิดเผยปัญหานี้

โค้ดที่ผิด — ไม่ใช้แทนฉบับแก้

#include <stdio.h>
int main(void)
{
    int values[] = {2, 3, 1};
    int count = 3;
    for (int i = 0; i < count - 1; ++i) {
        int smallest = i;
        for (int j = i + 1; j < count - 1; ++j) {
            if (values[j] < values[smallest]) smallest = j;
        }
        int temporary = values[i];
        values[i] = values[smallest];
        values[smallest] = temporary;
    }
    printf("%d %d %d\n", values[0], values[1], values[2]);
    return 0;
}

คำสั่งสร้างและข้อความที่ได้จริง

gcc -std=c11 -O0 -Wall -Wextra -Wpedantic -Wformat=2 -fdiagnostics-color=never -fmessage-length=0 bad.c -o bad

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

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

ผลจากการรันฉบับผิด

stdout:

2 3 1

stderr ว่าง ไม่มี runtime diagnostic จากระบบในการทดลองนี้ ต้องใช้การเทียบผลกับข้อกำหนดเป็นหลักฐาน

สถานะจบที่ตัวเก็บผลอ่านได้: 0

ผลตามข้อกำหนดที่ใช้เทียบ:

1 2 3

อ่านข้อความว่าแจ้งอะไรและผิดอย่างไร

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

โค้ดที่แก้แล้ว

#include <stdio.h>
int main(void)
{
    int values[] = {2, 3, 1};
    int count = 3;
    for (int i = 0; i < count - 1; ++i) {
        int smallest = i;
        for (int j = i + 1; j < count; ++j) {
            if (values[j] < values[smallest]) smallest = j;
        }
        int temporary = values[i];
        values[i] = values[smallest];
        values[smallest] = temporary;
    }
    printf("%d %d %d\n", values[0], values[1], values[2]);
    return 0;
}

เหตุผลของการแก้และสิ่งที่ต้องตรวจซ้ำ

คงลูปนอก i < count-1 แต่แก้ลูปในเป็น j < count ทดสอบค่าน้อยสุดที่ต้น กลาง และท้าย รวมทั้งค่าซ้ำ เพื่อไม่ให้ตัวอย่างเดียวที่เรียงแล้วสร้างความมั่นใจเกินหลักฐาน

ผลตรวจฉบับแก้จริง: คอมไพล์ด้วยตัวเลือกเดิมและเพิ่ม -Werror เพื่อให้ชุดทดสอบผู้เขียนไม่ยอมรับ warning ไม่มีข้อความวินิจฉัยและคำสั่งสร้างจบด้วยสถานะ 0 จากนั้นรันได้ stdout ดังนี้ และ stderr ว่าง

1 2 3

ลำดับการอ่าน log เมื่อลองโปรแกรมของบทนี้

1. ระบุว่าเกิดในขั้น compile, link, run หรือ test และแยกข้อความจากระบบออกจากข้อความที่โปรแกรมพิมพ์เอง
2. อ่าน diagnostic แรกกับบริบทบรรทัดก่อนหน้า แล้วใช้ note เพื่อเทียบ declaration หรือชนิดข้อมูล อย่าแก้ทุกข้อความตามลำดับโดยไม่หาสาเหตุร่วม
3. แก้ทีละสาเหตุ สร้างโปรแกรมใหม่ และตรวจว่ากำลังรันผล build ใหม่ การเติมวงเล็บ ปิด warning หรือลบ test อาจทำให้ log เงียบโดยยังผิดโจทย์
4. ใช้ข้อมูลเดิมที่ทำให้ผิดทดสอบซ้ำ แล้วเพิ่มกรณีขอบเขตที่สัมพันธ์กับบท การรันจบสถานะศูนย์เพียงครั้งเดียวไม่แทนการตรวจข้อกำหนดครบถ้วน

ความหมายตามภาษาอ้างจากร่างมาตรฐาน C11 โดยข้อความ diagnostic เฉพาะถ้อยคำเป็นของเครื่องมือที่ใช้ ไม่ได้กำหนดให้ compiler ทุกตัวพิมพ์เหมือนกัน (WG14 N1570, GCC: Warning Options)

ปฏิบัติการที่ 10 การเรียงลำดับและการค้นหา

ปฏิบัติการนี้แบ่งเป็นสองส่วนที่ต่อเนื่องกันในไฟล์เดียว ส่วนแรกฝึกการเรียงลำดับด้วย selection sort และการค้นหาเชิงเส้น ส่วนที่สองต่อยอดด้วยการค้นหาแบบทวิภาคบนอาร์เรย์ที่เรียงแล้วและการเทียบจำนวนรอบ ควรทำตามลำดับเพราะการค้นหาแบบทวิภาคในส่วนที่สองต้องใช้อาร์เรย์ที่เรียงแล้วจากส่วนแรก

Lab A: selection sort และการค้นหาเชิงเส้น

สถานการณ์ ต้องการเรียงคะแนนที่เก็บในอาร์เรย์จำนวนเต็มจากน้อยไปมากด้วย selection sort แล้วค้นหาค่าหนึ่งด้วยการค้นหาเชิงเส้น เพื่อฝึกการเขียนขั้นตอนวิธีการเรียงลำดับและการค้นหาด้วยฟังก์ชัน

เป้าหมาย ฝึก LLO10.1 และ LLO10.2 คือเขียน selection sort เรียงอาร์เรย์ และเขียนการค้นหาเชิงเส้นที่คืนดัชนีหรือ -1

ขั้นปฏิบัติ

1. สร้างไฟล์ชื่อ ch10_sortsearch.c ด้วยโปรแกรมแก้ไขข้อความหรือ IDE
2. พิมพ์ซอร์สโค้ดต่อไปนี้ โดยจัดย่อหน้า 4 ช่องว่างและใส่คอมเมนต์ส่วนหัว

/* ch10_sortsearch.c : การเรียงลำดับแบบ selection sort และการค้นหาเชิงเส้น */
#include <stdio.h>
 
void selection_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
}
 
int linear_search(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}
 
int main(void) {
    int data[6] = {29, 10, 14, 37, 13, 25};
    int n = 6;
 
    selection_sort(data, n);
    printf("หลังเรียง: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
 
    printf("linear_search 37 -> ดัชนี %d\n", linear_search(data, n, 37));
    return 0;
}

3. คอมไพล์และรันด้วยคำสั่ง

gcc -std=c11 -Wall ch10_sortsearch.c -o ch10_sortsearch
./ch10_sortsearch

ผลการรันจริง (ทดสอบแล้วด้วย gcc 13.3.0)

หลังเรียง: 10 13 14 25 29 37 
linear_search 37 -> ดัชนี 5

ฟังก์ชัน selection_sort วนตำแหน่งปัจจุบันด้วย i และหาตำแหน่งของค่าน้อยที่สุดในส่วนที่เหลือด้วยลูปในที่เริ่มจาก i + 1 เมื่อพบจึงสลับค่าด้วยตัวแปรชั่วคราว temp อาร์เรย์ {29, 10, 14, 37, 13, 25} จึงเรียงเป็น 10 13 14 25 29 37 ส่วน linear_search วนเทียบทีละสมาชิกจนพบค่า 37 ที่ดัชนี 5 แล้วคืนดัชนีนั้น หากไม่พบจะคืน -1

ตัดสินใจเอง A.1 ดัดแปลงฟังก์ชัน selection_sort ให้เรียงอาร์เรย์จากมากไปน้อยแทน โดยเปลี่ยนเงื่อนไขการเลือกให้หาสมาชิกที่มากที่สุดในส่วนที่เหลือมาไว้ตำแหน่งปัจจุบัน พร้อมตั้งชื่อตัวแปรให้สื่อความหมาย

ผลลัพธ์ที่คาดหวัง A.1 โปรแกรมคอมไพล์ผ่านไม่มีการแจ้งเตือน และเรียงอาร์เรย์จากมากไปน้อยได้ถูกต้อง เช่น จากอาร์เรย์ตัวอย่างควรได้ 37 29 25 14 13 10 (ผลที่คาดว่าจะเห็นสำหรับโปรแกรมที่ผู้เรียนออกแบบเอง ยังไม่ได้ทดสอบในเอกสารนี้ เพราะขึ้นกับการออกแบบของแต่ละคน)

จุดตรวจ A เรียงอาร์เรย์จากน้อยไปมากถูกต้อง สลับค่าด้วยตัวแปรชั่วคราวถูก การค้นหาเชิงเส้นคืนดัชนีที่พบและคืน -1 เมื่อไม่พบ ลูปวนอยู่ในช่วงดัชนีที่ถูกต้อง และโค้ดมีการจัดย่อหน้าและคอมเมนต์ส่วนหัว

ปัญหาที่พบบ่อย

เปิดหลังผู้เรียนออกแบบด้วยตนเองแล้ว

ใบงานตรวจ Lab A: เรียงถูกและข้อมูลไม่หาย

ฟังก์ชัน sort รับ count ที่ไม่ติดลบและไม่เกินพื้นที่ที่ตั้งค่าแล้ว การทดสอบชุดว่างใช้พื้นที่จริงที่มีอยู่แต่ส่ง count เป็น 0 ไม่จำเป็นต้องประกาศอาร์เรย์ขนาดศูนย์ซึ่งไม่ใช่รูปแบบมาตรฐานที่ใช้ในบทนี้

งาน A.1 เปลี่ยนการเลือกเป็นค่าสูงสุดเพื่อเรียงมากไปน้อย พร้อมเปลี่ยนชื่อให้ตรงหน้าที่ หากจะใช้ binary search ที่เปรียบเทียบแบบเรียงขึ้นต่อ ต้องไม่ส่งข้อมูลเรียงลงให้โดยไม่ปรับสัญญา

Lab B: การค้นหาแบบทวิภาคและการเทียบจำนวนรอบ

สถานการณ์ ต้องการค้นหาค่าบนอาร์เรย์ที่เรียงแล้วด้วยการค้นหาแบบทวิภาค แล้วเทียบกับการค้นหาเชิงเส้น เพื่อฝึกการเขียนการค้นหาแบบทวิภาคและเข้าใจประสิทธิภาพของแต่ละวิธี

เป้าหมาย ฝึก LLO10.2 และ LLO10.3 คือเขียนการค้นหาแบบทวิภาคและเลือกใช้ให้เหมาะกับสถานการณ์ และอธิบายประสิทธิภาพด้วยจำนวนรอบการเปรียบเทียบ

ขั้นปฏิบัติ

1. ต่อยอดไฟล์ ch10_sortsearch.c จาก Lab A โดยเพิ่มฟังก์ชัน binary_search และเรียกใช้ใน main ให้ซอร์สโค้ดเป็นดังนี้

/* ch10_sortsearch.c : การเรียงลำดับแบบ selection sort และการค้นหา */
#include <stdio.h>
 
void selection_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
}
 
int linear_search(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}
 
int binary_search(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}
 
int main(void) {
    int data[6] = {29, 10, 14, 37, 13, 25};
    int n = 6;
 
    selection_sort(data, n);
    printf("หลังเรียง: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
 
    printf("linear_search 37 -> ดัชนี %d\n", linear_search(data, n, 37));
    printf("binary_search 25 -> ดัชนี %d\n", binary_search(data, n, 25));
    printf("binary_search 99 -> ดัชนี %d\n", binary_search(data, n, 99));
    return 0;
}

2. คอมไพล์และรันด้วยคำสั่ง

gcc -std=c11 -Wall ch10_sortsearch.c -o ch10_sortsearch
./ch10_sortsearch

ผลการรันจริง (ทดสอบแล้วด้วย gcc 13.3.0)

หลังเรียง: 10 13 14 25 29 37 
linear_search 37 -> ดัชนี 5
binary_search 25 -> ดัชนี 3
binary_search 99 -> ดัชนี -1

ฟังก์ชัน binary_search ทำงานบนอาร์เรย์ที่ selection_sort เรียงแล้ว โดยเริ่ม low ที่ 0 และ high ที่ n - 1 แล้วตัดช่วงค้นหาเหลือครึ่งหนึ่งทุกรอบด้วยการเลื่อน low หรือ high เทียบกับ mid การค้นหา 25 พบที่ดัชนี 3 และการค้นหา 99 ที่ไม่มีในอาร์เรย์คืน -1 เงื่อนไขลูป low <= high ทำให้ตรวจสมาชิกตัวสุดท้ายที่ low เท่ากับ high ได้ครบ

ตัดสินใจเอง B.1 ต่อยอดโปรแกรมโดยเพิ่มตัวนับจำนวนรอบการเปรียบเทียบในการค้นหาเชิงเส้นและการค้นหาแบบทวิภาค แล้วแสดงจำนวนรอบของทั้งสองวิธีเมื่อค้นหาค่าเดียวกันบนอาร์เรย์ที่เรียงแล้ว เพื่อเทียบว่าวิธีใดใช้รอบน้อยกว่า พร้อมตั้งชื่อตัวแปรนับให้สื่อความหมาย

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

จุดตรวจ B การค้นหาแบบทวิภาคคืนดัชนีที่พบและคืน -1 เมื่อไม่พบ ทำงานบนอาร์เรย์ที่เรียงแล้ว เงื่อนไขลูป low <= high ถูกต้องและปรับ low/high พ้น mid ทุกรอบ อธิบายได้ว่าวิธีใดใช้รอบน้อยกว่าเมื่อข้อมูลมาก และโค้ดมีการจัดย่อหน้าและคอมเมนต์ส่วนหัว

ปัญหาที่พบบ่อย

เปิดหลังผู้เรียนส่งงานแล้ว

ใบงานตรวจ Lab B: ทดสอบขอบเขตและนิยามหน่วยนับ

งาน B.1 ให้ระบุว่าตัวนับนับ probe หรือจำนวนตัวดำเนินการเปรียบเทียบจริง หากเลือกแบบหลังต้องนับ == กับ < ตามเส้นทางจริงแยกกัน ไม่เอาสองนิยามมารวมในตารางเดียว

การเพิ่มลูปตรวจว่าเรียงแล้วทุกครั้งมีต้นทุนเพิ่มตามจำนวนข้อมูล สำหรับ search_probes จุดประสงค์คือป้องกันการทดลองผิดสัญญา ส่วนผล probes แสดงเฉพาะงานภายในฟังก์ชันค้นหา

เก็บกวาด

เมื่อจบปฏิบัติการ ให้ลบไฟล์ปฏิบัติการที่สร้างจากการคอมไพล์ (เช่น ch10_sortsearch) และเก็บเฉพาะไฟล์ซอร์สโค้ด .c ไว้ เพื่อให้โฟลเดอร์งานสะอาดและส่งไฟล์ซอร์สโค้ด .c พร้อมบันทึกผลการรันตามที่กำหนด

ตรวจความเข้าใจก่อนเริ่มบทที่ 11

ตอบโดยชี้ช่วงดัชนี กุญแจที่เรียง หรือสมบัติของผลลัพธ์ที่ตรวจได้

1. หลังจบลูปนอก selection sort หนึ่งรอบ ส่วนใดได้รับการยืนยันแล้ว
2. ทำไมจำนวนเปรียบเทียบกับจำนวนสลับจึงไม่จำเป็นต้องเท่ากัน
3. binary search ตามรหัสใช้กับรายการเรียงคะแนนได้หรือไม่
4. เมื่อพบค่าซ้ำตรงกลาง เหตุใดจึงยังไม่ยืนยันว่าเป็นตัวแรก
5. ทำไมการอัปเดตขอบเขตต้องพ้น mid ในรูปแบบที่ใช้
6. probe ที่น้อยกว่ารับรองเวลารันจริงที่เร็วกว่าเสมอหรือไม่
7. หลังเรียงต้องตรวจอะไรนอกจากค่าคู่ติดกันอยู่ในลำดับ

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

สรุป

บทนี้นำอาร์เรย์จากบทที่ 7 ฟังก์ชันจากบทที่ 6 และลูปกับเงื่อนไขจากบทที่ 4–5 มาประกอบเป็นเทคนิคการแก้ปัญหาด้วยการเรียงลำดับและการค้นหา เริ่มจากการเรียงลำดับแบบ selection sort ที่แต่ละรอบเลือกสมาชิกน้อยที่สุดในส่วนที่เหลือมาไว้ตำแหน่งปัจจุบันแล้วสลับค่าด้วยตัวแปรชั่วคราว temp ต่อด้วยการค้นหาเชิงเส้นที่ตรวจทีละสมาชิกด้วย linear_search คืนดัชนีที่พบหรือ -1 เมื่อไม่พบ จากนั้นเป็นการค้นหาแบบทวิภาคด้วย binary_search ที่ตัดช่วงค้นหาเหลือครึ่งหนึ่งทุกรอบด้วย low, mid, high โดยต้องเรียงข้อมูลก่อนเสมอ และปิดท้ายด้วยประสิทธิภาพเบื้องต้นที่นับจำนวนรอบการเปรียบเทียบ ได้แก่ selection sort ประมาณ n·n/2 การค้นหาเชิงเส้นประมาณ n และการค้นหาแบบทวิภาคประมาณ log2(n) การเลือกวิธีขึ้นกับขนาดข้อมูลและว่าข้อมูลเรียงแล้วหรือไม่ ทักษะเหล่านี้เป็นพื้นฐานของการวัดประสิทธิภาพและการจัดการข้อมูลในบทถัดไป

สิ่งที่ส่งต่อไปยังบทถัดไป

สรุปคำสั่ง

แบบฝึกหัดท้ายบท

ตอนที่ 1 ฝึกทบทวน (15 ข้อ ตรวจคำตอบให้ทันที)

ตอนที่ 2 แบบฝึกหัดเขียนตอบ (5 ข้อ)

กลุ่ม ก (เข้าใจ)

• ก1 (LLO10.1) จงอธิบายว่าในแต่ละรอบของ selection sort สมาชิกใดถูกเลือกมาไว้ที่ตำแหน่งปัจจุบัน และเหตุใดการสลับค่าสองตัวจึงต้องใช้ตัวแปรชั่วคราว
• ก2 (LLO10.2) จงอธิบายว่าการค้นหาแบบทวิภาคใช้กับอาร์เรย์ที่ยังไม่เรียงได้หรือไม่ เพราะเหตุใด

กลุ่ม ข (ประยุกต์)

• ข1 (LLO10.1) จงเขียนโปรแกรมภาษา C ที่ประกาศอาร์เรย์จำนวนเต็ม 6 ตัวพร้อมกำหนดค่าเริ่มต้น แล้วเขียนฟังก์ชัน selection sort เรียงจากน้อยไปมาก และแสดงสมาชิกหลังเรียง จากนั้นคอมไพล์และรันให้ได้ผลจริง
• ข2 (LLO10.2) จงเขียนฟังก์ชันการค้นหาเชิงเส้นและการค้นหาแบบทวิภาคที่คืนดัชนีที่พบหรือ -1 แล้วทดสอบค้นหาค่าที่มีอยู่และค่าที่ไม่มีในอาร์เรย์ที่เรียงแล้ว

กลุ่ม ค (วิเคราะห์)

• ค1 (LLO10.3) จากการค้นหาค่าหนึ่งบนอาร์เรย์ที่เรียงแล้วและมีจำนวนมาก จงวิเคราะห์ว่าการค้นหาเชิงเส้นและการค้นหาแบบทวิภาคใช้จำนวนรอบการเปรียบเทียบต่างกันอย่างไร และควรเลือกใช้วิธีใดเมื่อต้องค้นหาบ่อยครั้ง

การศึกษาค้นคว้าเพิ่มเติม

1. ศึกษาการเรียงลำดับและการค้นหาเพิ่มเติมจาก Kernighan และ Ritchie (1988) โดยเฉพาะการใช้ฟังก์ชันและอาร์เรย์ แล้วทดลองเขียนโปรแกรมที่เรียงอาร์เรย์แล้วค้นหาค่าด้วยการค้นหาแบบทวิภาค
2. ทบทวนข้อกำหนดเรื่องอาร์เรย์และการดำเนินการกับสมาชิกในมาตรฐานภาษา C ตาม ISO/IEC 9899 เพื่อเข้าใจพฤติกรรมของการเข้าถึงดัชนีขณะเขียนขั้นตอนวิธีการเรียงและการค้นหา
3. ทดลองออกแบบโปรแกรมที่นับจำนวนรอบการเปรียบเทียบของการค้นหาเชิงเส้นและการค้นหาแบบทวิภาค แล้วเปรียบเทียบจำนวนรอบเมื่อขนาดข้อมูลเพิ่มขึ้น เพื่อเตรียมต่อยอดสู่การวัดประสิทธิภาพในบทที่ 12

เอกสารอ้างอิง

International Organization for Standardization. (2011). ISO/IEC 9899:2011 — Information technology — Programming languages — C. ISO.

Kernighan, B. W., & Ritchie, D. M. (1988). The C programming language (2nd ed.). Prentice Hall.

ตำราหลักภาษาไทยของรายวิชา. (ผู้สอนเติมรายละเอียดบรรณานุกรม — เพิ่มตามมติผู้สอน 21 ต.ค. 2569).

แหล่งปฐมภูมิที่ตรวจประกอบการปรับปรุง 23 ตุลาคม 2569

• NIST — Selection Sort
• NIST — Binary Search

ใช้เอกสารข้างต้นตรวจหลักการก่อนเรียบเรียงส่วนขยายและสร้างข้อมูลสมมติ ตัวอย่างใหม่ที่เป็นโปรแกรม C ครบไฟล์ตรวจด้วย GCC 12.2.0 (Debian Linux) และ GCC 6.3.0 (MinGW-w64), C11 และคำเตือน -Wall -Wextra -Wpedantic เมื่อ 23 ตุลาคม 2569 แยกจากผลทดสอบ GCC 13.3.0 ของตัวอย่างเดิม ค่ารูปแบบและผลคำนวณตรวจจากการรัน ส่วนเวลา CPU ขึ้นกับสภาพแวดล้อม ไม่ใช่ผลตายตัว

แหล่งปฐมภูมิเพิ่มสำหรับชุดสอนพร้อมใช้บทที่ 10

• NIST DADS: Selection Sort — การเลือกจากส่วนที่เหลือ ต้นทุนกำลังสอง และข้อจำกัดการรักษาลำดับค่าที่เท่ากัน
• NIST DADS: Binary Search — เงื่อนไขอาร์เรย์เรียงและสูตรหาตำแหน่งกลาง
• NIST DADS: Linear Search — การตรวจสมาชิกทีละตัว

ตรวจเอกสารก่อนเขียนส่วนเพิ่มเมื่อ 23 ตุลาคม 2569 จำนวนงานและตาราง trace ในกิจกรรมเป็นผลวิเคราะห์ของโค้ดฉบับนี้ ต้องแยกจากเวลา CPU ที่ขึ้นกับสภาพแวดล้อม ตัวอย่างใช้ hosted C11 และข้อมูลสมมติ