13.1 ทำไมต้องเรียงข้อมูล

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

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

เรียงจากน้อยไปมาก (ascending) ทุกช่องมีค่าไม่มากกว่าช่องถัดไป a[0] ≤ a[1] ≤ ... ≤ a[n - 1] เช่น 2 3 3 5 8
เรียงจากมากไปน้อย (descending) กลับกัน เช่น 8 5 3 3 2

ใช้ ≤ ไม่ใช่ < เพราะค่าซ้ำกันได้ ถ้าโจทย์บอกแค่ว่า "เรียง" ไม่บอกทิศ ส่วนใหญ่หมายถึงจากน้อยไปมาก

ค่ากลาง

น้องจดเวลาเดินทางมาโรงเรียนเจ็ดวัน เป็นนาที วันหนึ่งฝนตกรถติดหนัก ใช้ไป 95 นาที ถ้าอยากรู้ว่าปกติใช้เวลาเท่าไร ค่าเฉลี่ยจะถูกวันนั้นดึงให้สูงเกินจริง ตัวเลขที่บอกว่า "ปกติ" ได้ดีกว่าคือ ค่ากลาง (median) คือค่าที่อยู่ตรงกลางเมื่อเรียงแล้ว มีครึ่งหนึ่งน้อยกว่าหรือเท่า อีกครึ่งมากกว่าหรือเท่า

ถ้าข้อมูลเรียงจากน้อยไปมากแล้ว และมี n ตัวเป็นเลขคี่ ค่ากลางอยู่ที่ช่อง n / 2 พอดี เช่น n = 7 ช่องกลางคือ a[3] มีสามช่องอยู่ทางซ้ายและสามช่องอยู่ทางขวา ตัวอย่างนี้สมมติว่าข้อมูลเข้าเรียงมาให้แล้ว

#include <stdio.h>

int minutes[1000];

int main()
{
    int n;
    scanf("%d", &n);
    int total = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &minutes[i]);
        total += minutes[i];
    }
    printf("average = %.2f\n", (double)total / n);
    printf("median = %d\n", minutes[n / 2]);
    return 0;
}

7
25 27 28 30 31 33 95

average = 38.43
median = 30

ค่าเฉลี่ยบอกว่าใช้ราว 38 นาที ทั้งที่หกวันจากเจ็ดวันใช้ไม่เกิน 33 นาที ส่วนค่ากลางได้ 30 ซึ่งใกล้ความจริงกว่า ต่อให้วันนั้นรถติดถึง 200 นาที ค่ากลางก็ยังเป็น 30 เท่าเดิม

ถ้า n เป็นเลขคู่ จะมีสองช่องตรงกลาง คือ a[n / 2 - 1] กับ a[n / 2] ค่ากลางนิยามเป็นค่าเฉลี่ยของสองช่องนั้น โจทย์จะบอกเองว่าต้องการแบบไหน อ่านให้ดีก่อนเขียน

คนที่ k

เมื่อเรียงจากน้อยไปมากแล้ว ตัวที่น้อยเป็นอันดับ k อยู่ที่ a[k - 1] ทันที ลบหนึ่งเพราะช่องแรกคือช่องที่ 0 ส่วนตัวที่มากเป็นอันดับ k นับจากท้ายมา อยู่ที่ a[n - k] ตัวอย่างนี้ใช้เวลาวิ่ง 100 เมตรของนักกีฬา 8 คน หน่วยเป็นร้อยละวินาที เช่น 1185 คือ 11.85 วินาที เก็บเป็นจำนวนเต็มจะไม่ต้องกังวลเรื่องการปัดทศนิยม

#include <stdio.h>

int times[1000];

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &times[i]);
    }
    printf("fastest #%d: %d\n", k, times[k - 1]);
    printf("slowest #%d: %d\n", k, times[n - k]);
    return 0;
}

8 3
1185 1192 1201 1201 1230 1244 1260 1302

fastest #3: 1201
slowest #3: 1244

ลองนับด้วยมือ คนที่เร็วเป็นอันดับ 3 ได้ 1201 และคนที่ช้าเป็นอันดับ 3 คือ 1244 ตรงกับที่โปรแกรมพิมพ์ ข้อมูลที่ยังไม่เรียงต้องหาค่าน้อยสุดแบบหน้า 5.2 แล้วตัดทิ้ง ทำซ้ำ k รอบ ซึ่งยุ่งกว่ามาก

ค่าซ้ำอยู่ติดกัน

ร้านขนมจดราคาของที่ขายได้วันนี้ อยากรู้ว่ามีราคาที่ต่างกันกี่แบบ และแต่ละราคาขายได้กี่ชิ้น ในหน้า 5.3 เราใช้อาเรย์นับ ซึ่งต้องมีช่องเท่ากับช่วงของค่า ถ้าราคาสูงได้ถึง 10⁹ บาท อาเรย์พันล้านช่องใหญ่เกินกว่าที่จะประกาศได้

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

#include <stdio.h>

int price[1000];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &price[i]);
    }
    int distinct = 0;
    int start = 0; // (1)!
    for (int i = 1; i <= n; i++) {
        if (i == n || price[i] != price[i - 1]) { // (2)!
            printf("%d x%d\n", price[start], i - start);
            distinct++;
            start = i;
        }
    }
    printf("distinct = %d\n", distinct);
    return 0;
}

start คือช่องแรกของกลุ่มที่กำลังนับ กลุ่มแรกเริ่มที่ช่อง 0 เสมอ
กลุ่มจบเมื่อเจอค่าที่ต่างจากช่องก่อนหน้า หรือเมื่อเลยช่องสุดท้ายไปแล้ว ต้องเช็ก i == n ก่อน เพราะ || หยุดตรวจทันทีที่ข้างซ้ายจริง จึงไม่แตะ price[n] ที่ไม่ใช่ข้อมูลของเรา ลูปนี้วนถึง i <= n ก็เพื่อปิดกลุ่มสุดท้ายนี่เอง

8
15 15 20 20 20 35 50 50

15 x2
20 x3
35 x1
50 x2
distinct = 4

ลูปเดียว ไม่ต้องใช้อาเรย์นับ ค่าจะใหญ่แค่ไหนก็ได้ เทียบกับข้อมูลที่ยังไม่เรียง ซึ่งต้องเทียบทุกคู่แบบลูปซ้อนในหน้า 4.4 ราว n² / 2 ครั้ง ถ้า n เป็นแสนก็ห้าพันล้านครั้ง ไม่ทันเวลา

ตรวจว่าเรียงแล้วหรือยัง

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

#include <stdio.h>

int a[1000];

int first_unsorted(int a[], int n)
{
    for (int i = 0; i + 1 < n; i++) {
        if (a[i] > a[i + 1]) {
            return i;
        }
    }
    return -1;
}

int main()
{
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        int position = first_unsorted(a, n);
        if (position == -1) {
            printf("sorted\n");
        } else {
            printf("not sorted: a[%d] = %d > a[%d] = %d\n", position, a[position], position + 1, a[position + 1]);
        }
    }
    return 0;
}

sorted
not sorted: a[2] = 5 > a[3] = 3
sorted

อาเรย์ที่มีตัวเดียวถือว่าเรียงแล้ว ลูปไม่ทำงานเลยเพราะ 0 + 1 < 1 เป็นเท็จ ตัวอย่างนี้อ่านหลายชุดจนหมดข้อมูลด้วย while (scanf(...) == 1) แบบหน้า 4.3 ข้อดีของการเขียน i + 1 < n แทน i < n - 1 คือดูออกทันทีว่า a[i + 1] ยังอยู่ในอาเรย์

สลับค่าสองช่อง

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

#include <stdio.h>

void swap(int *x, int *y) // (1)!
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

int main()
{
    int a[5] = {6, 3, 8, 2, 5};
    swap(&a[0], &a[3]); // (2)!
    for (int i = 0; i < 5; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", a[i]);
    }
    printf("\n");
    return 0;
}

รับที่อยู่ของสองช่อง เพราะฟังก์ชันต้องแก้ค่าของตัวแปรที่อยู่ข้างนอก ถ้ารับเป็น int x, int y จะได้แค่สำเนา สลับแล้วของจริงไม่เปลี่ยน เป็นเรื่องที่เรียนแล้วในบทที่ 10
&a[0] คือที่อยู่ของช่อง 0 สลับช่อง 0 กับช่อง 3

2 3 8 6 5

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

ลองทำให้พัง

แบบที่ 1 สลับโดยไม่มีแก้วเปล่า

หลายคนลองเขียนสลับให้สั้นลง แบบนี้

#include <stdio.h>

int main()
{
    int a[5] = {6, 3, 8, 2, 5};
    a[0] = a[3];
    a[3] = a[0];
    for (int i = 0; i < 5; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", a[i]);
    }
    printf("\n");
    return 0;
}

2 3 8 2 5

ได้ 2 สองตัว และ 6 หายไปเลย บรรทัดที่ 6 เทน้ำส้มทับนมไปแล้ว นมหายตั้งแต่ตรงนั้น บรรทัดที่ 7 จึงได้แค่ค่าที่เพิ่งใส่กลับไปที่เดิม ไม่มี error ไม่มี warning ถ้าอยู่ในวิธีเรียง จะเห็นแค่ว่าผลมีตัวเลขซ้ำแปลกๆ และบางตัวหายไป เจออาการนี้ให้ดูที่การสลับก่อน

แบบที่ 2 หาค่ากลางทั้งที่ยังไม่เรียง

ใช้โปรแกรม median ตัวเดิม แต่ป้อนเวลาเจ็ดวันตามลำดับวันจริง ซึ่งยังไม่เรียง

#include <stdio.h>

int minutes[1000];

int main()
{
    int n;
    scanf("%d", &n);
    int total = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &minutes[i]);
        total += minutes[i];
    }
    printf("average = %.2f\n", (double)total / n);
    printf("median = %d\n", minutes[n / 2]);
    return 0;
}

7
30 28 95 33 25 31 27

average = 38.43
median = 33

ค่าเฉลี่ยยังถูก เพราะผลรวมไม่ขึ้นกับลำดับ แต่ค่ากลางกลายเป็น 33 ซึ่งแค่บังเอิญอยู่ช่องที่ 3 ของวันที่ป้อน คำตอบผิดแบบนี้ไม่มีอะไรเตือน ผ่านตัวอย่างในโจทย์ได้ด้วยถ้าตัวอย่างบังเอิญเรียงมา สูตร a[n / 2] a[k - 1] และการเทียบกับช่องก่อนหน้า ใช้ได้กับข้อมูลที่เรียงแล้วเท่านั้น

สรุป

เรียงจากน้อยไปมาก (ascending) คือ a[i] ≤ a[i + 1] ทุกช่อง มากไปน้อย (descending) คือกลับกัน
ข้อมูลที่เรียงแล้ว ค่ากลางอยู่ที่ a[n / 2] ตัวที่น้อยอันดับ k อยู่ที่ a[k - 1] ตัวที่มากอันดับ k อยู่ที่ a[n - k]
ค่าที่เท่ากันอยู่ติดกัน นับจำนวนค่าที่ต่างกันได้ด้วยการเทียบกับช่องก่อนหน้า ไม่ต้องใช้อาเรย์นับ
สลับค่าต้องมีตัวแปรพัก temp และฟังก์ชัน swap ต้องรับที่อยู่ int *
สูตรเหล่านี้ใช้กับข้อมูลที่ยังไม่เรียงไม่ได้ และจะได้คำตอบผิดเงียบๆ