Mảng đã sắp xếp (Sorted Arrays) trong C++

Mảng đã sắp xếp luôn duy trì thứ tự. Khi chèn phần tử mới, tự đặt đúng vị trí không cần sắp xếp lại. Khi xóa, dịch chuyển phần tử bên phải lấp đầy. Tìm kiếm dùng binary search.

Thuật toán

Chèn vào mảng đã sắp xếp

insertSorted(arr, n, key):
    if n >= MAX_SIZE return
    i = n - 1
    while i >= 0 và arr[i] > key:
        arr[i+1] = arr[i]
        i--
    arr[i+1] = key
    n++

Xóa khỏi mảng đã sắp xếp

deleteSorted(arr, n, key):
    pos = binary_search(arr, key)
    if pos == -1 return
    for i = pos to n-2:
        arr[i] = arr[i+1]
    n--

Ví dụ mã nguồn

#include <iostream>
#define MAX 10
using namespace std;

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

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

void chen(int arr[], int &n, int key) {
    if (n >= MAX) { cout << "Mảng đầy\n"; return; }
    int i;
    for (i = n-1; i >= 0 && arr[i] > key; i--)
        arr[i+1] = arr[i];
    arr[i+1] = key;
    n++;
}

void xoa(int arr[], int &n, int key) {
    int pos = timKiemNhiPhan(arr, 0, n-1, key);
    if (pos == -1) { cout << "Không tìm thấy\n"; return; }
    for (int i = pos; i < n-1; i++)
        arr[i] = arr[i+1];
    n--;
}

int main() {
    int arr[MAX]; int n = 0;
    chen(arr, n, 10); chen(arr, n, 20); chen(arr, n, 30);
    chen(arr, n, 40); chen(arr, n, 50); chen(arr, n, 60); chen(arr, n, 70);
    hienThi(arr, n);
    xoa(arr, n, 35); xoa(arr, n, 40); xoa(arr, n, 60);
    hienThi(arr, n);
    return 0;
}

Kết quả

10 20 30 40 50 60 70
Không tìm thấy
10 20 30 50 70