Sorting: selection and insertion sort · Sắp xếp: selection sort và insertion sort
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · Trang này cần trình duyệt gần đây (hỗ trợ SharedArrayBuffer). Vui lòng cập nhật Chrome, Edge, Firefox hoặc Safari lên phiên bản mới nhất.
English
Putting an array in order
- Sorting means putting the values of an array in order, usually from small to large.
- On the AP CSA exam you must be able to write and trace two sorts: selection sort and insertion sort.
- You also need to trace (but not write) a third sort: merge sort. We look at all three here.
Tiếng Việt
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.
English
Selection sort: the idea
- Walk through the array from left to right.
- At each spot
i, find the smallest value in the part that is still unsorted (fromito the end). - Swap that smallest value into spot
i. Now0..iis sorted. - Repeat until the whole array is in order.
Tiếng Việt
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;
}
}
}
English
Selection sort: a trace
- Let us sort
{5, 2, 4, 1, 3}. The bold part is already sorted. - Each pass picks the smallest value from the rest and swaps it to the front.
Tiếng Việt
Sắp xếp theo lựa chọn: vẽ sơ đồ
- Hãy sắp xếp
{5, 2, 4, 1, 3}. Phần in đậm đã được sắp xếp sẵn. - 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]
English
Insertion sort: the idea
- Think of holding playing cards and adding one card at a time into the right place.
- Start at index
1. Call this value the key. - Slide bigger values on the left one step to the right, until the key fits.
- Drop the key into the gap. Now everything to the left is sorted.
Tiếng Việt
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
}
}
}
English
Insertion sort: a trace
- Sort
{5, 2, 4, 1, 3}again. The bold part stays sorted as we go. - The
keyis the value we are inserting on each pass.
Tiếng Việt
Sắp xếp chèn: vẽ sơ đồ
- Sắp xếp lại
{5, 2, 4, 1, 3}. Phần in đậm vẫn giữ nguyên thứ tự khi 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]
English
Merge sort: trace only
- Merge sort uses recursion (lesson 15). You do not write it on the exam, but you must trace it.
- Split the array in half again and again, until each piece has one value.
- Merge pairs of pieces back together, always keeping them in order.
Tiếng Việt
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ự.
English
Merge sort: a trace
- One value is already "sorted". Merging two sorted pieces gives a bigger sorted piece.
- Selection and insertion sort are slow on big arrays (they do about n² steps).
- Merge sort is faster on big arrays (about n·log n steps). That is why it matters.
Tiếng Việ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.
English
Common mistakes
- Selection and insertion sort are both O(n²).
- Trace a small array by hand to check your sort.
Tiếng Việt
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.
English
Now you try
- Each task gives you a method skeleton with a TODO. Sort the array in place (change
aitself). - A hidden Harness sorts several arrays and checks the result.
- Press Run to compile, then Check answer.
Tiếng Việt
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ả.
- Nhấn Run để biên dịch, sau đó nhấn Check answer.
Explore · Khám phá
Selection / insertion sort · Selection / Insertion sort
Sorting compares and swaps until the list is ordered. · 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ự.
Complete selectionSort(int[] a) so it sorts the array in place from small to large, using selection sort. The checker tests several arrays. · 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.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Complete insertionSort(int[] a) so it sorts the array in place from small to large, using insertion sort. The checker tests several arrays. · 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.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Complete isSorted(int[] a) returning true if the array is in order from small to large (each item is <= the next), else false. An empty or one-item array counts as sorted. · 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.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.