13.4 เรียงด้วย qsort

ภาษา C มีฟังก์ชันเรียงข้อมูลมาให้ใน stdlib.h ชื่อ qsort เรียงแสนตัวได้ในเวลาไม่ถึงหนึ่งในร้อยวินาที และเรียงอะไรก็ได้ ทั้งตัวเลข ข้อความ และอาเรย์ของ struct ตามเงื่อนไขที่เรากำหนดเอง เช่น คะแนนมากก่อน ถ้าคะแนนเท่ากันใครใช้เวลาน้อยกว่าก่อน หน้านี้คือวิธีใช้ และกับดักหนึ่งข้อที่ทำให้คนเสียคะแนนกันมาก คือการลบกันในฟังก์ชันเปรียบเทียบ

qsort ต้องรู้อะไรบ้าง

qsort ไม่รู้ว่าอาเรย์ของเราเก็บอะไร มันจึงต้องการข้อมูลสี่อย่าง

qsort(score, n, sizeof(int), compare_int);

ช่องที่ 3 จำเป็นเพราะ qsort เห็นอาเรย์เป็นแค่ byte เรียงกันยาวๆ ต้องบอกว่าทุกกี่ byte คือหนึ่งช่อง sizeof บอกขนาดของชนิดหรือตัวแปรเป็น byte ส่วนช่องที่ 4 ใส่ชื่อฟังก์ชันโดยไม่มีวงเล็บ เพราะเราไม่ได้เรียกฟังก์ชันนั้นเอง แต่ส่งตัวฟังก์ชันไปให้ qsort เรียกเมื่อต้องการเทียบสองช่อง

ฟังก์ชันเปรียบเทียบ

ฟังก์ชันเปรียบเทียบ (comparison function) รับที่อยู่ของสองช่อง แล้วตอบเป็นตัวเลขแบบเดียวกับ strcmp ในหน้า 6.4

#include <stdio.h>
#include <stdlib.h> // (1)!

int score[100000];

int compare_int(const void *p, const void *q) // (2)!
{
    int x = *(const int *)p; // (3)!
    int y = *(const int *)q;
    if (x < y) {
        return -1;
    }
    if (x > y) {
        return 1;
    }
    return 0;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &score[i]);
    }
    qsort(score, n, sizeof(int), compare_int);
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", score[i]);
    }
    printf("\n");
    return 0;
}

1. qsort อยู่ใน stdlib.h ลืมบรรทัดนี้แล้วจะคอมไพล์ไม่ผ่าน ดูในส่วนลองทำให้พัง
2. หัวฟังก์ชันต้องเป็นแบบนี้ทุกตัวอักษร คืน int รับ const void * สองตัว ตั้งชื่อฟังก์ชันกับชื่อพารามิเตอร์เองได้
3. แปลง p เป็น pointer ไปยัง int ก่อน แล้วใช้ * หยิบค่าที่ชี้อยู่ออกมา

8
72 85 64 85 90 58 100 64

58 64 64 72 85 85 90 100

หัวฟังก์ชันมีสองคำที่เคยเจอแล้วในบทที่ 10 คราวนี้ใช้คู่กัน

• void * ชนิดเดียวกับที่ malloc คืนในหน้า 10.5 คือ pointer ที่ไม่บอกว่าชี้ไปยังข้อมูลชนิดไหน qsort ต้องใช้ชนิดนี้เพราะมันเรียงได้ทุกชนิด จึงบอกเราไม่ได้ว่าเป็น int หน้าที่ของเราคือแปลงกลับเป็นชนิดที่ถูกด้วย (const int *) แบบเดียวกับการแปลงชนิดด้วย (double) ในหน้า 1.4 แล้วค่อยใช้ * หยิบค่า ใช้ *p ตรงๆ ไม่ได้ เพราะ compiler ไม่รู้ว่าต้องหยิบกี่ byte
• const แบบเดียวกับ const char * ในหน้า 10.4 คือสัญญาว่าจะไม่แก้ค่าที่ชี้อยู่ ฟังก์ชันเปรียบเทียบมีหน้าที่ดูอย่างเดียว ถ้าเผลอเขียนค่าใส่ compiler จะฟ้อง

ฟังก์ชันเปรียบเทียบต้องตอบตรงกันทุกครั้ง ถ้าบอกว่า a มาก่อน b ก็ต้องบอกว่า b มาทีหลัง a และถ้า a มาก่อน b และ b มาก่อน c ก็ต้องบอกว่า a มาก่อน c ฟังก์ชันที่ตอบขัดกันเองจะทำให้ qsort ให้ผลที่ไม่เรียง

เร็วแค่ไหน

ใช้โปรแกรมจับเวลาแบบหน้า 13.3 แต่เปลี่ยนการเรียงเป็น qsort ข้อมูลชุดเดิมที่สร้างจาก srand(2569)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int a[100000];

int compare_int(const void *p, const void *q)
{
    int x = *(const int *)p;
    int y = *(const int *)q;
    if (x < y) {
        return -1;
    }
    if (x > y) {
        return 1;
    }
    return 0;
}

int main()
{
    int n;
    scanf("%d", &n);
    srand(2569);
    for (int i = 0; i < n; i++) {
        a[i] = rand();
    }
    clock_t start = clock();
    qsort(a, n, sizeof(int), compare_int);
    clock_t end = clock();
    printf("n = %d, time = %.3f seconds\n", n, (double)(end - start) / CLOCKS_PER_SEC);
    return 0;
}

100000

n = 100000, time = 0.009 seconds

วัดบนเครื่องและวิธีเดียวกับหน้า 13.3 ค่ากลางของ 5 ครั้ง

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

เรียงจากมากไปน้อย

ไม่ต้องแก้ qsort แค่กลับคำตอบของฟังก์ชันเปรียบเทียบ ตัวที่มากกว่าให้มาก่อน

#include <stdio.h>
#include <stdlib.h>

int score[100000];

int compare_desc(const void *p, const void *q)
{
    int x = *(const int *)p;
    int y = *(const int *)q;
    if (x > y) {
        return -1;
    }
    if (x < y) {
        return 1;
    }
    return 0;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &score[i]);
    }
    qsort(score, n, sizeof(int), compare_desc);
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", score[i]);
    }
    printf("\n");
    return 0;
}

8
72 85 64 85 90 58 100 64

100 90 85 85 72 64 64 58

อาเรย์ของ long long ก็ใช้แบบเดียวกัน แต่ต้องเปลี่ยนสามจุดให้ตรงกัน คือ sizeof(long long) ในการเรียก qsort การแปลงเป็น (const long long *) และตัวแปร x y ในฟังก์ชันเปรียบเทียบ ถ้าลืมจุดใดจุดหนึ่ง qsort จะหั่นข้อมูลผิดขนาดและได้ผลมั่ว

กับดัก return x - y

ในเว็บและหนังสือหลายเล่ม จะเห็นฟังก์ชันเปรียบเทียบที่สั้นกว่าของเราแบบนี้

int compare_int(const void *p, const void *q)
{
    return *(const int *)p - *(const int *)q;
}

ดูถูกต้อง ถ้าตัวแรกน้อยกว่า ผลลบก็ติดลบ ถ้ามากกว่าก็เป็นบวก และกับตัวเลขเล็กๆ ก็ทำงานได้จริง แต่ลองใช้ฟังก์ชันนี้แทนของเดิมในโปรแกรม scores แล้วป้อนเลขที่ใหญ่ใกล้ขอบของ int ซึ่งโจทย์ที่ให้ค่าถึง ±2 × 10⁹ ก็มีบ่อย

5
2000000000 -2000000000 7 -7 1500000000

2000000000 -2000000000 -7 7 1500000000

นี่คือผลบนเครื่องที่เขียนเอกสารนี้ ไม่เรียงเลย 2000000000 มาอยู่หน้า -2000000000 เพราะเมื่อ qsort ถามว่า 2000000000 กับ -2000000000 ตัวไหนมาก่อน ฟังก์ชันคำนวณ 2000000000 - (-2000000000) = 4000000000 ซึ่งเกิน int แล้วล้นวนไปเป็น -294967296 แบบที่เห็นในหน้า 1.3 ผลติดลบจึงบอกว่า 2000000000 ต้องมาก่อน ฟังก์ชันตอบขัดกับความจริง และขัดกับคำตอบของคู่อื่น qsort จึงเรียงผิด

ลองโปรแกรมเดียวกันบน Linux ได้ -7 7 1500000000 2000000000 -2000000000 ซึ่งก็ผิด แต่ผิดคนละแบบ เพราะ qsort ของแต่ละระบบเทียบคู่ในลำดับต่างกัน แปลว่าโปรแกรมอาจผ่านในเครื่องเรา แต่ตกบน grader และการล้นของ int เป็น undefined behavior ตามหน้า 1.3 อยู่แล้ว ไม่มีอะไรรับประกันผลเลย

เรียงข้อความ

รายชื่อหลายชื่อเก็บในอาเรย์สองมิติของ char แบบในบทที่ 7 แถวละหนึ่งชื่อ แต่ละแถวคือหนึ่งช่องที่ qsort จะสลับไปมา ขนาดหนึ่งช่องจึงเป็นขนาดของทั้งแถว คือ sizeof(name[0]) ซึ่งเท่ากับ 21 byte ไม่ใช่ sizeof(char)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char name[1000][21];

int compare_name(const void *p, const void *q)
{
    return strcmp((const char *)p, (const char *)q); // (1)!
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", name[i]);
    }
    qsort(name, n, sizeof(name[0]), compare_name); // (2)!
    for (int i = 0; i < n; i++) {
        printf("%s\n", name[i]);
    }
    return 0;
}

1. p ชี้ไปที่ตัวอักษรตัวแรกของแถว ซึ่งก็คือสตริงหนึ่งสตริง ส่งให้ strcmp ได้เลย strcmp ไม่ได้ลบตัวเลขใหญ่ จึงไม่มีปัญหาล้น
2. หนึ่งช่องคือหนึ่งแถว 21 byte ถ้าใส่ sizeof(char) qsort จะสลับตัวอักษรทีละตัวปนกันทุกชื่อ

6
songkhla
nan
phuket
chiangmai
nakhonpathom
nakhonnayok

chiangmai
nakhonnayok
nakhonpathom
nan
phuket
songkhla

เรียงแบบพจนานุกรม nakhonnayok มาก่อน nakhonpathom เพราะหกตัวแรกเหมือนกัน ตัวที่เจ็ด n มาก่อน p และทั้งสองมาก่อน nan เพราะตัวที่สาม k มาก่อน n อย่าลืมว่า strcmp เทียบรหัส ASCII ตัวพิมพ์ใหญ่ทุกตัวจึงมาก่อนตัวพิมพ์เล็กทุกตัว ตามที่เห็นในหน้า 6.4

เรียงอาเรย์ของ struct หลายเงื่อนไข

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct contestant {
    char name[21];
    int score;
    int minutes;
};

struct contestant list[1000];

int compare_rank(const void *p, const void *q)
{
    const struct contestant *a = p; // (1)!
    const struct contestant *b = q;
    if (a->score != b->score) { // (2)!
        return a->score > b->score ? -1 : 1;
    }
    if (a->minutes != b->minutes) { // (3)!
        return a->minutes < b->minutes ? -1 : 1;
    }
    return strcmp(a->name, b->name); // (4)!
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s %d %d", list[i].name, &list[i].score, &list[i].minutes);
    }
    qsort(list, n, sizeof(list[0]), compare_rank);
    for (int i = 0; i < n; i++) {
        printf("%d. %s %d %d\n", i + 1, list[i].name, list[i].score, list[i].minutes);
    }
    return 0;
}

1. ภาษา C แปลง const void * เป็น pointer ชนิดอื่นให้เองเมื่อกำหนดค่า จึงไม่ต้องเขียน (const struct contestant *) แต่จะเขียนก็ได้ a->score คือ (*a).score ค่า score ของ struct ที่ a ชี้อยู่
2. เงื่อนไขแรก คะแนนมากมาก่อน ใช้ ? : จากหน้า 3.4 ตอบ -1 ถ้า a คะแนนมากกว่า ไม่อย่างนั้นตอบ 1 บรรทัดนี้ทำงานเฉพาะเมื่อคะแนนไม่เท่ากัน จึงไม่ต้องตอบ 0
3. คะแนนเท่ากัน ดูเวลา เวลาน้อยมาก่อน
4. เท่ากันทั้งสองอย่าง เรียงตามชื่อ ชื่อไม่ซ้ำกัน ลำดับจึงตายตัวเสมอ

6
somchai 85 40
malee 92 55
anan 85 35
kanya 92 55
preeda 70 20
boonmee 85 40

1. kanya 92 55
2. malee 92 55
3. anan 85 35
4. boonmee 85 40
5. somchai 85 40
6. preeda 70 20

sizeof(list[0]) คือขนาดของ struct หนึ่งตัว ซึ่งรวมชื่อ 21 byte กับ int อีกสองตัว ใช้ sizeof(list[0]) ดีกว่าเขียนขนาดเอง เพราะถ้าเพิ่มช่องใน struct ทีหลัง ขนาดจะถูกเสมอ

ค่าที่เท่ากันอาจสลับที่

ถ้าฟังก์ชันเปรียบเทียบตอบ 0 แปลว่าเราบอก qsort ว่าอันไหนมาก่อนก็ได้ และมันก็จะเลือกเองจริงๆ ตัวอย่างนี้เรียงนักเรียนเลขที่ 1 ถึง 8 ตามคะแนนจากมากไปน้อยอย่างเดียว แล้วพิมพ์เป็น เลขที่:คะแนน

#include <stdio.h>
#include <stdlib.h>

struct student {
    int id;
    int score;
};

struct student list[1000];

int compare_score(const void *p, const void *q)
{
    const struct student *a = p;
    const struct student *b = q;
    if (a->score != b->score) {
        return a->score > b->score ? -1 : 1;
    }
    return 0;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        list[i].id = i + 1;
        scanf("%d", &list[i].score);
    }
    qsort(list, n, sizeof(list[0]), compare_score);
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d:%d", list[i].id, list[i].score);
    }
    printf("\n");
    return 0;
}

8
5 7 5 7 5 7 5 7

2:7 6:7 4:7 8:7 5:5 7:5 3:5 1:5

นี่คือผลบนเครื่องที่เขียนเอกสารนี้ ตัวอย่างนี้จึงไม่มีการตรวจผลอัตโนมัติเหมือนตัวอย่างอื่น

คะแนนเรียงถูก แต่คนที่ได้ 7 ไม่ได้อยู่ตามลำดับเลขที่ ส่วนโปรแกรมเดียวกันบน Linux ได้ 2:7 4:7 6:7 8:7 1:5 3:5 5:5 7:5 วิธีเรียงที่รักษาลำดับเดิมของค่าที่เท่ากันเรียกว่า stable มาตรฐานภาษา C ไม่ได้สัญญาว่า qsort เป็น stable ถ้าโจทย์บอกว่า "ถ้าคะแนนเท่ากัน ให้เรียงตามลำดับที่รับเข้ามา" ให้เก็บลำดับที่รับเข้ามาไว้ใน struct ด้วย แล้วใช้เป็นเงื่อนไขสุดท้าย

if (a->score != b->score) {
    return a->score > b->score ? -1 : 1;
}
return a->id < b->id ? -1 : 1;

ส่วน bubble sort และ insertion sort ที่เราเขียนเองเป็น stable เพราะสลับหรือเลื่อนเฉพาะเมื่อมากกว่ากันจริงๆ ค่าที่เท่ากันจึงไม่เคยข้ามกัน selection sort ไม่ใช่ เพราะการสลับระยะไกลพาค่าข้ามตัวที่เท่ากันได้

ลองทำให้พัง

แบบที่ 1 หัวฟังก์ชันเปรียบเทียบไม่ตรงแบบ

ในโปรแกรม scores ถ้าคิดว่ารับเป็น int * ไปเลยจะได้ไม่ต้องแปลงชนิด แล้วเขียนหัวฟังก์ชันเป็น int compare_int(int *p, int *q)

scores.c:26:34: error: passing argument 4 of 'qsort' from incompatible pointer type [-Wincompatible-pointer-types]
   26 |     qsort(score, n, sizeof(int), compare_int);
      |                                  ^~~~~~~~~~~
      |                                  |
      |                                  int (*)(int *, int *)
In file included from scores.c:2:
C:/Program Files/CodeBlocks/MinGW/x86_64-w64-mingw32/include/stdlib.h:441:93: note: expected 'int (*)(const void *, const void *)' but argument is of type 'int (*)(int *, int *)'
  441 |   void __cdecl qsort(void *_Base,size_t _NumOfElements,size_t _SizeOfElements,int (__cdecl *_PtFuncCompare)(const void *,const void *));
      |                                                                               ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

GCC 14 ถือว่าเป็น error ข้อความบอกว่าช่องที่ 4 ของ qsort ได้ฟังก์ชันชนิด int (*)(int *, int *) แต่ qsort ต้องการ int (*)(const void *, const void *) ส่วน note ชี้ไปที่บรรทัดใน stdlib.h ที่ประกาศ qsort ไว้ ให้แก้หัวฟังก์ชันกลับเป็น const void * แล้วแปลงชนิดข้างใน

แบบที่ 2 ลืม include stdlib.h

scores.c:25:5: error: implicit declaration of function 'qsort' [-Wimplicit-function-declaration]
   25 |     qsort(score, n, sizeof(int), compare_int);
      |     ^~~~~

implicit declaration แปลว่าเรียกฟังก์ชันที่ compiler ยังไม่รู้จัก printf กับ scanf อยู่ใน stdio.h แต่ qsort อยู่ใน stdlib.h เจอข้อความนี้กับฟังก์ชันของไลบรารีเมื่อไร ให้หาว่ามันอยู่ในไฟล์ไหนแล้ว include ให้ครบ

สรุป

• qsort(อาเรย์, จำนวน, ขนาดหนึ่งช่อง, ฟังก์ชันเปรียบเทียบ) อยู่ใน stdlib.h เรียงแสนตัวในเวลาราวหนึ่งในร้อยวินาที
• ฟังก์ชันเปรียบเทียบมีหัวเป็น int f(const void *p, const void *q) แปลงชนิดก่อนใช้ คืนค่าลบถ้าตัวแรกมาก่อน บวกถ้ามาทีหลัง 0 ถ้าเท่ากัน
• เปรียบเทียบด้วย if อย่าใช้ return x - y เพราะล้นเมื่อค่าใหญ่ และผลผิดต่างกันไปในแต่ละเครื่อง
• เรียงข้อความใช้ strcmp ขนาดหนึ่งช่องคือ sizeof(name[0]) เรียง struct ใช้ sizeof(list[0])
• หลายเงื่อนไข ไล่ดูทีละเงื่อนไข เงื่อนไขแรกที่ต่างกันเป็นตัวตัดสิน
• qsort ไม่รับประกันลำดับของค่าที่เท่ากัน ถ้าโจทย์สนใจ ให้เพิ่มลำดับที่รับเข้ามาเป็นเงื่อนไขสุดท้าย