Sorting Algorithms

Input: list ที่ยังไม่เรียง → Output: list ที่เรียงแล้ว เรียงเสร็จแล้วปัญหาอื่นง่ายขึ้นเยอะ

ทำไมต้อง sort

ก่อน:  34, 8, 64, 51, 32, 21, 1, 2, 9, 10
หลัง:  1, 2, 8, 9, 10, 21, 32, 34, 51, 64

[1, 2, 12, 19, 30, 32, 50]  หา k = 3 ตัวที่ใหญ่สุด → 30 (อ่านจาก index ได้เลย)

Bubble Sort

• อัลกอริทึมเรียงที่ง่ายที่สุดแบบหนึ่ง
• เทียบตัวที่ติดกัน ถ้าสลับที่ผิดก็สลับกัน
• รอบ i จะดันค่ามากสุดไปอยู่ท้ายสุด (max sort)

i=0   j < n-i-1 = 5
  34 8 64 51 32 21   → สลับ 34,8
   8 34 64 51 32 21  → 34<64 ไม่สลับ
   8 34 64 51 32 21  → สลับ 64,51
   8 34 51 64 32 21  → สลับ 64,32
   8 34 51 32 64 21  → สลับ 64,21
   8 34 51 32 21 64  ← 64 เข้าที่แล้ว

i=1   j < 6-1-1 = 4   →  8 34 32 21 51 64
i=2   j < 6-2-1 = 3   →  8 32 21 34 51 64
i=3   j < 6-3-1 = 2   →  8 21 32 34 51 64
i=4   j < 6-4-1 = 1   →  8 21 32 34 51 64  (เรียงเสร็จ)

โค้ด Bubble Sort

public static int[] bubbleSort(int[] arr)
{
    int n = arr.length;
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1])
            {
                // swap arr[j] and arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
    return arr;
}

ทำไมเป็น O(n²)

วาดเป็นตาราง n × n แล้วนับจำนวนช่องที่ทำงานจริง

พื้นที่สี่เหลี่ยมทั้งหมด  = n²
เส้นทแยงมุม             = n
ครึ่งสามเหลี่ยมที่ใช้จริง = (n² - n)/2

O((n² - n)/2)  →  O(n²)

อีกมุมหนึ่ง: รอบที่ 1 เทียบ n-1 ครั้ง, รอบที่ 2 เทียบ n-2 ครั้ง, … รวม = (n-1)+(n-2)+…+1 = n(n-1)/2

ปรับปรุงด้วย flag swapped

void bubbleSort(int[] arr)
{
    int n = arr.length;
    boolean swapped;
    for (int i = 0; i < n-1; i++) {
        swapped = false;
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swapped = true;
            }
        // ถ้าทั้งรอบไม่มีการสลับเลย แปลว่าเรียงเสร็จแล้ว
        if (swapped == false) {
            break;
        }
    }
}

Insertion Sort

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

Insertion(a)
{
    n = a.len
    for(i = 1 ; i < n ; i++) {
        min = a[i]; pos = i;
        for(j = 0 ; j < i ; j++) {
            if(a[i] < a[j]){
                min = a[j]; pos = j;
            }
        }
        // เลื่อน a[pos..i-1] ไปทางขวา 1 ช่อง
        for(k = i-1 ; k >= pos ; k--) {
            tmp = a[k]
            a[k+1] = tmp
        }
        // แทรกค่าที่ตำแหน่ง pos
        a[pos] = min
    }
}

วิเคราะห์

• ต้องไล่ดูทุกตัวอย่างน้อย 1 รอบ → ต้องมีลูปนอกเสมอ
• จำนวนครั้งที่ต้องเลื่อนขึ้นกับ input
• ถ้า input เรียงมาแล้ว ไม่ต้องเลื่อนเลย → Ω(n)
• ถ้า input เรียงจากมากไปน้อย ต้องเลื่อนทุกตัว → O(n²)

ทบทวน Recursive

public static int funny(int z)
{
    if(z == 3)          // base case — เงื่อนไขหยุด
    {
        return z;
    }
    else{
        return funny(z+1);
    }
}

Tower of Hanoi

hanoi(n, a, c, b)   // n = จำนวนจาน, ย้ายจาก a ไป c โดยมี b เป็นตัวพัก
{
    if(n == 0)
    {
        return;
    }
    hanoi(n-1, a, b, c)
    print(a + " -> " + c)
    hanoi(n-1, b, c, a)
}

แก้ recurrence:

T(n)   = 2·T(n-1) + 1
T(n-1) = 2·T(n-2) + 1
T(n-2) = 2·T(n-3) + 1
…
T(n) = 2³·T(n-3) + 2² + 2¹ + 2⁰
T(n) = 2ⁿ⁻¹·T(1) + 2ⁿ⁻² + … + 2² + 2¹ + 2⁰
T(n) = (2ⁿ - 1)/(2 - 1)   →  O(2ⁿ)

Merge Sort

• เป็น recursion แบบ Divide and Conquer
• Divide: แบ่ง array ใหญ่เป็นสองส่วนไปเรื่อย ๆ จนเหลือชิ้นละ 1 ตัว
• Conquer (Merge): รวมสอง array ที่เรียงแล้วเข้าด้วยกันแบบเรียงน้อยไปมาก

Divide step

divide(a, l, r){
    if(l >= r)              // base case: เหลือตัวเดียว
        return;

    m = (r-l)/2

    divide(a, l, m)
    divide(a, m+1, r)
    merge(a, l, m, r)
}

Merge step — รวม 2 array ที่เรียงแล้ว

A = [1, 13, 24, 26]      B = [2, 15, 27, 38]

เทียบหัวต่อหัวแล้วหยิบตัวน้อยกว่าใส่ C:
C = [1, 2, 13, 15, 24, 26, 27, 38]

int[] sort_min_to_max(int[] a, int[] b){
    int[] c = new int[a.length + b.length];
    i = 0; j = 0; k = 0;
    while(true){
        // ถ้า a หมดก่อน เทที่เหลือของ b ลง c
        if(i >= a.length) {
            for (int l = j; l < b.length; l++) { c[k] = b[l]; k = k + 1; }
            break;
        }
        // ถ้า b หมดก่อน เทที่เหลือของ a ลง c
        if(j >= b.length){
            for (int l = i; l < a.length; l++) { c[k] = a[l]; k = k + 1; }
            break;
        }
        if(a[i] < b[j]){
            c[k] = a[i];
            i = i + 1;
        }else{
            c[k] = b[j];
            j = j + 1;
        }
        k = k + 1;
    }
    return c;
}

merge เต็มรูปแบบ: copy ออกมาเป็น 2 array → รวมแบบเรียง → เขียนกลับลง array เดิม

merge(a, l, m, r){
    a1 ← {a[l], … , a[m]}
    a2 ← {a[m+1], … , a[r]}

    int[] C = sort_min_to_max(a1, a2);

    int q = 0;
    for (int k = l; k <= r; k++) {
        a[k] = C[q];
        q = q + 1;
    }
}

วิเคราะห์ Merge Sort

เฉพาะ divide step

T(n) = 2T(n/2) + k
     = 2(2T(n/4) + k) + k
     = 4T(n/4) + 3k
     = …
     = n·T(1) + (n-1)k
     = 2nk - k        →  O(n)

คิดจากต้นไม้: ชั้นล่างสุดทำงาน n ครั้ง ส่วนชั้นบนรวมกันแล้วยังน้อยกว่า n

2⁰ + 2¹ + … + 2^(k-2)  <  2^(k-1)
ดังนั้น O(n) + O(<n) → O(n)

divide + merge รวมกัน

T(1) = 1
T(N) = 2T(N/2) + N        // +N เพราะ merge ต้องไล่ข้อมูล N ตัว

หารด้วย N ทั้งสมการ:
T(N)/N     = T(N/2)/(N/2) + 1
T(N/2)/(N/2) = T(N/4)/(N/4) + 1
…
T(2)/2     = T(1)/1 + 1

T(N)/N = T(1)/1 + log₂N
T(N)   = N + N·log₂N      →  Θ(n log n)

ชั้น 0:  เรียงข้อมูล 8           = 8 ครั้ง
ชั้น 1:  เรียงข้อมูล 4 + 4       = 8 ครั้ง
ชั้น 2:  เรียงข้อมูล 2+2+2+2     = 8 ครั้ง
มี log₂8 = 3 ชั้น  →  8 × 3

สรุปเทียบทุกวิธี