Sorted Arrays ใน C++ การแทรกและลบข้อมูล

ภาพรวม Sorted Array

Sorted Array คืออาร์เรย์ที่ข้อมูลถูกจัดเรียงลำดับ (มักเป็นน้อยไปมาก) อยู่แล้ว ข้อได้เปรียบคือการค้นหาเร็ว (Binary Search O(log n)) แต่การแทรก/ลบช้ากว่า Unsorted Array (O(n)) เพราะต้องเลื่อนข้อมูล

การแทรกข้อมูลใน Sorted Array (Insert)

ขั้นตอน:

1. หาตำแหน่งที่ควรแทรก (ใช้ Binary Search)
2. เลื่อนข้อมูลจากตำแหน่งนั้นไปขวา 1 ช่อง
3. วางค่าใหม่ในตำแหน่งที่ว่าง
4. เพิ่ม Size ขึ้น 1

อัลกอริทึม Insert

INSERT_SORTED(arr, n, key):
    IF n >= MAX_SIZE: RETURN ERROR
    i = n - 1
    WHILE i >= 0 AND arr[i] > key:
        arr[i + 1] = arr[i]
        i = i - 1
    arr[i + 1] = key
    n = n + 1

การลบข้อมูลจาก Sorted Array (Delete)

ขั้นตอน:

1. ค้นหาตำแหน่งของ Key (ใช้ Binary Search)
2. ถ้าไม่พบ → Return Error
3. เลื่อนข้อมูลจากตำแหน่งถัดไปไปซ้าย 1 ช่อง
4. ลด Size ลง 1

อัลกอริทึม Delete

DELETE_SORTED(arr, n, key):
    pos = BINARY_SEARCH(arr, 0, n-1, key)
    IF pos == -1: RETURN NOT_FOUND
    FOR i = pos TO n-2:
        arr[i] = arr[i + 1]
    n = n - 1

Binary Search Helper

int binarySearch(int arr[], int low, int high, int key) {
    if (high < low) return -1;
    int mid = low + (high - low) / 2;
    if (key == arr[mid]) return mid;
    if (key > arr[mid]) return binarySearch(arr, mid + 1, high, key);
    return binarySearch(arr, low, mid - 1, key);
}

ตัวอย่างโค้ด C++ สมบูรณ์

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX = 100;

void display(int arr[], int n) {
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
}

int binarySearch(int arr[], int low, int high, int key) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == key) return mid;
        if (arr[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

bool insertSorted(int arr[], int& n, int key) {
    if (n >= MAX) {
        cout << "Array is full!\n";
        return false;
    }
    
    // หาตำแหน่งแทรก (Lower Bound)
    int i = n - 1;
    while (i >= 0 && arr[i] > key) {
        arr[i + 1] = arr[i];
        i--;
    }
    arr[i + 1] = key;
    n++;
    return true;
}

bool deleteSorted(int arr[], int& n, int key) {
    int pos = binarySearch(arr, 0, n - 1, key);
    if (pos == -1) {
        cout << "Element " << key << " not found.\n";
        return false;
    }
    
    for (int i = pos; i < n - 1; i++) {
        arr[i] = arr[i + 1];
    }
    n--;
    return true;
}

int main() {
    int arr[MAX] = {};
    int n = 0;
    
    cout << "=== Sorted Array Demo ===\n\n";
    
    // Insert
    cout << "Inserting: 10, 20, 30, 40, 50, 60, 70\n";
    insertSorted(arr, n, 10);
    insertSorted(arr, n, 20);
    insertSorted(arr, n, 30);
    insertSorted(arr, n, 40);
    insertSorted(arr, n, 50);
    insertSorted(arr, n, 60);
    insertSorted(arr, n, 70);
    display(arr, n);
    
    // Delete
    cout << "\nDeleting 35 (not exist): ";
    deleteSorted(arr, n, 35);
    display(arr, n);
    
    cout << "Deleting 40: ";
    deleteSorted(arr, n, 40);
    display(arr, n);
    
    cout << "Deleting 60: ";
    deleteSorted(arr, n, 60);
    display(arr, n);
    
    // Insert ใหม่
    cout << "\nInserting 35, 55:\n";
    insertSorted(arr, n, 35);
    insertSorted(arr, n, 55);
    display(arr, n);
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

=== Sorted Array Demo ===

Inserting: 10, 20, 30, 40, 50, 60, 70
10 20 30 40 50 60 70

Deleting 35 (not exist):
Element 35 not found.
10 20 30 40 50 60 70
Deleting 40:
10 20 30 50 60 70
Deleting 60:
10 20 30 50 70

Inserting 35, 55:
10 20 30 35 50 55 70

การใช้ STL แทนการเขียนเอง

ใน C++ จริง ควรใช้ std::vector + std::lower_bound + insert/erase:

#include <vector>
#include <algorithm>

vector sortedVec;

void insertSorted(vector& v, int key) {
    auto it = lower_bound(v.begin(), v.end(), key);
    v.insert(it, key);  // O(n) shift
}

void deleteSorted(vector& v, int key) {
    auto it = lower_bound(v.begin(), v.end(), key);
    if (it != v.end() && *it == key) {
        v.erase(it);  // O(n) shift
    }
}

เปรียบเทียบโครงสร้างข้อมูลสำหรับข้อมูลเรียงลำดับ

* Average case, ** ถ้าเพิ่มท้ายแล้ว Sort ครั้งเดียว

เมื่อไหร่ควรใช้ Sorted Array?

• ข้อมูลไม่เปลี่ยนแปลงบ่อย (Read-heavy, Write-rare)
• ต้องการ Memory Efficiency (ไม่มี Pointer Overhead)
• Cache Friendly (Contiguous Memory)
• ข้อมูลขนาดเล็ก-ปานกลาง (n < 10,000)
• ต้องการ Random Access ด้วย Index

ข้อควรระวัง

• Insert/Delete ที่กลางอาร์เรย์ ต้อง Shift ข้อมูล O(n)
• Fixed Size Array ต้องจัดการ Capacity เอง
• Duplicate Values: Binary Search หาตำแหน่งไหนก็ได้ของค่าที่ซ้ำ
• ใช้ std::lower_bound/upper_bound สำหรับ Range Query