Sắp xếp: selection sort và insertion sort
Sắp xếp một mảng
- Sắp xếp nghĩa là đặt các giá trị của mảng theo thứ tự, thông thường là từ nhỏ đến lớn.
- Trong kỳ thi AP CSA, bạn phải biết viết và vẽ sơ đồ (trace) hai kiểu sắp xếp: sắp xếp theo lựa chọn (selection sort) và sắp xếp chèn (insertion sort).
- Bạn cũng cần vẽ sơ đồ (nhưng không cần viết) một kiểu sắp xếp thứ ba: sắp xếp gộp (merge sort). Chúng ta xem xét cả ba ở đây.
Sắp xếp theo lựa chọn: ý tưởng
- Duyệt qua mảng từ trái sang phải.
- Tại mỗi vị trí
i, tìm giá trị nhỏ nhất trong phần chưa được sắp xếp (từiđến cuối). - Hoán đổi giá trị nhỏ nhất đó vào vị trí
i. Lúc này0..iđã được sắp xếp. - Lặp lại cho đến khi toàn bộ mảng được sắp xếp.
public class Sorter {
public static void selectionSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = i; // index of smallest so far
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j; // found a smaller value
}
}
int temp = a[min]; // swap a[i] and a[min]
a[min] = a[i];
a[i] = temp;
}
}
}
Sắp xếp theo lựa chọn: vẽ sơ đồ
- Hãy sắp xếp
{5, 2, 4, 1, 3}. Phần nằm bên trái|đã được sắp xếp rồi. - Mỗi lượt sẽ chọn giá trị nhỏ nhất từ phần còn lại và hoán đổi nó lên đầu.
start: [5, 2, 4, 1, 3]
i=0 smallest=1 → swap a[0],a[3]: [1 | 2, 4, 5, 3]
i=1 smallest is already 2 → no move: [1, 2 | 4, 5, 3]
i=2 smallest=3 → swap a[2],a[4]: [1, 2, 3 | 5, 4]
i=3 smallest=4 → swap a[3],a[4]: [1, 2, 3, 4 | 5]
done: [1, 2, 3, 4, 5]
Sắp xếp chèn: ý tưởng
- Hãy tưởng tượng như đang cầm bài, thêm từng lá bài vào đúng vị trí.
- Bắt đầu từ chỉ số
1. Gọi giá trị này là khóa (key). - Trượt các giá trị lớn hơn ở trái một bước sang phải, cho đến khi khóa vừa khít.
- Đặt khóa vào chỗ trống. Bây giờ everything bên trái đã được sắp xếp.
public class Sorter {
public static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i]; // the value to place
int j = i - 1;
while (j >= 0 && a[j] > key) { // shift bigger values right
a[j + 1] = a[j];
j = j - 1;
}
a[j + 1] = key; // drop key into the gap
}
}
}
Sắp xếp chèn: vẽ sơ đồ
- Sắp xếp lại
{5, 2, 4, 1, 3}. Phần nằm bên trái|vẫn giữ nguyên thứ tự khi chúng ta di chuyển. keychính là giá trị mà chúng ta đang chèn vào trong mỗi lần lặp.
start: [5, 2, 4, 1, 3]
i=1 key=2 → shift 5 right, place 2: [2, 5 | 4, 1, 3]
i=2 key=4 → shift 5 right, place 4: [2, 4, 5 | 1, 3]
i=3 key=1 → shift 5,4,2 right, place 1: [1, 2, 4, 5 | 3]
i=4 key=3 → shift 5,4 right, place 3: [1, 2, 3, 4, 5]
done: [1, 2, 3, 4, 5]
Sắp xếp gộp: chỉ vẽ sơ đồ
- Sắp xếp gộp sử dụng đệ quy (bài 15). Bạn không viết nó trong kỳ thi, nhưng bắt buộc phải vẽ sơ đồ (trace).
- Chia đôi mảng ra nhiều lần, cho đến khi mỗi mảnh chỉ còn một giá trị.
- Gộp từng cặp mảnh lại với nhau, luôn đảm bảo thứ tự.
Sắp xếp gộp: vẽ sơ đồ
- Một giá trị đã được coi là "đã sắp xếp". Gộp hai mảnh đã sắp xếp sẽ tạo thành một mảnh lớn hơn đã được sắp xếp.
split: [5, 2, 4, 1]
[5, 2] [4, 1]
[5] [2] [4] [1]
merge: [2, 5] [1, 4]
merge: [1, 2, 4, 5]
- Sắp xếp theo lựa chọn và sắp xếp chèn khá chậm trên mảng lớn (chúng thực hiện khoảng n² bước).
- Sắp xếp gộp nhanh hơn trên mảng lớn (khoảng n·log n bước). Đó là lý do tại sao nó quan trọng.
Lỗi thường gặp
- Cả sắp xếp theo lựa chọn và sắp xếp chèn đều có độ phức tạp O(n²).
- Vẽ sơ đồ một mảng nhỏ bằng tay để kiểm tra thuật toán sắp xếp của bạn.
Bây giờ bạn thử
- Mỗi bài tập cung cấp cho bạn một khung phương thức (method skeleton) với TODO. Sắp xếp mảng ngay tại chỗ (thay đổi trực tiếp
a). - Một Harness ẩn sẽ sắp xếp nhiều mảng và kiểm tra kết quả.
- Sử dụng Check answer để biên dịch mã của bạn với các bài kiểm tra được cung cấp và xem kết quả. Giữ nguyên giao diện class và phương thức được hiển thị trong file khởi tạo.
Selection / Insertion sort
Sắp xếp so sánh và hoán đổi cho đến khi danh sách được sắp xếp theo thứ tự.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Hoàn thiện selectionSort(int[] a) sao cho nó sắp xếp mảng trực tiếp từ nhỏ đến lớn, sử dụng selection sort. Bộ kiểm tra sẽ thử nghiệm với nhiều mảng khác nhau.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Hoàn thiện insertionSort(int[] a) sao cho nó sắp xếp mảng trực tiếp từ nhỏ đến lớn, sử dụng insertion sort. Bộ kiểm tra sẽ thử nghiệm với nhiều mảng khác nhau.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Hoàn thiện isSorted(int[] a) trả về true nếu mảng đang trong thứ tự tăng dần (mỗi phần tử nhỏ hơn <= phần tử tiếp theo), ngược lại trả về false. Mảng rỗng hoặc có một phần tử coi như đã sắp xếp.
Nhấn Chạy để xem kết quả ở đây.