Sorting: bubble, selection, and insertion · Sắp xếp: bubble, selection, và insertion
Putting an array in order
- Sorting rearranges an array so the items go from smallest to largest.
- We sort in place: we move items around inside the same array, with no return value.
- Three classic methods do this: bubble, insertion, and selection sort.
Sắp xếp một mảng
- Sắp xếp sắp xếp lại một mảng sao cho các phần tử đi từ nhỏ đến lớn.
- Chúng ta sắp xếp ngay tại chỗ: di chuyển các phần tử xung quanh bên trong cùng một mảng, mà không có giá trị trả về.
- Ba phương pháp cổ điển thực hiện việc này: sắp xếp bọt, sắp xếp chèn và sắp xếp lựa chọn.
Swapping two elements
- Every sort needs to swap two items. Save one in a temporary, then overwrite.
int t = a[i]; a[i] = a[j]; a[j] = t;exchanges positionsiandj.- Forgetting the temporary loses one of the values — always keep it.
hoán đổi hai phần tử
- Mọi thuật toán sắp xếp đều cần hoán đổi hai phần tử. Lưu một phần vào biến tạm thời, sau đó ghi đè lên.
int t = a[i]; a[i] = a[j]; a[j] = t;hoán đổi vị tríivàj.- Quên biến tạm thời sẽ mất một trong hai giá trị — luôn phải giữ nó lại.
Bubble sort
- Go through the array and compare each pair of neighbours:
a[j]anda[j + 1]. - If they are in the wrong order, swap them. The biggest value "bubbles" to the end.
- Repeat the passes until the whole array is in order.
Sắp xếp nổi bọt
- Duyệt qua mảng và so sánh từng cặp kẻ cạnh nhau:
a[j]vàa[j + 1]. - Nếu chúng đang ở thứ tự sai, hãy hoán đổi chúng. Giá trị lớn nhất sẽ "nổi bọt" lên cuối mảng.
- Lặp lại các lượt duyệt cho đến khi toàn bộ mảng được sắp xếp theo thứ tự.
Insertion sort
- Treat the left part of the array as already sorted, and grow it one item at a time.
- Take the next item as a key, shift bigger sorted items to the right, then drop the key into the gap.
- This is how many people sort playing cards in their hand.
Sắp xếp chèn
- Coi phần bên trái của mảng là đã được sắp xếp, và mở rộng nó thêm một phần tử mỗi lần.
- Lấy phần tử tiếp theo làm khóa (key), đẩy các phần tử đã sắp xếp lớn hơn sang phải, sau đó thả khóa vào khoảng trống.
- Đây chính là cách nhiều người sắp xếp bài trên tay.
#include <stdio.h>
int main(void) {
int a[] = {3, 1, 2};
// one bubble pass: compare neighbours and swap if out of order
for (int j = 0; j < 2; j++) {
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
printf("%d %d %d\n", a[0], a[1], a[2]); // 1 2 3
return 0;
}
Common mistakes
- Bubble, selection and insertion sort are all O(n²).
- Trace a small array by hand to check your sort.
Lỗi thường gặp
- Sắp xếp bọt, lựa chọn và 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.
Now you try
- Sort ascending (smallest first), in place, with no return value.
- The checker tries several arrays, including negatives and an already-sorted one.
- Do not write a
main— the checker provides one.
Bây giờ bạn thử
- Sắp xếp tăng dần (nhỏ trước), ngay tại chỗ, không có giá trị trả về.
- Trình kiểm tra thử nghiệm với nhiều mảng khác nhau, bao gồm cả số âm và mảng đã được sắp xếp sẵn.
- Không viết một
main— trình kiểm tra sẽ cung cấp cho bạn một cái.
Watch a sort run · Xem quá trình sắp xếp chạy
Bubble / selection / insertion all compare and swap into order. · Bubble / selection / insertion đều so sánh và hoán đổi vào thứ tự.
Complete void swap(int a[], int i, int j) so it exchanges the items at index i and j, in place (no return). Do not write a main. · Hoàn thành void swap(int a[], int i, int j) để hoán đổi các phần tử tại chỉ số i và j, ngay tại chỗ (không return). Không viết một main.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Complete void bubble_sort(int a[], int n) so it sorts the array ascending, in place, using bubble sort. Do not write a main. · Hoàn thành void bubble_sort(int a[], int n) để sắp xếp mảng tăng dần, ngay tại chỗ, sử dụng bubble sort. Không viết một main.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Complete void insertion_sort(int a[], int n) so it sorts the array ascending, in place, using insertion sort (take each item as a key and shift bigger items right). Do not write a main. · Hoàn thành void insertion_sort(int a[], int n) để sắp xếp mảng tăng dần, ngay tại chỗ, sử dụng insertion sort (xét mỗi phần tử làm khóa và dịch các phần tử lớn hơn sang phải). Không viết một main.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.