[0]zero-index clytie0x/zero-index

13.3 insertion sort และเวลาที่ใช้

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

insertion sort แทรกเข้าที่ทีละตัว

แบ่งอาเรย์เป็นสองส่วน ส่วนซ้ายคือไพ่ในมือซึ่งเรียงแล้ว ตอนเริ่มมีแค่ช่อง 0 ช่องเดียว ส่วนขวาคือไพ่ที่ยังไม่ได้หยิบ แต่ละรอบ

  1. หยิบ a[i] ตัวแรกของส่วนขวาออกมาเก็บไว้ในตัวแปร key
  2. ไล่จากท้ายส่วนซ้ายมาทางซ้าย ตัวไหนมากกว่า key ให้เลื่อนไปทางขวาหนึ่งช่อง
  3. เจอตัวที่ไม่มากกว่า key หรือเลยช่อง 0 ไปแล้ว ให้วาง key ลงในช่องว่างที่เหลือ

ขั้นที่ 2 กับ 3 คือการแทรกสมาชิกในหน้า 5.5 ที่ต้องเลื่อนจากทางขวาก่อนเพื่อไม่ให้ค่าถูกทับ รูปนี้ใช้ข้อมูล 6 3 8 2 5 ชุดเดิม ส่วนสีน้ำเงินคือส่วนซ้ายที่เรียงแล้ว ช่องสีส้มคือตำแหน่งที่ key ถูกวางลงในรอบนั้น

start 6 3 8 2 5 i = 1 3 6 8 2 5 key 3, shift 1 i = 2 3 6 8 2 5 key 8, shift 0 i = 3 2 3 6 8 5 key 2, shift 3 i = 4 2 3 5 6 8 key 5, shift 2

รอบ i = 2 หยิบ 8 มา ตัวสุดท้ายของส่วนซ้ายคือ 6 ไม่มากกว่า 8 จึงวางที่เดิมโดยไม่ต้องเลื่อนอะไร ส่วนรอบ i = 3 หยิบ 2 ซึ่งน้อยกว่าทุกตัวในมือ ต้องเลื่อนทั้งสามตัวแล้ววางที่ช่อง 0

#include <stdio.h>

void print_array(int a[], int n)
{
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", a[i]);
    }
    printf("\n");
}

int main()
{
    int a[5] = {6, 3, 8, 2, 5};
    int n = 5;
    for (int i = 1; i < n; i++) { // (1)!
        int key = a[i]; // (2)!
        int j = i - 1;
        while (j >= 0 && a[j] > key) { // (3)!
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key; // (4)!
        printf("i = %d, key = %d: ", i, key);
        print_array(a, n);
    }
    return 0;
}
  1. เริ่มที่ i = 1 เพราะช่อง 0 ตัวเดียวถือว่าเรียงแล้ว
  2. ต้องเก็บ a[i] ไว้ก่อน เพราะการเลื่อนครั้งแรกจะเขียนทับช่อง i ดูผลของการลืมเก็บในส่วนลองทำให้พัง
  3. ลำดับของสองเงื่อนไขสำคัญ ต้องเช็ก j >= 0 ก่อน && หยุดตรวจทันทีที่ข้างซ้ายเป็นเท็จ จึงไม่แตะ a[-1]
  4. ลูปจบตอนที่ a[j] ไม่มากกว่า key หรือ j เป็น -1 ช่องว่างจึงอยู่ที่ j + 1 ทั้งสองกรณี
i = 1, key = 3: 3 6 8 2 5
i = 2, key = 8: 3 6 8 2 5
i = 3, key = 2: 2 3 6 8 5
i = 4, key = 5: 2 3 5 6 8

เก็บเป็นฟังก์ชัน

void insertion_sort(int a[], int n)
{
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

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

เทียบสามวิธีกับข้อมูลสามแบบ

โปรแกรมนี้นับสองอย่างในทั้งสามวิธี คือจำนวนครั้งที่เทียบค่าในอาเรย์ และจำนวนครั้งที่ย้ายค่า (สลับของ bubble กับ selection หรือเลื่อนของ insertion) ข้อมูล n = 1000 ตัวมีสามแบบ

  • ascending เรียงจากน้อยไปมากอยู่แล้ว คือ 0 1 2 ... 999
  • descending เรียงกลับด้าน คือ 999 998 ... 0
  • mixed ปนกัน ใช้สูตร i * 7919 % n ซึ่งได้เลข 0 ถึง 999 ครบทุกตัวแต่สลับลำดับกัน ใช้สูตรแทนการสุ่มเพื่อให้ทุกเครื่องได้ข้อมูลชุดเดียวกัน

ตัวนับเป็นตัวแปรนอกฟังก์ชัน (global) ทุกฟังก์ชันจึงเพิ่มค่าได้ และใช้ long long เผื่อลองกับ n ที่ใหญ่ขึ้น ใน insertion sort แยกการเทียบออกมาเป็น if ข้างในลูปเพื่อให้นับได้ แต่ทำงานเหมือนเดิมทุกอย่าง

#include <stdio.h>

int original[100000], a[100000];
long long comparisons, moves;

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

void bubble_sort(int a[], int n)
{
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            comparisons++;
            if (a[j] > a[j + 1]) {
                swap(&a[j], &a[j + 1]);
                moves++;
            }
        }
    }
}

void selection_sort(int a[], int n)
{
    for (int i = 0; i < n - 1; i++) {
        int min_index = i;
        for (int j = i + 1; j < n; j++) {
            comparisons++;
            if (a[j] < a[min_index]) {
                min_index = j;
            }
        }
        if (min_index != i) {
            swap(&a[i], &a[min_index]);
            moves++;
        }
    }
}

void insertion_sort(int a[], int n)
{
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0) {
            comparisons++;
            if (a[j] <= key) {
                break;
            }
            a[j + 1] = a[j];
            moves++;
            j--;
        }
        a[j + 1] = key;
    }
}

void prepare(int n)
{
    for (int i = 0; i < n; i++) {
        a[i] = original[i];
    }
    comparisons = 0;
    moves = 0;
}

void report(const char *data, const char *method)
{
    printf("%-10s %-9s compare %6lld  move %6lld\n", data, method, comparisons, moves);
}

int main()
{
    int n;
    scanf("%d", &n);
    const char *names[3] = {"ascending", "descending", "mixed"};
    for (int kind = 0; kind < 3; kind++) {
        for (int i = 0; i < n; i++) {
            if (kind == 0) {
                original[i] = i;
            } else if (kind == 1) {
                original[i] = n - 1 - i;
            } else {
                original[i] = i * 7919 % n;
            }
        }
        prepare(n);
        bubble_sort(a, n);
        report(names[kind], "bubble");
        prepare(n);
        selection_sort(a, n);
        report(names[kind], "selection");
        prepare(n);
        insertion_sort(a, n);
        report(names[kind], "insertion");
    }
    return 0;
}

1000

ascending  bubble    compare 499500  move      0
ascending  selection compare 499500  move      0
ascending  insertion compare    999  move      0
descending bubble    compare 499500  move 499500
descending selection compare 499500  move    500
descending insertion compare 499500  move 499500
mixed      bubble    compare 499500  move 250101
mixed      selection compare 499500  move    947
mixed      insertion compare 251100  move 250101

const char *names[3] คืออาเรย์ของข้อความสามข้อความ แต่ละช่องเก็บที่อยู่ของข้อความหนึ่งข้อความ ส่วน %-10s คือพิมพ์ข้อความชิดซ้ายกว้าง 10 ช่อง แบบเดียวกับ %-5d ในหน้า 2.2 ตารางจึงตรงกัน อ่านผลได้ดังนี้

  • bubble กับ selection เทียบ 499500 ครั้งเสมอ ไม่ว่าข้อมูลจะเป็นแบบไหน ซึ่งคือ 1000 × 999 / 2 ข้อมูลที่เรียงอยู่แล้วก็ยังต้องเทียบครบ (bubble sort ในตัวอย่างนี้ไม่ได้ใส่การหยุดก่อนจากหน้า 13.2)
  • insertion sort ขึ้นกับข้อมูล ถ้าเรียงอยู่แล้ว แต่ละรอบเทียบครั้งเดียวก็เจอว่าไม่ต้องเลื่อน รวม 999 ครั้ง เร็วมาก แต่ถ้าเรียงกลับด้าน ทุกตัวต้องเลื่อนไปจนสุด เทียบเท่ากับอีกสองวิธี
  • จำนวนครั้งที่ย้ายของ bubble กับ insertion เท่ากันทุกแถว เพราะทั้งคู่เท่ากับจำนวนคู่ที่ผิดลำดับ ข้อมูลที่ปนกันมี 250101 คู่ ใกล้กับ n2 / 4 = 250000 ซึ่งเป็นค่าที่ได้โดยเฉลี่ยเมื่อข้อมูลสุ่ม ส่วน selection ย้ายไม่เกิน 999 ครั้ง

ในกรณีแย่ที่สุด ทั้งสามวิธีเทียบประมาณ n2 / 2 ครั้ง ต่อไปจะดูว่าตัวเลขนี้แปลเป็นเวลาเท่าไร

จับเวลาจริง

ใช้ clock() แบบหน้า 4.5 จับเฉพาะช่วงที่เรียง ข้อมูลสร้างด้วย rand() จาก stdlib.h ซึ่งคืนเลขสุ่มที่ไม่ติดลบ ส่วน srand(2569) กำหนดจุดเริ่มของการสุ่ม รันกี่ครั้งก็ได้ชุดเดิมบนเครื่องเดิม ตอนนี้ใช้ตามแบบไปก่อน อาเรย์ 100000 ช่องต้องอยู่นอก main ตามหน้า 5.5

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

int a[100000];

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

void bubble_sort(int a[], int n)
{
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                swap(&a[j], &a[j + 1]);
            }
        }
    }
}

void selection_sort(int a[], int n)
{
    for (int i = 0; i < n - 1; i++) {
        int min_index = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min_index]) {
                min_index = j;
            }
        }
        swap(&a[i], &a[min_index]);
    }
}

void insertion_sort(int a[], int n)
{
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    srand(2569);
    for (int i = 0; i < n; i++) {
        a[i] = rand();
    }
    clock_t start = clock();
    bubble_sort(a, n); // (1)!
    clock_t end = clock();
    printf("n = %d, time = %.3f seconds\n", n, (double)(end - start) / CLOCKS_PER_SEC);
    return 0;
}
  1. เปลี่ยนบรรทัดนี้เป็น selection_sort(a, n); หรือ insertion_sort(a, n); เพื่อวัดวิธีอื่น
10000

n = 10000, time = 0.074 seconds

วัดบนเครื่องเดียวกับหน้า 4.5 คือโน้ตบุ๊ก ASUS Vivobook S 14 ซีพียู AMD Ryzen AI 9 HX 370 Windows 11 เสียบสายชาร์จ โหมดพลังงาน Balanced คอมไพล์ด้วย GCC 14.2 ของ Code::Blocks ทั้งแบบ Code::Blocks (-Wall อย่างเดียว) และแบบ -O2 รันแต่ละช่อง 5 ครั้ง ตารางเป็นค่ากลางของ 5 ครั้งนั้น

วิธีnแบบ Code::Blocksแบบ -O2
bubble sort1,0000.000 วินาที0.001 วินาที
bubble sort10,0000.080 วินาที0.111 วินาที
bubble sort100,00018.589 วินาที19.515 วินาที
selection sort1,0000.000 วินาที0.000 วินาที
selection sort10,0000.031 วินาที0.012 วินาที
selection sort100,0003.584 วินาที1.314 วินาที
insertion sort1,0000.000 วินาที0.000 วินาที
insertion sort10,0000.022 วินาที0.006 วินาที
insertion sort100,0002.438 วินาที0.600 วินาที

0.000 ไม่ได้แปลว่าไม่ใช้เวลาเลย แต่น้อยกว่าที่ clock() วัดได้ อ่านตารางได้สามเรื่อง

  1. n เพิ่ม 10 เท่า เวลาเพิ่มราว 100 เท่า selection sort แบบ Code::Blocks จาก 0.031 เป็น 3.584 วินาที insertion sort จาก 0.022 เป็น 2.438 วินาที ตรงกับจำนวนครั้งที่เทียบ n2 / 2 ซึ่งเพิ่ม 10 × 10 = 100 เท่า การโตแบบนี้เรียกว่าโตตาม n กำลังสอง ส่วน bubble sort เพิ่มถึงราว 230 เท่า ส่วนที่เกิน 100 เท่ามาจากรายละเอียดของการทำงานในซีพียู ซึ่งไม่อยู่ในบทนี้ จำนวนครั้งที่เทียบเพิ่มแค่ 100 เท่าเท่ากับอีกสองวิธี
  2. วิธีที่เทียบเท่ากันไม่ได้ใช้เวลาเท่ากัน bubble sort ช้าที่สุดเพราะสลับบ่อยมาก ราวหนึ่งในสี่ของ n2 ครั้งกับข้อมูลสุ่ม insertion sort เร็วที่สุดเพราะเลื่อนถูกกว่าสลับ และหยุดเทียบทันทีที่เจอที่วาง
  3. -O2 ไม่ได้ช่วยทุกวิธี insertion sort เร็วขึ้นราว 4 เท่า แต่ bubble sort กลับช้าลงเล็กน้อย เวลาที่หายไปจากการเปลี่ยนวิธีมีมากกว่าการเปลี่ยนตัวเลือกของ compiler หลายเท่า

ถ้า n เป็นล้าน เวลาจะเพิ่มอีกราว 100 เท่า bubble sort จะใช้ราวครึ่งชั่วโมง ตัวเลขนี้ประมาณจากตาราง ไม่ได้วัดจริง

ใช้สามวิธีนี้ได้เมื่อไร

หลักจากหน้า 4.5 คือ 1 วินาทีทำงานง่ายๆ ได้ราว 108 รอบ เอาไปเทียบกับ n2 / 2

ขอบเขต n ในโจทย์n2 / 2ใช้สามวิธีนี้ได้ไหม
1,0005 × 105สบาย
10,0005 × 107ได้ ตามตารางช้าสุดคือ bubble sort แบบ -O2 ใช้ 0.111 วินาที
100,0005 × 109เสี่ยงมาก insertion sort แบบ -O2 ใช้ 0.600 วินาทีกับข้อมูลสุ่ม เฉียดขอบ 1 วินาที แบบ Code::Blocks ใช้ 2.438 วินาที ส่วนอีกสองวิธีไม่ทัน
1,000,0005 × 1011ไม่มีทาง

โจทย์ TOI Zero และโจทย์ค่าย 1 จำนวนมากให้ n ถึงแสน จึงต้องมีวิธีที่เร็วกว่านี้ หน้าถัดไปจะใช้ฟังก์ชัน qsort ที่มากับภาษา C ซึ่งเรียงแสนตัวได้ในเสี้ยววินาที ส่วนวิธีเรียงเร็วที่เขียนเองได้ คือ merge sort กับ quick sort จะเรียนในบทที่ 22 และการวิเคราะห์ว่าวิธีไหนโตเร็วแค่ไหนแบบเป็นระบบ ที่เรียกว่า Big O อยู่ในบทที่ 18

แล้วเรียนสามวิธีนี้ไปทำไม

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

ลองทำให้พัง

ลืมเก็บ key

ถ้าคิดว่าตัวแปร key ไม่จำเป็น เพราะค่าก็อยู่ใน a[i] อยู่แล้ว แล้วเขียนแบบนี้

#include <stdio.h>

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

6 6 8 8 8

เหลือแค่ 6 กับ 8 ตัวเลขอื่นหายหมด รอบ i = 1 การเลื่อนครั้งแรกคือ a[1] = a[0] ซึ่งเขียน 6 ทับ 3 ใน a[i] ไปแล้ว ตั้งแต่นั้นเงื่อนไขในลูปและบรรทัดที่วางค่ากลับก็ใช้ 6 แทน 3 ค่าที่จะถูกเขียนทับต้องเก็บไว้ก่อนเสมอ เหมือนแก้วเปล่าในการสลับ

สรุป

  • insertion sort หยิบ a[i] มาเก็บใน key เลื่อนตัวที่มากกว่าไปทางขวา แล้ววาง key ที่ a[j + 1] ต้องเช็ก j >= 0 ก่อน a[j] > key
  • insertion sort เร็วมากกับข้อมูลที่เกือบเรียง แต่กรณีแย่ที่สุดเทียบ n2 / 2 ครั้งเท่ากับอีกสองวิธี
  • จำนวนครั้งที่ bubble sort สลับ เท่ากับจำนวนครั้งที่ insertion sort เลื่อน เท่ากับจำนวนคู่ที่ผิดลำดับ
  • ทั้งสามวิธีโตตาม n กำลังสอง n เพิ่ม 10 เท่า เวลาเพิ่มราว 100 เท่า บนเครื่องที่เขียนเอกสารนี้ n = 100,000 ใช้ 0.6 ถึง 20 วินาที
  • n ไม่เกินหลักหมื่นเขียนเองได้ n ถึงแสนให้ใช้ qsort ในหน้าถัดไป วิธีเร็วที่เขียนเองอยู่ในบทที่ 22