Cholwich’s blog

ในไลบรารีมาตรฐานของภาษาซี มีฟังก์ชันสำหรับจัดการข้อมูลที่สำคัญอยู่ 2 ฟังก์ชัน คือ bsearch สำหรับการค้นหาข้อมูลแบบ binary search และ qsort สำหรับเรียงลำดับข้อมูลโดยใช้อัลกอริทึม quick sort โดยปกตินักศึกษาส่วนใหญ่มักจะไม่ใช้ เพราะมันดูเหมือนจะยุ่งยากซับซ้อน โดยเฉพาะเรื่องเกี่ยวกับ pointer วันนี้ต้องเขียนโปรแกรมเพื่อเรียงลำดับสายอักขระ เลยเอามาเขียนอธิบายวิธีการใช้ไว้หน่อย เผื่อจะเป็นประโยชน์ต่อตัวเอง และคนที่ผ่านมาเห็น

void qsort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *))

จาก function prototype จะเห็นว่าฟังก์ชันนี้ต้องการ argument 4 ตัว คือ

1. base เป็น pointer ที่ชี้ไปยังอะเรย์ที่ใช้เก็บข้อมูลทั้งหมด
2. nmemb ใช้ระบุจำนวนสมาชิกของอะเรย์ที่ต้องการเรียงลำดับ
3. size กำหนดขนาดของข้อมูลแต่ละชุด ซึ่งจำเป็นต้องใช้เวลาย้ายข้อมูลสลับตำแหน่งกัน
4. compar เป็น pointer ที่ชี้ไปยังฟังก์ชัน เพื่อเปรียบเทียบสมาชิกแต่ละตัวในอะเรย์ ฟังก์ชันนี้ควรจะให้ค่าน้อยกว่าศูนย์ เท่ากับศูนย์ และมากกว่าศูนย์ เช่นเดียวกับฟังก์ชัน strcmp

ตัวอย่าง ผมต้องการเรียงลำดับสตริง ซึ่งในภาษาซีจะใช้ char * ดังนั้นผมจึงสร้างตัวแปรแบบ char ** เพื่อเป็นอะเรย์สำหรับเก็บ pointer ที่ชี้ไปยังสตริงแต่ละตัว ส่วน nmemb ก็คือจำนวนสมาชิกของอะเรย์ กับ size ก็คือ sizeof(char) หาได้ไม่ยาก ปัญหาหลักอยู่ที่ฟังก์ชันสำหรับเปรียบเทียบข้อมูล ซึ่งจะเห็นว่าเรามีฟังก์ชัน strcmp สำหรับเปรียบเทียบสตริงอยู่แล้ว เพียงแต่ prototype อาจจะไม่เหมือนกัน เลยต้องทำฟังก์ชันขึ้นมาห่อไว้หน่อย

int compare(const void *a, const void *b) {
    const char **pa = (const char **)(a);
    const char **pb = (const char **)(b);
    return strcmp((*pa), (*pb));
}

อ้อ เวลาฟังก์ชัน qsort เรียก compar มาทำงาน จะเรียกโดยส่ง pointer ที่ชี้ไปยังสมาชิก 2 ตัวในอะเรย์ไปให้ ฉะนั้นจึงต้องมา cast ให้เป็น char ** ก่อน แล้วถึงจะไปเรียกใช้ strcmp ได้ ส่วนการเรียกฟังก์ชัน qsort ก็แค่

qsort(a, n, sizeof(char *), compare);

สุดท้ายที่อยากฝากไว้ก็คือ “don’t reinvent the wheel” เราควรจะใช้สิ่งที่มีอยู่แล้วให้เป็นประโยชน์ให้มากที่สุด โดยเฉพาะอย่างยิ่งฟังก์ชันมาตรฐานต่างๆ เพราะฟังก์ชันเหล่านี้ได้รับการพัฒนามายาวนาน ผ่านร้อนผ่านหนาวมาเยอะ น่าจะทำงานได้ดีกว่าการเขียนฟังก์ชันขึ้นมาใช้งานเอง แต่ทั้งนี้ไม่ได้บอกว่าไม่ควรทำเองนะ เพียงแต่พยายามปรับใช้สิ่งต่างๆ ที่มีอยู่ให้ดี เพื่อจะได้มีเวลาไปทำให้สิ่งใหม่ๆ

อ้างอิง: man qsort

programming C, programming, qsort