การเรียงแบบฟองและแบบแทรก

การเรียงลำดับแบบง่าย

การทำงานของการเรียงลำดับแบบฟอง

การสลับจำนวนเต็มสองตัว

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

int main(void) {
    int x = 1, y = 2;
    swap(&x, &y);
    printf("%d %d\n", x, y);
    return 0;
}

การใช้งานการเรียงลำดับแบบฟอง

#include <stdio.h>

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]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
            }
}

int main(void) {
    int a[] = {5, 2, 9, 1, 3};
    bubble_sort(a, 5);
    for (int i = 0; i < 5; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

การปรับปรุงด้วยการหยุดก่อน

#include <stdio.h>

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

int main(void) {
    int a[] = {1, 2, 3, 4, 5};
    bubble_sort(a, 5);
    printf("sorted with early exit\n");
    return 0;
}

การทำงานของการเรียงลำดับแบบแทรก

การใช้งานการเรียงลำดับแบบแทรก

#include <stdio.h>

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(void) {
    int a[] = {5, 2, 9, 1, 3};
    insertion_sort(a, 5);
    for (int i = 0; i < 5; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

การเรียงลำดับแบบแทรกกับข้อมูลที่เกือบเรียงลำดับแล้ว

#include <stdio.h>

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

int main(void) {
    int a[] = {1, 2, 4, 3, 5}; /* one out of place */
    insertion_sort(a, 5);
    for (int i = 0; i < 5; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

ความคงเสถียร

การเปรียบเทียบความซับซ้อน

การนับการดำเนินการ

#include <stdio.h>

int main(void) {
    int a[] = {5, 4, 3, 2, 1};
    int n = 5; long cmp = 0;
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && (cmp++, a[j] > key)) { a[j+1] = a[j]; j--; }
        a[j+1] = key;
    }
    printf("comparisons = %ld\n", cmp);
    return 0;
}

ตรวจสอบความเข้าใจ

สรุปทบทวน