Sorting: sắp xếp đơn hàng theo tiền, theo ngày, lấy top-k

Được. Bài 1.14 đã có Big-O, giờ dùng nó để hiểu sorting. Trong shop-backend ta sort suốt: đơn theo số tiền, theo ngày tạo, lấy top 10 đơn lớn nhất. Học theo thứ tự này:

1. Bài toán

Có danh sách số tiền đơn hàng (đơn vị nghìn đồng): [5, 3, 8, 2]. Cần sắp tăng dần. Ví dụ nhỏ để trace bằng tay; ý tưởng giống hệt với 1 triệu đơn.

2. Vấn đề

Điểm quan trọng nhất lúc này không phải thuộc code. Với mỗi thuật toán, hãy trả lời 3 câu: so sánh cái gì → khi nào đổi chỗ → sau mỗi vòng, phần tử nào chắc chắn đã đúng vị trí?

3. Giải pháp: ba thuật toán O(n²) cơ bản

Bubble Sort: so sánh từng cặp cạnh nhau, lớn hơn thì đổi. Sau mỗi vòng, số lớn nhất "nổi" về cuối.

Vòng 1:
5 3 8 2      5 > 3 → đổi
3 5 8 2      5 < 8 → giữ
3 5 8 2      8 > 2 → đổi
3 5 2 8      ← 8 đã đúng chỗ
Vòng 2:  3 5 2 8 → 3 2 5 8
Vòng 3:  3 2 5 8 → 2 3 5 8

Selection Sort: tìm phần tử nhỏ nhất trong phần chưa sort → đưa nó lên đầu.

[5, 3, 8, 2]     nhỏ nhất = 2 → đổi 5 ↔ 2 → [2 | 3, 8, 5]
[2 | 3, 8, 5]    nhỏ nhất = 3, đã đúng chỗ  → [2, 3 | 8, 5]
[2, 3 | 8, 5]    nhỏ nhất = 5 → đổi 8 ↔ 5 → [2, 3, 5, 8]

Insertion Sort: như xếp bài trên tay. Lấy từng phần tử, chèn vào đúng chỗ trong phần bên trái đã sort.

[5 | 3, 8, 2]    lấy 3: 3 < 5 → dịch 5 sang phải → [3, 5 | 8, 2]
[3, 5 | 8, 2]    lấy 8: 8 > 5 → giữ nguyên      → [3, 5, 8 | 2]
[3, 5, 8 | 2]    lấy 2:
                 2 < 8 → dịch 8   [3, 5, _, 8]
                 2 < 5 → dịch 5   [3, _, 5, 8]
                 2 < 3 → dịch 3   [_, 3, 5, 8]
                 chèn 2           [2, 3, 5, 8]

4. Code từng bước

Bước 1: Bubble Sort

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < arr.length - 1 - i; j++) {   // phần cuối đã đúng chỗ
            if (arr[j] > arr[j + 1]) {
                int t = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = t;
                swapped = true;
            }
        }
        if (!swapped) break;                              // đã sort → best case O(n)
    }
}

Bước 2: Selection Sort

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) minIndex = j;
        }
        int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp;
    }
}

Bước 3: Insertion Sort

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int current = arr[i];              // "cầm thằng này lên, tìm chỗ nhét vào"
        int j = i - 1;
        while (j >= 0 && arr[j] > current) {
            arr[j + 1] = arr[j];           // thằng bên trái lớn hơn → đẩy sang phải
            j--;
        }
        arr[j + 1] = current;              // tìm được chỗ → chèn
    }
}

Bước 4: test nhanh

int[] amounts = {5, 3, 8, 2};
insertionSort(amounts);
System.out.println(Arrays.toString(amounts));   // [2, 3, 5, 8]

5. Cách hoạt động: vì sao O(n²)

Bubble    → so sánh 2 thằng cạnh nhau → thằng lớn dần nổi về cuối
Selection → tìm thằng nhỏ nhất         → đưa nó về đầu
Insertion → lấy một số                 → chèn vào phần đã sort

Cả ba: vòng ngoài n lần × vòng trong ~n lần
n = 1000 → 1000 × 999 / 2 ≈ 500.000 phép so sánh

6. So sánh

7. Khi nào nên dùng / không nên

• Insertion Sort: mảng nhỏ hoặc gần như đã sort. Chính Java dùng nó cho đoạn nhỏ bên trong TimSort / Quicksort.
• Bubble, Selection: chủ yếu để học. Không dùng trong code thật.
• Dữ liệu lớn: cần O(n log n).

Từ đây khác 3 thuật toán trước: chuyển từ O(n²) sang O(n log n). Ý tưởng: chia nhỏ mảng → sort các mảng nhỏ → merge lại. Đây là thuật toán điển hình của Divide and Conquer (chia để trị).

Bước 1: Chia đôi liên tục
          [5, 3, 8, 2]
          /          \
      [5, 3]        [8, 2]
      /    \        /    \
    [5]    [3]    [8]    [2]     ← 1 phần tử = đã sort

Bước 2: Merge ngược lên
    [5]+[3] → [3, 5]       [8]+[2] → [2, 8]

    Merge [3, 5] và [2, 8], so sánh phần tử đầu:
    3 vs 2 → lấy 2   [2]
    3 vs 8 → lấy 3   [2, 3]
    5 vs 8 → lấy 5   [2, 3, 5]
    còn 8            [2, 3, 5, 8]

Vì sao O(n log n)? Mỗi lần chia đôi: 8 → 4 → 2 → 1, tức log₂(n) tầng (log₂8 = 3). Mỗi tầng merge tổng cộng n phần tử. Vậy n × log n.

n = 1.000.000:
n²         ≈ 1.000.000.000.000
n log₂ n   ≈ 20.000.000

public static void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;   // tránh tràn int
    mergeSort(arr, left, mid);             // chia
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);          // ghép
}

static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];  // O(n) bộ nhớ phụ
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];  // <= giữ stable
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    System.arraycopy(temp, 0, arr, left, temp.length);
}

Đánh đổi cần nhớ: nhanh hơn nhóm O(n²) khi dữ liệu lớn, worst case vẫn O(n log n), nhưng tốn thêm bộ nhớ O(n). Dấu <= khi merge làm Merge Sort stable.

Quick Sort rất hay được hỏi cùng Merge Sort. Ý tưởng: chọn một phần tử làm pivot → số nhỏ hơn pivot sang trái, lớn hơn sang phải → làm tương tự cho hai bên. Cũng Divide and Conquer, nhưng cách chia khác.

[5, 3, 8, 2, 7]   pivot = 7 (phần tử cuối)
partition →  [5, 3, 2] [7] [8]     ← 7 đã nằm ĐÚNG vị trí cuối cùng
[5, 3, 2]         pivot = 2 → [] [2] [5, 3]
[5, 3]            pivot = 3 → [] [3] [5]
Kết quả: [2, 3, 5, 7, 8]

Cốt lõi:  [ nhỏ hơn pivot | pivot | lớn hơn pivot ]

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int p = partition(arr, low, high);
        quickSort(arr, low, p - 1);
        quickSort(arr, p + 1, high);
    }
}

static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;                       // biên của vùng "nhỏ hơn pivot"
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
        }
    }
    int t = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = t;
    return i + 1;                          // vị trí cuối cùng của pivot
}

Complexity: best/average O(n log n), worst O(n²). Worst xảy ra khi pivot tệ, ví dụ mảng đã sort mà luôn chọn phần tử cuối:

[1,2,3,4,5]  pivot 5 → [1,2,3,4] | 5
             pivot 4 → [1,2,3] | 4 | 5 ...

Lẽ ra:   n           Thực tế:  n
        / \                     \
      n/2  n/2                  n-1
                                  \
                                  n-2  → O(n²)

Cách tránh: random pivot, phần tử giữa, median-of-three. Quick Sort sort tại chỗ, chỉ tốn O(log n) stack, nhưng không stable.

Merge Sort → chia đôi trước → sort → MERGE lại
Quick Sort → chọn PIVOT → PARTITION → sort hai bên

Bảng tổng hợp (Heap Sort chỉ cần biết: dựng heap rồi lấy max liên tục, O(n log n) mọi trường hợp, O(1) bộ nhớ, không stable):

Đúng, trong công việc thực tế gần như không ai tự viết Bubble, Merge hay Quick Sort. Java chỉ cần list.sort(...) hoặc Collections.sort(list). Phỏng vấn hỏi sorting không phải để xem bạn tự implement, mà để kiểm tra nền tảng:

1. Tư duy Big-O: hiểu vì sao O(n log n) tốt hơn O(n²) khi dữ liệu lớn.
2. Phân tích trade-off: Merge O(n) bộ nhớ, Quick worst O(n²). "Vậy sao không luôn dùng Merge Sort?" mới là phần họ muốn nghe.
3. Recursion / divide and conquer: một bài sort kiểm tra được recursion, index, swap, complexity, memory.
4. Sort là bước đầu của bài khác. Ví dụ: tìm 2 đơn có tổng bằng target. Hai vòng lặp là O(n²); sort trước rồi dùng two pointers là O(n log n) + O(n). Họ muốn biết bạn có nghĩ đến việc sort không.

Với Java developer, nên nắm đến mức:

Bubble / Selection / Insertion → hiểu ý tưởng → biết O(n²)
Merge Sort → Divide & Conquer → O(n log n) → cần extra memory
Quick Sort → Pivot + Partition → average O(n log n) → worst O(n²)
Java sorting → Comparator / Comparable, Java dùng thuật toán gì, vì sao

Thấy "1 triệu records" là phải phản xạ: O(n²) ❌, O(n log n) ✓. Sau đó đáng học hơn là các pattern dùng sort: Two Pointers, Binary Search, Top K.

Java dùng hai thuật toán khác nhau tùy kiểu dữ liệu:

• Vì sao primitive dùng Quicksort: nhanh trong thực tế (cache-friendly, không cần mảng phụ). Stable vô nghĩa với số nguyên. Hai pivot chia thành 3 đoạn, ít so sánh hơn; đoạn nhỏ chuyển insertion sort.
• Vì sao object dùng TimSort: object cần stable. Sort đơn theo ngày rồi theo tiền thì các đơn cùng tiền phải giữ thứ tự ngày. TimSort tìm các "run" đã sort sẵn, nên dữ liệu thật (thường gần sort) chạy gần O(n); worst O(n log n).

Comparable vs Comparator

// Comparable: thứ tự "tự nhiên", nằm trong class
public record Order(String id, BigDecimal amount, LocalDateTime createdAt, OrderStatus status)
        implements Comparable<Order> {
    @Override
    public int compareTo(Order o) { return createdAt.compareTo(o.createdAt); }
}
Collections.sort(orders);   // theo createdAt

// Comparator: thứ tự bên ngoài, tạo bao nhiêu cũng được
orders.sort(Comparator.comparing(Order::amount).reversed()      // tiền giảm dần
        .thenComparing(Order::createdAt));                      // cùng tiền → cũ trước

// null-safe
orders.sort(Comparator.comparing(Order::createdAt,
        Comparator.nullsLast(Comparator.naturalOrder())));

Lưu ý: không viết (a, b) -> a.qty() - b.qty(), có thể tràn int; dùng Integer.compare hoặc Comparator.comparingInt.

Top-k đơn lớn nhất: không cần sort cả list.

// Sort cả list: O(n log n)
List<Order> top10 = orders.stream()
        .sorted(Comparator.comparing(Order::amount).reversed())
        .limit(10).toList();

// Min-heap kích thước k: O(n log k), tốt khi n rất lớn, k nhỏ
PriorityQueue<Order> heap = new PriorityQueue<>(Comparator.comparing(Order::amount));
for (Order o : orders) {
    heap.offer(o);
    if (heap.size() > 10) heap.poll();     // bỏ đơn nhỏ nhất
}

Còn nếu dữ liệu nằm trong DB: ORDER BY amount DESC LIMIT 10 với index, đừng load về rồi sort.

Câu 1: Merge Sort và Quick Sort khác nhau thế nào?

🇻🇳 Tiếng Việt:

Cả hai đều là divide and conquer, trung bình O(n log n). Merge Sort chia đôi, sort từng nửa rồi merge; worst case vẫn O(n log n), stable, nhưng tốn O(n) bộ nhớ phụ. Quick Sort chọn pivot, partition để nhỏ hơn bên trái, lớn hơn bên phải, rồi đệ quy hai bên; sort tại chỗ nhưng không stable, và worst case O(n²) nếu pivot tạo partition lệch, ví dụ mảng đã sort mà luôn chọn phần tử cuối. Chọn pivot random hoặc median-of-three để tránh.

🇬🇧 English:

Both are divide and conquer with O(n log n) on average. Merge sort splits the array in half, sorts each half and merges them; it stays O(n log n) in the worst case and is stable, but needs O(n) extra memory. Quick sort picks a pivot, partitions smaller elements to the left and larger to the right, then recurses on both sides; it sorts in place but isn't stable, and degrades to O(n²) when partitions are unbalanced, for example an already sorted array with the last element as pivot. Random or median-of-three pivots avoid that.

Câu 2: Java dùng thuật toán sort nào? Vì sao khác nhau?

🇻🇳 Tiếng Việt:

Arrays.sort cho mảng primitive dùng Dual-Pivot Quicksort, vì nhanh, tại chỗ, và với primitive không cần stable. Còn sort object như Collections.sort, List.sort dùng TimSort, kết hợp merge sort và insertion sort, vì object cần stable và dữ liệu thực tế thường đã sort một phần nên TimSort chạy gần O(n). Trong dự án em sort đơn hàng bằng Comparator.comparing(Order::amount).reversed().thenComparing(Order::createdAt).

🇬🇧 English:

Arrays.sort on primitive arrays uses Dual-Pivot Quicksort because it's fast, in place, and stability doesn't matter for primitives. Sorting objects with Collections.sort or List.sort uses TimSort, a hybrid of merge sort and insertion sort, because objects need a stable sort and real data is often partly sorted, so TimSort gets close to O(n). In my project I sort orders with Comparator.comparing(Order::amount).reversed().thenComparing(Order::createdAt).

Câu 3: Stable sort là gì? Comparable và Comparator khác nhau?

🇻🇳 Tiếng Việt:

Stable sort giữ nguyên thứ tự tương đối của các phần tử bằng nhau, nên sort nhiều lần theo nhiều tiêu chí vẫn đúng. Comparable định nghĩa thứ tự tự nhiên bên trong class qua compareTo, chỉ có một. Comparator là thứ tự bên ngoài, tạo được nhiều cái và nối bằng thenComparing, reversed, nullsLast.

🇬🇧 English:

A stable sort keeps equal elements in their original relative order, so sorting by several criteria in sequence works correctly. Comparable defines a single natural order inside the class via compareTo. Comparator is an external order; you can have many and chain them with thenComparing, reversed and nullsLast.

Câu 4: Lấy top 10 đơn lớn nhất trong 10 triệu đơn?

🇻🇳 Tiếng Việt:

Nếu dữ liệu trong DB thì để DB làm: ORDER BY amount DESC LIMIT 10 có index. Nếu đã ở trong bộ nhớ, em dùng min-heap PriorityQueue kích thước 10: duyệt một lần, heap vượt 10 thì poll phần tử nhỏ nhất. Độ phức tạp O(n log k) và O(k) bộ nhớ, tốt hơn sort cả list O(n log n).

🇬🇧 English:

If the data is in the database, let it do the work: ORDER BY amount DESC LIMIT 10 with an index. If it's already in memory, I use a min-heap PriorityQueue of size 10: one pass, and when the heap exceeds 10 I poll the smallest. That's O(n log k) time and O(k) memory, better than sorting the whole list in O(n log n).

Cách nhớ ngắn gọn

• Bubble đổi cặp, Selection tìm min, Insertion chèn: O(n²), Insertion tốt khi gần sort.
• Merge: chia → merge, O(n log n) luôn, O(n) RAM, stable.
• Quick: pivot + partition, tại chỗ, worst O(n²), không stable.
• Java: primitive → Dual-Pivot Quicksort; object → TimSort (stable).
• Top-k: heap O(n log k); trong DB thì ORDER BY + LIMIT.