CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
1
CHƯƠNG 2
TÌM KIẾM VÀ SẮP XẾP NỘI
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
2
Nội Dung
Các giải thuật tìm kiếm nội
1. Tìm kiếm tuyến tính
2. Tìm kiếm nhị phân
Các giải thuật sắp xếp nội
1. Đổi chỗ trực tiếp – Interchange Sort
2. Chọn trực tiếp – Selection Sort
3. Nổi bọt – Bubble Sort
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
3
Nội Dung (Tt)
4. Chèn trực tiếp – Insertion Sort
5. Chèn nhị phân – Binary Insertion Sort
6. Shaker Sort
7. Shell Sort
8. Heap Sort
9. Quick Sort
10. Merge Sort
11. Radix Sort
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
4
Bài Toán Tìm Kiếm
Cho danh sách có n phần tử a0, a1, a2…, an-1.
Để đơn giản trong việc trình bày giải thuật ta dùng
mảng 1 chiều a để lưu danh sách các phần tử nói
trên trong bộ nhớ chính.
Tìm phần tử có khoá bằng X trong mảng
Giải thuật tìm kiếm tuyến tính (tìm tuần tự)
Giải thuật tìm kiếm nhị phân
Lưu ý: Trong quá trình trình bày thuật giải ta
dùng ngôn ngữ lập trình C.
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
5
Tìm Kiếm Tuyến Tính
Ý tưởng : So sánh X lần lượt với phần tử thứ 1,
thứ 2,…của mảng a cho đến khi gặp được khóa
cần tìm, hoặc tìm hết mảng mà không thấy.
Các bước tiến hành
• Bước 1: Khởi gán i=0;
• Bước 2: So sánh a[i] với giá trị x cần tìm, có 2 khả
năng
+ a[i] == x tìm thấy x. Dừng;
+ a[i] != x sang bước 3;
• Bước 3: i=i+1 // Xét tiếp phần tử kế tiếp trong mảng
Nếu i==N: Hết mảng. Dừng;
Ngược lại: Lặp lại bước 2;