Vấn đề
Tại sao sắp xếp làm tìm kiếm dễ dàng hơn? Làm sao đánh giá hiệu quả sắp xếp?
Giải pháp
Sắp xếp là quá trình sắp xếp các phần tử theo thứ tự tăng dần hoặc giảm dần.
- Con người nhận ra tầm quan trọng của tìm kiếm nhanh → khái niệm sắp xếp ra đời.
- Dữ liệu không có thứ tự → tìm kiếm khó khăn. Sắp xếp giúp dữ liệu có trình tự → tìm kiếm dễ dàng.
Hiệu quả sắp xếp
Tiêu chí đánh giá thuật toán:
- Thời gian thực hiện (Time complexity).
- Bộ nhớ tiêu tốn (Space complexity).
Các nhà khoa học máy tính phát triển nhiều thuật toán sắp xếp khác nhau để tối ưu hai tiêu chí này.
Ví dụ chương trình (Selection Sort)
#include <stdio.h>
int main() {
int a[50], n, i, j, t, sm;
printf("Nhap so phan tu: ");
scanf("%d", &n);
printf("Nhap cac phan tu: ");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
for (i = 0; i < n-1; i++) {
sm = i;
for (j = i+1; j < n; j++)
if (a[j] < a[sm]) sm = j;
t = a[i];
a[i] = a[sm];
a[sm] = t;
}
printf("Mang sau sap xep: ");
for (i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}
Kết quả
Nhap so phan tu: 4 Nhap cac phan tu: 34 12 56 7 Mang sau sap xep: 7 12 34 56