Sorting: bubble, selection, and insertion
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.
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.
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ự.
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;
}
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.
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.
Xem quá trình sắp xếp chạy
Bubble / selection / insertion all compare and swap into order.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Complete void swap(int a[], int i, int j) so it exchanges the items at index i và j, in place (no return). Do không write a main.
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
Complete void bubble_sort(int a[], int n) so it sorts the array ascending, in place, using bubble sort. Do không write a main.
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
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 không write a main.
Nhấn Chạy để xem kết quả ở đây.