[Java Basics] Các thuật toán cơ bản với mảng trong Java: tìm max/min, tìm kiếm và sắp xếp

Gần như mọi thuật toán với mảng đều có chung một hình dạng: một vòng lặp chạy qua các index, và một hai variable mang state từ lần lặp này sang lần lặp khác. Tìm giá trị lớn nhất, tính tổng, đếm, tìm kiếm và sắp xếp đều là đúng mẫu đó với state khác nhau.

Bug không nằm ở vòng lặp. Nó nằm ở giá trị khởi tạo của state, ở phép tính bị overflow, và ở giả định mà một method thư viện âm thầm đặt ra về dữ liệu của bạn. Bài này đi qua các thuật toán chuẩn và chứng minh từng lỗi đó bằng output thật.

Mọi dòng output, message lỗi và con số đếm bên dưới đều lấy từ việc compile và chạy code thật trên OpenJDK 21.0.6. Chi phí được diễn đạt bằng số comparison và số swap đếm được từ vòng lặp đã gắn counter, không bao giờ bằng thời gian chạy — một counter cho ra cùng một con số trên mọi máy, còn đồng hồ bấm giờ thì không.

Tìm max và min trong mảng

Mẫu running max giữ một variable, so nó với từng phần tử, và thay thế khi gặp phần tử lớn hơn. Tìm min là đúng vòng lặp đó với dấu so sánh đảo lại.

public class MaxMin {
    public static void main(String[] args) {
        int[] temps = {17, 23, 12, 29, 8, 31, 21};

        int max = temps[0];
        int min = temps[0];
        for (int i = 1; i < temps.length; i++) {
            if (temps[i] > max) max = temps[i];
            if (temps[i] < min) min = temps[i];
        }
        System.out.println("max = " + max);
        System.out.println("min = " + min);
    }
}

max = 31
min = 8

Có hai chi tiết làm nên tính đúng đắn ở đây. State được khởi tạo từ temps[0], nên vòng lặp bắt đầu từ i = 1 — phần tử số 0 đã được dùng rồi. In state ra ở mỗi bước thì thấy ngay hình dạng của nó:

init   max=17 best=0
i=1 a[i]=23  UPDATE  max=23 best=1
i=2 a[i]=12  keep    max=23 best=1
i=3 a[i]=29  UPDATE  max=29 best=3
i=4 a[i]=8  keep    max=29 best=3
i=5 a[i]=31  UPDATE  max=31 best=5
i=6 a[i]=21  keep    max=31 best=5
max 31 at index 5

Chỉ ba trong sáu lần so sánh làm thay đổi state. Đó là chuyện bình thường: state hiếm khi được cập nhật nhưng liên tục được đọc.

Vì sao khởi tạo max = 0 là một bug

Khởi tạo state bằng một literal thay vì bằng dữ liệu của mảng vẫn chạy đúng cho tới khi mọi phần tử đều nhỏ hơn literal đó. Với int max = 0, thân của if không bao giờ chạy, và method trả về một con số vốn không hề có trong mảng.

public class ZeroInit {
    static int maxFromZero(int[] a) {
        int max = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] > max) max = a[i];
        }
        return max;
    }

    static int maxFromFirst(int[] a) {
        int max = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] > max) max = a[i];
        }
        return max;
    }

    public static void main(String[] args) {
        int[] losses = {-9, -3, -14, -7, -21};
        System.out.println("max init 0     = " + maxFromZero(losses));
        System.out.println("max init a[0]  = " + maxFromFirst(losses));

        int[] mixed = {4, 9, 2};
        System.out.println("mixed, init 0  = " + maxFromZero(mixed));
        System.out.println("mixed, init a[0] = " + maxFromFirst(mixed));
    }
}

max init 0     = 0
max init a[0]  = -3
mixed, init 0  = 9
mixed, init a[0] = 9

Bản khởi tạo bằng 0 cho kết quả đúng trên mảng có số dương và sai trên mảng toàn số âm — đó chính là lý do nó sống sót qua khâu test. Nhiệt độ dưới 0, số dư tài khoản, độ chênh lệch, độ cao so với mực nước biển: chỉ cần dữ liệu thật xuống dưới 0 là đáp án lập tức thành 0.

Khởi tạo bằng Integer.MIN_VALUE là một biến thể khác của cùng sai lầm. Nó cho kết quả đúng với mảng khác rỗng, nhưng lại trả về -2147483648 cho mảng rỗng, tức cũng là một giá trị không có trong mảng. Giá trị khởi tạo duy nhất không thể nói dối là một phần tử của chính mảng đó.

Còn lại trường hợp mảng rỗng phải xử lý riêng, vì a[0] không tồn tại:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0
	at EmptyMax.main(EmptyMax.java:4)

"Giá trị lớn nhất của tập rỗng" không có đáp án, nên method buộc phải nói ra điều đó — bằng cách throw, bằng cách trả về -1 nếu nó trả về index, hoặc bằng cách từ chối nhận mảng rỗng.

Trả về index của max, không chỉ giá trị

Code thật gần như không bao giờ chỉ cần mỗi giá trị. Nó cần biết phần tử nào thắng, để còn tra ra dòng dữ liệu, cái tên hay cái timestamp tương ứng. Cứ giữ index thì giá trị lấy lại được miễn phí bằng a[best].

public class MaxIndex {
    static int indexOfMax(int[] a) {
        if (a == null || a.length == 0) return -1;
        int best = 0;
        for (int i = 1; i < a.length; i++) {
            if (a[i] > a[best]) best = i;
        }
        return best;
    }

    public static void main(String[] args) {
        String[] days = {"Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"};
        int[] temps = {17, 23, 12, 29, 8, 31, 21};

        int at = indexOfMax(temps);
        System.out.println("index  = " + at);
        System.out.println("hottest: " + days[at] + " at " + temps[at]);

        System.out.println("empty  -> " + indexOfMax(new int[0]));

        int[] ties = {7, 9, 9, 3};
        System.out.println("first of two 9s -> index " + indexOfMax(ties));
    }
}

index  = 5
hottest: Sat at 31
empty  -> -1
first of two 9s -> index 1

Phép so sánh là > chứ không phải >=, nên khi có hai giá trị bằng nhau thì index nhỏ hơn thắng. Đó là một quyết định chứ không phải tai nạn: đổi sang >= thì index lớn hơn sẽ thắng. Hãy chọn một cách có chủ ý và ghi lại, vì "trong hai giá trị max bằng nhau thì bạn muốn cái nào" là một bug report có thật.

Tổng và trung bình: hai cái bẫy trong bốn dòng code

int overflow khi cộng dồn cả mảng

Tính tổng cũng là mẫu running state, chỉ thay so sánh bằng +, nhưng nó có một kiểu hỏng mà phép so sánh không có: biến tích lũy có thể hết bit. Bốn kích thước file, không cái nào gần giới hạn của int, cộng lại thì vượt quá sức chứa của một int.

public class SumOverflow {
    public static void main(String[] args) {
        int[] fileSizes = {900_000_000, 800_000_000, 700_000_000, 600_000_000};

        int badSum = 0;
        for (int i = 0; i < fileSizes.length; i++) badSum += fileSizes[i];

        long goodSum = 0;
        for (int i = 0; i < fileSizes.length; i++) goodSum += fileSizes[i];

        System.out.println("int  sum = " + badSum);
        System.out.println("long sum = " + goodSum);
        System.out.println("Integer.MAX_VALUE = " + Integer.MAX_VALUE);
    }
}

int  sum = -1294967296
long sum = 3000000000
Integer.MAX_VALUE = 2147483647

Không exception, không cảnh báo: phép tính int wrap trong im lặng, nên tổng của bốn số dương lại ra số âm. Khai báo biến tích lũy là long thì hết lỗi, vì mỗi phần tử int được widen lên long trước khi cộng và phép cộng được thực hiện trên 64 bit.

⚠️ long sum = 0; mới là cách sửa. long sum = tongIntDaTinhSan; thì không — widen một giá trị đã wrap rồi chỉ là cất đáp án sai vào một cái hộp to hơn.

Mặc định hãy tích lũy bằng long khi cộng dồn một mảng. Bốn byte thêm vào một variable đơn lẻ không tốn gì cả, mà Long.MAX_VALUE lớn hơn Integer.MAX_VALUE hơn bốn tỉ lần.

Phép chia số nguyên làm cụt giá trị trung bình

Cái bẫy thứ hai nằm ngay dòng sau. Dấu / giữa hai giá trị int là phép chia số nguyên: nó cắt bỏ phần thập phân chứ không làm tròn, và nó cắt trước khi kết quả kịp được gán vào một double.

public class Average {
    public static void main(String[] args) {
        int[] scores = {7, 8, 8, 9, 10};

        int n = scores.length;
        long sum = 0;
        for (int i = 0; i < n; i++) sum += scores[i];

        double wrong = sum / n;
        double right = (double) sum / n;

        System.out.println("sum = " + sum + ", n = " + n);
        System.out.println("sum / n            = " + wrong);
        System.out.println("(double) sum / n   = " + right);
        System.out.printf("rounded to 2dp     = %.2f%n", right);
    }
}

sum = 42, n = 5
sum / n            = 8.0
(double) sum / n   = 8.4
rounded to 2dp     = 8.40

sum / n là 42 / 5, được tính hoàn toàn bằng số nguyên ra 8, rồi mới widen thành 8.0. Khai báo variable là double chẳng thay đổi được gì, vì phép chia đã xảy ra xong rồi. Cast phải nằm ở toán hạng: (double) sum / n đẩy cả expression sang dấu phẩy động và cho ra 8.4.

Mảng rỗng ở đây cũng cần một quyết định, và hai cách viết hỏng theo hai kiểu khác nhau:

(double) sum / n = NaN
Exception in thread "main" java.lang.ArithmeticException: / by zero
	at EmptyAvg.main(EmptyAvg.java:6)

Chia cho 0 trong dấu phẩy động cho ra NaN; chia cho 0 với số nguyên thì throw. Hãy kiểm tra n > 0 trước khi chia.

Đếm và lọc: đếm trước, rồi mới điền

Mảng trong Java có độ dài cố định, nên "giữ lại các phần tử thỏa điều kiện" không thể vừa chạy vừa nới rộng kết quả. Cách làm chuẩn là chạy điều kiện hai lần: một lần để đếm, một lần để copy.

import java.util.Arrays;

public class Filter {
    public static void main(String[] args) {
        int[] scores = {45, 82, 67, 91, 38, 74, 55, 88};
        int pass = 60;

        int count = 0;
        for (int i = 0; i < scores.length; i++) {
            if (scores[i] >= pass) count++;
        }

        int[] passed = new int[count];
        int k = 0;
        for (int i = 0; i < scores.length; i++) {
            if (scores[i] >= pass) passed[k++] = scores[i];
        }

        System.out.println("count  = " + count);
        System.out.println("passed = " + Arrays.toString(passed));
        System.out.println("length = " + passed.length);
    }
}

count  = 5
passed = [82, 67, 91, 74, 88]
length = 5

Mảng kết quả có đúng độ dài cần thiết, nên phía sau không ai phải biết bao nhiêu ô là dữ liệu thật. Điều đó quan trọng vì một int[] bị cấp dư không hề rỗng ở phần đuôi — nó đầy số 0, mà số 0 thì không phân biệt được với dữ liệu:

int[] buffer = new int[scores.length];
int k = 0;
for (int i = 0; i < scores.length; i++) {
    if (scores[i] >= 60) buffer[k++] = scores[i];
}
int[] passed = Arrays.copyOf(buffer, k);

buffer = [82, 67, 91, 74, 88, 0, 0, 0]
passed = [82, 67, 91, 74, 88]

Bản một lượt là lựa chọn tốt hơn khi điều kiện đắt: điền vào một buffer cấp dư, rồi cắt về đúng k. Trong cả hai bản, k làm hai việc cùng lúc — nó là con trỏ ghi khi vòng lặp đang chạy, và là số lượng cuối cùng khi vòng lặp dừng.

Biến đếm k riêng biệt là bắt buộc. Viết passed[i] thay cho passed[k++] sẽ để lại lỗ hổng ở mọi chỗ điều kiện sai, và vỡ ngay khi kết quả nhỏ hơn input.

Đảo ngược mảng tại chỗ

Đảo mảng cần hai index đi ngược chiều về phía nhau, swap dọc đường, và dừng khi chúng gặp nhau.

static void reverse(int[] a) {
    int i = 0, j = a.length - 1;
    while (i < j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
        i++;
        j--;
    }
}

start          [1, 2, 3, 4, 5]
swap 0 <-> 4   [5, 2, 3, 4, 1]
swap 1 <-> 3   [5, 4, 3, 2, 1]
stop: i=2 j=2

Năm phần tử chỉ cần hai lần swap, không phải năm. Phần tử ở giữa của mảng lẻ vốn đã nằm đúng chỗ, và i < j dừng vòng lặp ngay khi hai index gặp nhau.

Cách viết trông có vẻ hiển nhiên hơn là một vòng for chạy qua mọi index, và nó không chạy đúng:

static void reverseWrong(int[] a) {
    int n = a.length;
    for (int i = 0; i < n; i++) {
        int tmp = a[i];
        a[i] = a[n - 1 - i];
        a[n - 1 - i] = tmp;
    }
}

start        [1, 2, 3, 4, 5]
two indices  [5, 4, 3, 2, 1]
full loop    [1, 2, 3, 4, 5]
full loop, even n [1, 2, 3, 4, 5, 6]

Vòng lặp đầy đủ swap mỗi cặp hai lần. Khi i sang tới nửa sau, n - 1 - i trỏ ngược về nửa đầu, và cặp vừa swap xong bị swap trở lại. Mảng quay về đúng thứ tự ban đầu, với cả độ dài lẻ lẫn chẵn — một bug rất dễ nhìn lướt qua, vì code trông cân đối còn output thì trông như chẳng có gì xảy ra.

Cận của vòng lặp mới là chỗ sửa: for (int i = 0; i < n / 2; i++) chỉ ghé mỗi cặp một lần, và tương đương hoàn toàn với bản hai index.

Linear search: trả về index hoặc -1

Linear search duyệt mảng và dừng ở lần khớp đầu tiên. Nó chạy được trên mọi mảng, với mọi thứ tự.

public class LinearSearch {
    static long probes;

    static int indexOf(int[] a, int target) {
        for (int i = 0; i < a.length; i++) {
            probes++;
            if (a[i] == target) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] ids = {104, 217, 355, 402, 519, 663, 771};

        probes = 0;
        System.out.println("find 402 -> index " + indexOf(ids, 402) + ", probes " + probes);
        probes = 0;
        System.out.println("find 104 -> index " + indexOf(ids, 104) + ", probes " + probes);
        probes = 0;
        System.out.println("find 500 -> index " + indexOf(ids, 500) + ", probes " + probes);
    }
}

find 402 -> index 3, probes 4
find 104 -> index 0, probes 1
find 500 -> index -1, probes 7

Counter probes chính là cách đo dùng xuyên suốt bài này: một probe là một lần đọc một phần tử của mảng và so nó với target.

Các con số nói hết về chi phí. Tìm thấy ở index i tốn i + 1 probe, nên tốt nhất là 1 và xấu nhất là n. Lấy trung bình trên cả bảy phần tử của mảng này thì tổng là 28 probe, đúng 4,0 mỗi lần tìm — chính là công thức quen thuộc (n + 1) / 2. Không tìm thấy thì luôn tốn trọn n, vì vòng lặp chỉ có thể kết luận "không có" sau khi đã nhìn hết.

Trả về -1 cho "không tìm thấy" là convention của Java, và nó không tùy tiện: mọi index hợp lệ đều từ 0 trở lên, nên -1 không thể đụng vào một đáp án thật. String.indexOf, List.indexOf và Arrays.binarySearch đều dùng giá trị âm vì cùng lý do đó. Hãy kiểm tra bằng if (at >= 0) thay vì if (at != -1) — thói quen đó vẫn còn đúng khi bạn chuyển sang Arrays.binarySearch, nơi giá trị báo lỗi không phải lúc nào cũng là -1.

Binary search trên mảng đã sort

Binary search vứt đi một nửa khoảng còn lại sau mỗi lần probe. Cái giá phải trả là một điều kiện tiên quyết: mảng phải được sort sẵn.

static int binarySearch(int[] a, int target) {
    int low = 0;
    int high = a.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        probes++;
        if (a[mid] == target) return mid;
        if (a[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

Có ba thứ giữ cho vòng lặp đúng. low <= high — chứ không phải < — vì một khoảng còn đúng một phần tử vẫn là khoảng đáng kiểm tra, bỏ dấu = đi là bỏ sót mọi target rơi vào tình huống đó. mid + 1 và mid - 1 — chứ không phải mid — vì a[mid] vừa bị loại, để nó lại trong khoảng thì vòng lặp quay mãi không dừng. Và low chỉ tăng còn high chỉ giảm, đó là thứ bảo đảm vòng lặp kết thúc.

Trên mảng 15 phần tử trong hình, tìm 78 tốn linear search 11 probe và binary search 4 probe:

binary:
  step 1: low=0 mid=7 high=14  a[mid]=55
  step 2: low=8 mid=11 high=14  a[mid]=84
  step 3: low=8 mid=9 high=10  a[mid]=70
  step 4: low=10 mid=10 high=10  a[mid]=78
binary -> index 10, probes 4

Khoảng cách nới ra rất nhanh. Gắn counter cho cả hai thuật toán trên cùng một mảng đã sort gồm 1000 phần tử, rồi tìm lần lượt từng phần tử:

binary  find 1234 -> index 617, probes 10
linear  find 1234 -> index 617, probes 618

all 1000 hits   linear total 500500, avg 500.5, worst 1000
all 1000 hits   binary total 8987, avg 8.987, worst 10

miss 1235   linear 1000, binary 10

Ít hơn khoảng năm mươi sáu lần về trung bình, và đúng một trăm lần ở trường hợp xấu nhất. Cũng để ý rằng một lần không tìm thấy tốn của binary search đúng 10 probe như khi tìm thấy, trong khi nó tốn của linear search trọn 1000 — đúng cái bất đối xứng làm linear search đau đớn trên dữ liệu mà phần lớn truy vấn đều không khớp.

Cách tính mid an toàn với overflow

int mid = (low + high) / 2; là bản có trong hầu hết sách giáo khoa, và nó sai trên mảng lớn. Phép cộng được tính bằng số học int, nên khi low + high vượt Integer.MAX_VALUE thì nó wrap thành số âm và phép chia cho ra một index âm.

int low = 1_500_000_000;
int high = 2_000_000_000;

System.out.println("(low + high) / 2       = " + ((low + high) / 2));
System.out.println("low + (high - low) / 2 = " + (low + (high - low) / 2));
System.out.println("low + high             = " + (low + high));
System.out.println("Integer.MAX_VALUE      = " + Integer.MAX_VALUE);

(low + high) / 2       = -397483648
low + (high - low) / 2 = 1750000000
low + high             = -794967296
Integer.MAX_VALUE      = 2147483647

Đây đúng là kiểu wrap trong im lặng đã nói ở phần integer overflow trước đó trong series: cộng 1 vào Integer.MAX_VALUE cho ra Integer.MIN_VALUE, và Java không throw cũng không tự nâng lên type rộng hơn. Ở đây tổng bị wrap là -794967296, chia đôi ra một mid âm, và nó thành ArrayIndexOutOfBoundsException ngay khi được dùng làm index.

low + (high - low) / 2 tính ra đúng mid đó mà không bao giờ tạo ra tổng lớn kia. high - low nhiều nhất bằng độ dài mảng nên không thể overflow, và cộng một nửa của nó vào low thì không thể vượt quá high. Chính bug này đã nằm im trong Arrays.binarySearch của chính JDK suốt chín năm, cho tới khi Joshua Bloch viết bài về nó năm 2006. Bản sửa dùng phép dịch bit không dấu thay cho phép chia, và tới JDK 21 nó vẫn còn nguyên: int mid = (low + high) >>> 1;. Cách đó chạy được vì >>> đẩy cái sign bit bị wrap xuống thành một giá trị dương, và nó tương đương / 2 với mọi tổng không âm.

Một int[] phải có hơn một tỉ phần tử thì lỗi này mới kích hoạt, nên có thể cả đời bạn không gặp. Cứ viết bản an toàn đi — số ký tự y hệt nhau.

Arrays.binarySearch trả về gì khi không tìm thấy

JDK có sẵn binary search cho mọi kiểu mảng primitive, nên bạn không cần tự viết. Hành vi khi tìm thấy thì không có gì bất ngờ; hành vi khi không tìm thấy mới là phần đáng học.

import java.util.Arrays;

public class ArraysBinary {
    public static void main(String[] args) {
        int[] a = {3, 8, 12, 17, 23, 31, 42, 55, 61, 70, 78, 84, 90, 95, 99};

        System.out.println("find 78 -> " + Arrays.binarySearch(a, 78));

        int r = Arrays.binarySearch(a, 79);
        System.out.println("find 79 -> " + r);
        System.out.println("insertion point = " + (-r - 1));
        System.out.println("would sit before a[" + (-r - 1) + "] = " + a[-r - 1]);

        System.out.println("find 1   -> " + Arrays.binarySearch(a, 1)
                + "  insertion point " + (-Arrays.binarySearch(a, 1) - 1));
        System.out.println("find 200 -> " + Arrays.binarySearch(a, 200)
                + " insertion point " + (-Arrays.binarySearch(a, 200) - 1));
    }
}

find 78 -> 10
find 79 -> -12
insertion point = 11
would sit before a[11] = 84
find 1   -> -1  insertion point 0
find 200 -> -16 insertion point 15

Khi không tìm thấy, method trả về -(insertion point) - 1, trong đó insertion point là index mà giá trị đó sẽ chiếm nếu bạn chèn nó vào và giữ mảng vẫn sort. Lấy lại nó bằng -r - 1. Với 79 thì đó là 11, đúng chỗ của 79: sau 78 ở index 10 và trước 84 ở index 11.

Số - 1 trong công thức tồn tại để mọi lần không tìm thấy đều ra số âm. Không có nó, một giá trị thuộc về đầu mảng sẽ cho insertion point là 0, mà 0 lại là một index hoàn toàn hợp lệ và không phân biệt được với việc tìm thấy ở index 0. Hãy để ý hệ quả trong output trên: Arrays.binarySearch(a, 1) trả về -1, và điều đó nghĩa là "không có, chèn vào vị trí 0" chứ không phải convention tự viết "không tìm thấy, hết chuyện". Luôn kiểm tra bằng r >= 0.

Giá trị âm đó thật sự hữu ích. Nó là cách để làm "tìm giá trị gần nhất", "chèn vào mà vẫn giữ thứ tự sort" hoặc "giá trị này rơi vào khoảng nào" mà không cần quét thêm lần nữa.

Binary search trên mảng chưa sort là undefined

Javadoc nói kết quả là undefined nếu mảng chưa được sort, và "undefined" ở đây không có nghĩa là "một exception". Nó có nghĩa là một đáp án sai được trả về đầy tự tin.

import java.util.Arrays;

public class UnsortedBinary {
    public static void main(String[] args) {
        int[] a = {42, 8, 99, 17, 3, 61, 23};

        System.out.println("array       = " + Arrays.toString(a));
        System.out.println("contains 99 at index 2");
        System.out.println("binarySearch(a, 99) = " + Arrays.binarySearch(a, 99));
        System.out.println("binarySearch(a, 8)  = " + Arrays.binarySearch(a, 8));
        System.out.println("binarySearch(a, 17) = " + Arrays.binarySearch(a, 17));
        System.out.println("binarySearch(a, 3)  = " + Arrays.binarySearch(a, 3));
    }
}

array       = [42, 8, 99, 17, 3, 61, 23]
contains 99 at index 2
binarySearch(a, 99) = -8
binarySearch(a, 8)  = 1
binarySearch(a, 17) = 3
binarySearch(a, 3)  = -1

99 đang nằm ở index 2 mà method báo -8: không có, chèn vào cuối. Trong khi đó 8 và 17 lại được tìm thấy chính xác, thuần túy nhờ may mắn về chỗ các lần probe rơi vào. Không có gì hỏng ầm ĩ cả. Cái mớ lẫn lộn đúng-sai đó là kiểu hỏng tệ nhất có thể, vì nó sống sót qua một lần test qua loa.

Sort trước, rồi mới search. Cả hai việc đều gọn một dòng:

int[] ids = {771, 104, 519, 217, 663, 355, 402};
Arrays.sort(ids);
System.out.println("sorted " + Arrays.toString(ids));
int r = Arrays.binarySearch(ids, 519);
System.out.println("519 -> " + r + ", found = " + (r >= 0));
int m = Arrays.binarySearch(ids, 500);
System.out.println("500 -> " + m + ", found = " + (m >= 0));

sorted [104, 217, 355, 402, 519, 663, 771]
519 -> 4, found = true
500 -> -5, found = false

Sort tốn hơn một lần linear search, nên đánh đổi này chỉ có lời khi bạn tìm trên cùng mảng đó nhiều lần. Một lần tra: cứ quét. Hàng nghìn lần tra: sort một lần, rồi binary search.

Bubble sort và early exit

Bubble sort so từng cặp kề nhau và swap nếu chúng sai thứ tự. Sau một lượt đầy đủ, phần tử lớn nhất đã được đẩy về cuối, nên mỗi lượt sau có thể dừng sớm hơn một vị trí.

import java.util.Arrays;

public class BubbleSort {
    static void bubbleSort(int[] a) {
        int n = a.length;
        for (int pass = 0; pass < n - 1; pass++) {
            boolean swapped = false;
            for (int i = 0; i < n - 1 - pass; i++) {
                if (a[i] > a[i + 1]) {
                    int t = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = t;
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }

    public static void main(String[] args) {
        int[] a = {5, 1, 4, 2, 8};
        bubbleSort(a);
        System.out.println(Arrays.toString(a));
    }
}

[1, 2, 4, 5, 8]

Trace từng lần swap trên mảng năm phần tử đó:

start           [5, 1, 4, 2, 8]
  pass 1 swap (0,1) -> [1, 5, 4, 2, 8]
  pass 1 swap (1,2) -> [1, 4, 5, 2, 8]
  pass 1 swap (2,3) -> [1, 4, 2, 5, 8]
after pass 1   [1, 4, 2, 5, 8]   swapped=true
  pass 2 swap (1,2) -> [1, 2, 4, 5, 8]
after pass 2   [1, 2, 4, 5, 8]   swapped=true
after pass 3   [1, 2, 4, 5, 8]   swapped=false
no swaps in pass 3 -> already sorted, stop
sorted          [1, 2, 4, 5, 8]

Cờ swapped chính là early exit. Một pass không swap gì chứng minh không còn cặp kề nhau nào sai thứ tự, mà với một thứ tự tuyến tính thì điều đó nghĩa là cả mảng đã sort, nên các pass còn lại chắc chắn là công cốc. Pass 3 ở trên chính là pass đó.

Gắn counter cho cả hai bản, n = 1000, bốn dạng input khác nhau:

Early exit biến một mảng đã sort sẵn từ 499.500 comparison xuống còn 999 — đúng một pass xác nhận. Trên dữ liệu ngẫu nhiên nó gần như không tiết kiệm được gì, vì mảng ngẫu nhiên dù sao cũng cần gần hết số pass. Đó là kết luận trung thực: cái cờ đó tốn một boolean và có lời trên dữ liệu vốn đã gần sort.

499.500 không phải trùng hợp. Nó là n(n-1)/2 với n = 1000, tổng số lần so cặp kề nhau qua toàn bộ n - 1 pass, và đó chính là chỗ nhãn O(n²) sinh ra. Input gấp mười lần thì số comparison gấp một trăm lần.

Selection sort và insertion sort

Hai thuật toán sort kinh điển còn lại cùng một lớp độ phức tạp nhưng hành xử rất khác nhau ở phần hằng số.

Selection sort: ít swap hơn, số comparison không đổi

Selection sort quét phần chưa sort để tìm phần tử nhỏ nhất rồi swap nó vào đúng chỗ — mỗi pass đúng một lần swap, tổng cộng nhiều nhất n - 1 lần.

static void selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[min]) min = j;
        }
        if (min != i) {
            int t = a[i]; a[i] = a[min]; a[min] = t;
        }
    }
}

selection sort, start [5, 1, 4, 2, 8]
  swap a[0] <-> a[1] -> [1, 5, 4, 2, 8]
  swap a[1] <-> a[3] -> [1, 2, 4, 5, 8]
sorted [1, 2, 4, 5, 8]

Hai lần swap là đủ sort năm phần tử đó, so với bốn lần của bubble sort. Nhưng số comparison thì không hề nhúc nhích: selection sort luôn thực hiện đúng n(n-1)/2 lần so, vì vòng quét bên trong không thể dừng sớm — nó phải nhìn hết phần còn lại mới biết cái nào nhỏ nhất. Trên cả bốn input với n = 1000, con số đo được đều là 499.500, giống hệt nhau mọi lần, trong khi số swap dao động từ 0 tới 991.

Cái hồ sơ đó làm selection sort thú vị đúng trong một tình huống: khi việc di chuyển một phần tử đắt hơn nhiều so với việc so hai phần tử, và bạn muốn chặn trên số lần di chuyển.

Insertion sort: nhanh trên dữ liệu gần như đã sort

Insertion sort lấy từng phần tử và đẩy nó sang trái qua mọi phần tử lớn hơn, giống như xếp một cỗ bài trên tay.

static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; 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;
    }
}

insertion sort, start [5, 1, 4, 2, 8]
  key 1 placed -> [1, 5, 4, 2, 8]
  key 4 placed -> [1, 4, 5, 2, 8]
  key 2 placed -> [1, 2, 4, 5, 8]
  key 8 placed -> [1, 2, 4, 5, 8]
sorted [1, 2, 4, 5, 8]

Điều kiện của while nói lên tất cả: a[j] > key dừng ngay khi phần tử bên trái đã nhỏ hơn. Trên dữ liệu gần sort, chuyện đó xảy ra gần như tức thì.

Đo trên cùng bốn input với n = 1000, cột "move" đếm mỗi lần một phần tử bị đẩy sang phải một ô:

Cột "gần như đã sort" mới là điểm mấu chốt: một mảng 1000 phần tử đã sort rồi bị hoán vị ngẫu nhiên mười cặp tốn của insertion sort 5.781 comparison, so với 499.500 của selection sort — ít hơn khoảng tám mươi sáu lần. Insertion sort là O(n²) ở trường hợp xấu nhất và O(n) ở trường hợp tốt nhất, mà dữ liệu thật thì rất hay ở trạng thái gần sort.

Có hai dòng trong bảng đó giống hệt nhau, và không phải ngẫu nhiên. Số swap của bubble sort và số move của insertion sort đều đúng bằng số inversion — số cặp phần tử đang sai thứ tự tương đối. Cả hai thuật toán chỉ bao giờ đẩy một phần tử vượt qua một phần tử đáng lẽ phải đứng sau nó, nên cả hai buộc phải làm đúng chừng đó việc: 249.861 trên input ngẫu nhiên, 4.782 trên input gần sort.

Arrays.sort: thứ bạn nên dùng thật sự

Không có thứ nào ở trên là thứ bạn đem lên production. java.util.Arrays.sort gọn một dòng, được test kỹ hơn bất cứ thứ gì bạn tự viết, và nó không phải O(n²).

int[] a = {5, 1, 4, 2, 8};
Arrays.sort(a);
System.out.println(Arrays.toString(a));

[1, 2, 4, 5, 8]

Nó sort tại chỗ, tăng dần, và trả về void — một lỗi hay gặp là viết int[] b = Arrays.sort(a);, câu này không compile được.

SortVoid.java:5: error: incompatible types: void cannot be converted to int[]
        int[] b = Arrays.sort(a);
                             ^
1 error

Thuật toán nào chạy là tùy theo element type, và source của JDK 21 nói rõ cả hai. Các overload cho primitive gọi DualPivotQuicksort.sort, javadoc của chúng ghi: "The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch." Overload cho Object[] gọi ComparableTimSort.sort, javadoc ghi: "This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort."

Stable nghĩa là các phần tử bằng nhau giữ nguyên thứ tự tương đối vốn có. Sort primitive thì không stable, còn sort object thì có. Nghe như một cái bẫy, nhưng không phải — và lý do đáng được nói cho chính xác.

Với một int[], hai phần tử bằng nhau nghĩa là đúng một giá trị. Không có thuộc tính nào của số 5 phân biệt nó với một số 5 khác, nên không chương trình nào quan sát được là chúng có bị đảo chỗ hay không. Ở đó, tính không stable là không quan sát được ngay từ trong bản chất.

Với object thì quan sát được, vì hai phần tử có thể bằng nhau ở key đang sort mà khác nhau ở mọi thứ còn lại. Đó chính là thứ mà stable mang lại: sort theo một key, rồi sort theo key khác, và thứ tự lần đầu vẫn còn nguyên bên trong từng nhóm bằng nhau. Cái Integer cache đã nói trước đó trong series giúp nhìn thấy hiệu ứng này mà không cần viết class riêng — Integer.valueOf(1000) trả về một object mới mỗi lần gọi, nên hai Integer bằng nhau vẫn phân biệt được bằng ==:

import java.util.Arrays;

public class Stability {
    public static void main(String[] args) {
        Integer first  = Integer.valueOf(1000);
        Integer second = Integer.valueOf(1000);
        System.out.println("two distinct objects, equal value: first == second -> " + (first == second));

        Integer[] boxed = { second, first, Integer.valueOf(7) };
        System.out.println("before: boxed[0] == second -> " + (boxed[0] == second));
        Arrays.sort(boxed);
        System.out.println("after : " + Arrays.toString(boxed));
        System.out.println("after : boxed[1] == second -> " + (boxed[1] == second));
        System.out.println("after : boxed[2] == first  -> " + (boxed[2] == first));
    }
}

two distinct objects, equal value: first == second -> false
before: boxed[0] == second -> true
after : [7, 1000, 1000]
after : boxed[1] == second -> true
after : boxed[2] == first  -> true

second đứng trước first lúc đầu và vẫn đứng trước nó lúc sau. Hai phần tử so ra bằng nhau đã không bị đảo chỗ — đó là tính stable, quan sát được bằng mắt. Còn sort object theo một key do bạn chọn thay vì theo thứ tự tự nhiên thì cần Comparable và Comparator, hai thứ thuộc về khóa nâng cao.

Con số đo được mới là lý do để dùng thư viện. Đếm số comparison mà Arrays.sort thực sự thực hiện với n = 1000, trên đúng bốn input và đúng các seed như bảng trên:

Ít hơn khoảng hai mươi chín lần trên dữ liệu ngẫu nhiên, và đúng năm trăm lần trên mảng sort ngược — TimSort nhận ra dãy giảm dần và đảo nó trong một lượt, thay vì xáo đi xáo lại 499.500 cặp. Các con số đó có được nhờ cho phép so sánh đi qua một counter; cơ chế để làm việc đó là Comparable, thứ mà một khóa sau sẽ nói tới.

Sort một đoạn, và sort một bản copy

Arrays.sort(a, from, to) sort một lát cắt. from là bao gồm còn to là loại trừ, đúng convention dùng ở mọi chỗ khác trong JDK.

int[] b = {9, 7, 5, 3, 1, 8, 6};
Arrays.sort(b, 1, 4);
System.out.println(Arrays.toString(b));

[9, 3, 5, 7, 1, 8, 6]

Index 1, 2 và 3 — tức các giá trị 7, 5, 3 — thành 3, 5, 7. Index 0 và các index từ 4 trở đi không bị đụng tới.

Vì Arrays.sort sửa thẳng vào tham số của nó, sort là phá luôn thứ tự gốc. Khi cần giữ cả hai, hãy sort một bản copy:

int[] original = {5, 1, 4, 2, 8};
int[] copy = Arrays.copyOf(original, original.length);
Arrays.sort(copy);
System.out.println("original    " + Arrays.toString(original));
System.out.println("sorted copy " + Arrays.toString(copy));

original    [5, 1, 4, 2, 8]
sorted copy [1, 2, 4, 5, 8]

Chuyện này quan trọng hơn vẻ ngoài của nó. Nếu mảng được truyền vào như một parameter của method, sort tại chỗ sẽ làm thay đổi mảng của phía gọi, vì parameter giữ reference tới đúng object đó.

Bảng độ phức tạp

Big-O mô tả chi phí tăng theo n như thế nào, và các counter ở trên chính là hình ảnh của mức tăng đó tại n = 1000.

Hãy đọc hai dòng giữa cùng nhau. log₂(1000) xấp xỉ 9,97, và binary search đo được trung bình 8,987 probe với xấu nhất là 10 — lý thuyết và counter khớp nhau. Đọc hai dòng cuối cùng nhau thì khác biệt giữa O(n²) và O(n log n) hết trừu tượng: 250.858 so với 8.688 trên cùng một dữ liệu.

Bài học còn lại là hằng số vẫn quan trọng bên trong cùng một lớp độ phức tạp. Bubble, selection và insertion sort đều là O(n²), vậy mà trên dữ liệu gần sort, insertion sort làm 5.781 comparison còn selection sort làm 499.500.

Những lỗi thường gặp khi làm việc với mảng

Binary search trên mảng chưa sort. Đã chứng minh ở trên: Arrays.binarySearch báo -8 cho một giá trị đang nằm ở index 2. Không exception, chỉ là một đáp án sai trộn lẫn giữa những đáp án đúng.

Khởi tạo max bằng 0 hoặc min bằng 0. Chạy đúng trên dữ liệu test, hỏng ngay ở mảng toàn số âm đầu tiên. Hãy khởi tạo từ a[0] và xử lý mảng rỗng riêng.

Overflow ở chỗ tính mid và ở chỗ cộng tổng. (low + high) / 2 wrap thành số âm trên mảng khổng lồ; biến tích lũy int wrap thành số âm với giá trị lớn. Hãy viết low + (high - low) / 2 và long sum = 0.

Sửa mảng trong lúc đang lặp qua index của nó. Xóa một phần tử bằng cách dồn phần đuôi sang trái sẽ kéo phần tử kế tiếp vào đúng ô vừa xử lý xong, và i++ của vòng lặp bước qua luôn nó:

int[] a = {4, 0, 0, 7, 3};
int n = a.length;

for (int i = 0; i < n; i++) {
    if (a[i] == 0) {
        for (int j = i; j < n - 1; j++) a[j] = a[j + 1];
        n--;
        System.out.println("removed at " + i + " -> " + Arrays.toString(a) + "  n=" + n);
    }
}
System.out.println("result " + Arrays.toString(Arrays.copyOf(a, n)));

removed at 1 -> [4, 0, 7, 3, 3]  n=4
result [4, 0, 7, 3]

Hai số 0 đi vào mà chỉ một số 0 đi ra. Sau khi dồn, index 1 giữ số 0 thứ hai, nhưng i đã sang 2 rồi. Cách nén bằng hai index không dính lỗi đó, vì con trỏ đọc và con trỏ ghi là hai variable riêng:

int[] a = {4, 0, 0, 7, 3};
int k = 0;
for (int i = 0; i < a.length; i++) {
    if (a[i] != 0) a[k++] = a[i];
}
System.out.println("result " + Arrays.toString(Arrays.copyOf(a, k)));

result [4, 7, 3]

Đảo mảng bằng vòng lặp chạy qua mọi index. Nó swap mỗi cặp hai lần và trả lại đúng mảng ban đầu. Hãy dừng ở n / 2.

Tự viết sort cho code production. Arrays.sort đo được 8.688 comparison ở chỗ insertion sort đo được 250.858, và nó đã được test kỹ hơn bản của bạn rất nhiều.

FAQ

Làm sao tìm giá trị lớn nhất trong mảng Java?

Khởi tạo một variable từ a[0], lặp từ index 1, và thay giá trị đó mỗi khi gặp phần tử lớn hơn. Đừng bao giờ khởi tạo bằng 0 — trên mảng toàn số âm thì if không chạy lần nào và bạn nhận về 0, một giá trị không có trong mảng. Hãy xử lý mảng rỗng riêng vì a[0] không tồn tại ở đó, và nên cân nhắc trả về index thay vì giá trị: a[best] cho lại giá trị, còn chỉ mỗi giá trị thì không nói được phần tử nào đã thắng.

Vì sao giá trị trung bình của tôi ra số nguyên?

Vì / giữa hai giá trị int là phép chia số nguyên và nó cắt phần thập phân trước khi bất kỳ phép chuyển đổi nào xảy ra. sum / n với sum = 42 và n = 5 ra 8, và gán cái đó vào một double chỉ lưu được 8.0. Hãy cast một toán hạng: (double) sum / n cho 8.4. Tiện thể hãy tích lũy tổng bằng long để nó không âm thầm overflow.

Vì sao Arrays.binarySearch trả về số âm?

Giá trị âm nghĩa là không tìm thấy, và con số đó mã hóa luôn chỗ mà giá trị sẽ nằm: kết quả trả về là -(insertion point) - 1, nên -r - 1 lấy lại insertion point. Số - 1 có mặt để một giá trị thuộc về đầu mảng cho ra -1 chứ không phải 0, vì 0 sẽ không phân biệt được với việc tìm thấy ở index 0. Hãy kiểm tra bằng r >= 0, đừng bao giờ dùng r != -1.

Nên dùng thuật toán sort nào trong Java?

Arrays.sort. Nó là dual-pivot quicksort cho mảng primitive và TimSort cho mảng object, cả hai đều O(n log n), và trên mảng ngẫu nhiên 1000 phần tử nó thực hiện 8.688 comparison so với 250.858 của insertion sort. Hãy tự viết bubble, selection hay insertion sort để hiểu sort tốn gì, rồi dùng thư viện.

Bubble sort có bao giờ là lựa chọn đúng không?

Không, không phải trong production. Điểm mạnh thật sự duy nhất của nó là bản có cờ early exit nhận ra mảng đã sort chỉ trong một pass — 999 comparison với n = 1000 — nhưng insertion sort cũng làm được đúng vậy và tốt hơn hẳn ở mọi thứ còn lại: 250.858 comparison so với 497.730 của bubble sort trên dữ liệu ngẫu nhiên, với số lần di chuyển y hệt nhau. Bubble sort tồn tại vì nó dễ giải thích, không phải vì nó tốt.

Làm sao sort mảng mà không làm thay đổi mảng gốc?

Copy trước rồi sort bản copy: int[] copy = Arrays.copyOf(original, original.length); Arrays.sort(copy);. Arrays.sort sửa thẳng vào mảng được truyền vào và trả về void, nên không có overload nào không phá dữ liệu. Điều này quan trọng nhất khi mảng đi vào như một parameter của method — sort tại chỗ là sắp xếp lại dữ liệu của phía gọi, chuyện mà phía gọi hiếm khi mong đợi.

Kết luận

Các thuật toán trong bài này dùng chung một bộ khung: một vòng lặp qua index mang theo một chút state. Thứ tách code chạy được khỏi code hỏng trên dữ liệu thật nằm hết ở xung quanh vòng lặp — khởi tạo state từ chính mảng chứ không từ một literal, tích lũy bằng type đủ rộng để chứa đáp án, cast trước khi chia chứ không phải sau, và hiểu rằng tốc độ của binary search được mua bằng một điều kiện tiên quyết mà nó sẽ không tự kiểm tra giúp bạn.

Nửa còn lại là phép đo. Counter chứ không phải đồng hồ bấm giờ: 500,5 probe so với 8,987 cho hai cách tìm kiếm, 250.858 comparison so với 8.688 cho hai cách sort. Những con số đó giống nhau trên mọi máy, và chúng chính là ý nghĩa thực tế của O(n), O(log n), O(n²) và O(n log n). Hãy viết các thuật toán sort đơn giản một lần để thấy các con số từ đâu ra, rồi gọi Arrays.sort.

Bài tiếp theo trong series: String, StringBuilder và StringBuffer — vì sao nối chuỗi trong vòng lặp lại chậm, StringBuilder làm khác chỗ nào, StringBuffer còn chỗ đứng ở đâu, và chọn giữa ba thứ đó thế nào.