13.2 bubble sort และ selection sort

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

bubble sort เทียบคู่ที่ติดกัน

ไล่จากซ้ายไปขวา เทียบช่อง j กับช่อง j + 1 ทีละคู่ ถ้าตัวซ้ายมากกว่าตัวขวา แปลว่าผิดลำดับ ก็สลับ ไล่จนสุดแถวนับเป็นหนึ่งรอบ (pass) รูปนี้คือรอบที่ 1 ช่องที่มีขอบสีส้มคือคู่ที่กำลังเทียบ ถ้าระบายสีส้มด้วยคือคู่ที่เพิ่งสลับ

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

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

ข้อมูล 5 ตัว ใช้ 4 รอบ หลังรอบที่ 4 สี่ช่องทางขวาเข้าที่หมด ช่องที่เหลือทางซ้ายสุดจึงต้องเป็นค่าน้อยสุดโดยอัตโนมัติ ข้อมูล n ตัวจึงใช้ n - 1 รอบ

เขียน bubble sort แล้วพิมพ์ทุกรอบ

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

#include <stdio.h>

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

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 = 0; i < n - 1; i++) { // (1)!
        for (int j = 0; j < n - 1 - i; j++) { // (2)!
            if (a[j] > a[j + 1]) {
                swap(&a[j], &a[j + 1]);
            }
        }
        printf("pass %d: ", i + 1);
        print_array(a, n);
    }
    return 0;
}

วน n - 1 รอบ i นับว่าจบไปแล้วกี่รอบ ซึ่งเท่ากับจำนวนช่องท้ายแถวที่เข้าที่แล้ว
เทียบ a[j] กับ a[j + 1] ช่องขวาสุดที่ยังต้องดูคือ n - 1 - i จึงให้ j ไปถึงแค่ n - 2 - i ถ้าให้ j ไปถึง n - 1 จะแตะ a[n] ซึ่งไม่ใช่ข้อมูล ดูผลของมันในส่วนลองทำให้พัง

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

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

เมื่อแน่ใจแล้วว่าถูก ก็เก็บเป็นฟังก์ชันเพื่อใช้ซ้ำ ตัวอย่างนี้เรียงส่วนสูงของนักเรียน 8 คนเป็นเซนติเมตร

#include <stdio.h>

int height[1000];

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]);
            }
        }
    }
}

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

8
152 148 160 155 149 171 158 163

148 149 152 155 158 160 163 171

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

หยุดเมื่อไม่มีการสลับ

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

#include <stdio.h>

int a[1000];

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

int bubble_sort(int a[], int n)
{
    int passes = 0;
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0; // (1)!
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                swap(&a[j], &a[j + 1]);
                swapped = 1;
            }
        }
        passes++;
        if (swapped == 0) { // (2)!
            break;
        }
    }
    return passes;
}

int main()
{
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        printf("passes = %d\n", bubble_sort(a, n));
    }
    return 0;
}

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

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

passes = 4
passes = 2
passes = 1
passes = 7

ชุดแรกหยุดที่รอบที่ 4 เพราะต้องมีหนึ่งรอบที่ไม่สลับเพื่อยืนยันว่าเรียงแล้ว ชุดที่เกือบเรียงใช้ 2 รอบ ชุดที่เรียงอยู่แล้วใช้รอบเดียว แต่ชุดที่เรียงกลับด้านยังต้องใช้ครบ 7 รอบ การหยุดก่อนจึงช่วยเฉพาะข้อมูลที่เกือบเรียงอยู่แล้ว กรณีแย่ที่สุดยังช้าเท่าเดิม

selection sort เลือกตัวน้อยสุดมาวาง

อีกวิธีที่คนใช้จริงตอนจัดของ คือหาตัวที่น้อยที่สุดในกองแล้ววางไว้ที่ 1 หาตัวน้อยสุดในที่เหลือวางไว้ที่ 2 ไปเรื่อยๆ ในอาเรย์ทำแบบนี้

รอบ i = 0 หาค่าน้อยสุดในช่อง 0 ถึง n - 1 แล้วสลับกับช่อง 0
รอบ i = 1 หาค่าน้อยสุดในช่อง 1 ถึง n - 1 แล้วสลับกับช่อง 1
ทำจนถึงรอบ i = n - 2 ช่องสุดท้ายจะเหลือค่ามากสุดเอง

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

ต่างจาก bubble sort ตรงที่ส่วนที่เข้าที่แล้วโตจากทางซ้าย และแต่ละรอบสลับแค่ครั้งเดียว รอบ i = 1 กับ i = 3 ค่าน้อยสุดอยู่ที่ของมันอยู่แล้ว จึงไม่ต้องสลับ

#include <stdio.h>

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

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 = 0; i < n - 1; i++) {
        int min_index = i; // (1)!
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min_index]) {
                min_index = j;
            }
        }
        swap(&a[i], &a[min_index]); // (2)!
        printf("i = %d, min = %d: ", i, a[i]);
        print_array(a, n);
    }
    return 0;
}

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

i = 0, min = 2: 2 3 8 6 5
i = 1, min = 3: 2 3 8 6 5
i = 2, min = 5: 2 3 5 6 8
i = 3, min = 6: 2 3 5 6 8

เก็บเป็นฟังก์ชันได้แบบเดียวกับ bubble sort

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]);
    }
}

นับว่าสลับกี่ครั้ง

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

#include <stdio.h>

int original[1000], a[1000];

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

int bubble_swaps(int a[], int n)
{
    int count = 0;
    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]);
                count++;
            }
        }
    }
    return count;
}

int selection_swaps(int a[], int n)
{
    int count = 0;
    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;
            }
        }
        if (min_index != i) {
            swap(&a[i], &a[min_index]);
            count++;
        }
    }
    return count;
}

int main()
{
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &original[i]);
        }
        for (int i = 0; i < n; i++) {
            a[i] = original[i];
        }
        int bubble = bubble_swaps(a, n);
        for (int i = 0; i < n; i++) {
            a[i] = original[i];
        }
        int selection = selection_swaps(a, n);
        printf("n = %d: bubble %d swaps, selection %d swaps\n", n, bubble, selection);
    }
    return 0;
}

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

n = 5: bubble 6 swaps, selection 2 swaps
n = 8: bubble 28 swaps, selection 4 swaps
n = 8: bubble 0 swaps, selection 0 swaps

ก่อนเรียงแต่ละรอบต้องคัดลอกข้อมูลจาก original มาใหม่ ไม่อย่างนั้น selection sort จะได้ข้อมูลที่ bubble sort เรียงไว้แล้ว ผลที่ได้

bubble sort สลับเท่ากับจำนวนคู่ที่ผิดลำดับพอดี คู่ที่ผิดลำดับคือคู่ที่ตัวซ้ายมากกว่าตัวขวา ไม่จำเป็นต้องติดกัน ใน 6 3 8 2 5 มี 6 คู่ คือ 6-3 6-2 6-5 3-2 8-2 8-5 การสลับคู่ที่ติดกันหนึ่งครั้งแก้คู่ที่ผิดได้ทีละคู่เท่านั้น ข้อมูลที่เรียงกลับด้าน 8 ตัว ทุกคู่ผิดหมด 8 × 7 / 2 = 28 คู่
selection sort สลับไม่เกิน n - 1 ครั้ง เพราะสลับรอบละไม่เกินหนึ่งครั้ง ข้อมูลกลับด้าน 8 ตัวสลับแค่ 4 ครั้ง เพราะการสลับแต่ละครั้งวางค่าเข้าที่ได้สองตัว

แต่จำนวนครั้งที่เทียบของทั้งสองวิธีเท่ากัน คือ n(n - 1) / 2 ครั้ง (ไม่นับการหยุดก่อนของ bubble sort) เพราะลูปซ้อนทั้งคู่วนจำนวนรอบเท่ากัน หน้าถัดไปจะดูว่าตัวเลขนี้ทำให้ช้าแค่ไหนเมื่อ n ใหญ่

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

เปลี่ยนแค่เครื่องหมายที่เทียบ bubble sort เปลี่ยน a[j] > a[j + 1] เป็น a[j] < a[j + 1] คือสลับเมื่อตัวซ้ายน้อยกว่า ตัวน้อยจึงลอยไปท้ายแถวแทน ส่วน selection sort เปลี่ยนเป็นหาค่ามากสุดแทนค่าน้อยสุด ตัวอย่างนี้เรียงคะแนนสอบจากมากไปน้อย

#include <stdio.h>

int score[1000];

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

void bubble_sort_desc(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]);
            }
        }
    }
}

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

6
72 85 64 85 90 58

90 85 85 72 64 58

ลองทำให้พัง

แบบที่ 1 ลูปข้างในเกินไปหนึ่งช่อง

ในโปรแกรม bubble เปลี่ยนเงื่อนไขลูปข้างในเป็น j < n - i ดูเผินๆ เหมือนถูก เพราะลูปแบบ < n คุ้นตา

#include <stdio.h>

int height[1000];

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 - i; j++) {
            if (a[j] > a[j + 1]) {
                swap(&a[j], &a[j + 1]);
            }
        }
    }
}

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

8
152 148 160 155 149 171 158 163

148 0 149 152 155 158 160 163

ได้ 0 มาจากไหนไม่รู้ และคนที่สูงที่สุด 171 หายไป รอบแรก j ไปถึง 7 จึงเทียบ a[7] กับ a[8] ช่อง 8 ไม่ใช่ข้อมูลของเรา แต่เป็นช่องว่างของอาเรย์ 1000 ช่องที่ประกาศนอก main ซึ่งมีค่าเริ่มต้นเป็น 0 ตามหน้า 5.5 ค่ามากสุดจึงถูกสลับออกไปอยู่ช่อง 8 แล้ว 0 เข้ามาแทน รอบต่อๆ มา 0 ค่อยๆ เลื่อนไปทางซ้ายได้รอบละช่องเดียว จึงไปค้างอยู่ที่ช่อง 1 เมื่อครบ 7 รอบ

ถ้าอาเรย์ประกาศไว้พอดี n ช่อง a[n] จะเป็นหน่วยความจำของอย่างอื่น ผลจะเดาไม่ได้เลย เวลาเขียนลูปที่ใช้ a[j + 1] ให้ถามตัวเองเสมอว่า เมื่อ j เป็นค่าสุดท้าย j + 1 ยังอยู่ในข้อมูลไหม

แบบที่ 2 ลืมตั้ง min_index ใหม่ทุกรอบ

ในโปรแกรม selection sort ย้ายบรรทัดประกาศ min_index ออกไปไว้นอกลูป แล้วตั้งเป็น 0 ครั้งเดียว

#include <stdio.h>

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

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

2 5 3 8 6

รอบแรกถูก แต่รอบที่ 2 min_index ยังเป็น 3 จากรอบก่อน ซึ่งชี้ไปที่ช่องที่ตอนนี้เป็น 6 การหาค่าน้อยสุดจึงเริ่มเทียบกับ 6 แทนที่จะเริ่มจากช่อง 1 แล้วไปเจอ 5 ที่น้อยกว่า 6 แต่ไม่ได้น้อยกว่า 3 ซึ่งอยู่ช่อง 1 แล้ว 5 กับ 3 จึงถูกสลับผิดทาง ตัวแปรที่ต้องเริ่มใหม่ทุกรอบ ให้ประกาศไว้ในลูปแบบในตัวอย่างเดิม

สรุป

bubble sort เทียบคู่ที่ติดกัน ผิดลำดับก็สลับ แต่ละรอบค่ามากสุดที่เหลือลอยไปท้ายแถว ใช้ n - 1 รอบ ลูปข้างในหยุดที่ j < n - 1 - i
หยุดก่อนได้เมื่อรอบไหนไม่มีการสลับ ช่วยกับข้อมูลที่เกือบเรียง แต่ไม่ช่วยกรณีแย่ที่สุด
selection sort หาค่าน้อยสุดของส่วนที่เหลือมาวางที่ช่อง i สลับรอบละครั้ง ไม่เกิน n - 1 ครั้ง
bubble sort สลับเท่ากับจำนวนคู่ที่ผิดลำดับ ซึ่งมากได้ถึง n(n - 1) / 2 ส่วนทั้งสองวิธีเทียบ n(n - 1) / 2 ครั้งเท่ากัน
เรียงจากมากไปน้อยแค่กลับเครื่องหมายที่เทียบ
เขียนวิธีเรียงเองครั้งแรก ให้พิมพ์อาเรย์ทุกรอบออกมาดู และระวัง a[j + 1] ที่เกินข้อมูล