Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 2: Các giải thuật tìm kiếm và sắp xếp" cung cấp cho người học các kiến thức: Định nghĩa giải thuật tìm kiếm, bài toán, tìm kiếm tuần tự,... Mời các bạn cùng tham khảo nội dung chi tiết.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Đỗ Ngọc Như Loan
- GV: Đỗ Ngọc Như Loan
- Định nghĩa giải thuật tìm
kiếm
Input: một dãy n đối tượng (a1, a2, ...., an) và
một đối tượng k
Output: là một giá trị logic true nếu có k trong
dãy hoặc false nếu ngược lại
Dùng mảng hoặc DSLK để biểu diễn dãy đối
tượng
Phần này dùng mảng một chiều (các đối
tượng là số)
- Bài toán
Yêu cầu: Cho dãy số nguyên a chứa các số đôi
một khác nhau. Quy ước vị trí của phần tử đầu tiên
là 0. Tìm vị trí xuất hiện của phần tử có giá trị k
trong dãy a hoặc đưa ra 1 nếu không có phần tử
nào bằng k.
Dữ liệu vào từ file TIMKIEM.INP có dạng:
Dòng đầu là số nguyên n và k
Dòng thứ hai gồm n số
Kết quả ra file TIMKIEM.OUT có dạng: vị trí của k
trong dãy số.
Ví dụ:
TIMKIEM.INP
6 8
- Tìm kiếm tuần tự
(Linear search)
Ý tưởng:
Duyệt tuần tự từ đầu mảng, kết hợp so sánh giá trị
các phần tử của mảng với k để xác định có hay
không phần tử k
- k = 8 9 2 8 3 1 4
i = 0
9 2 8 3 1 4
i = 1
9 2 8 3 1 4
i = 2 Đã tìm
được
Output
2
- bool Search(int A[MAX], int n, int k)
//mảng có n số nguyên
{
for (int i=0; i
- ĐỘ PHỨC TẠP
Tốt nhất: T(n) = O(1)
Xấu nhất: T(n) = O(n)
Trung bình: T(n) = O(n)
- Bài toán
Yêu cầu: Cho dãy số nguyên a chứa các số đôi
một khác nhau đã sắp xếp tăng dần. Quy ước vị trí
của phần tử đầu tiên là 0. Tìm vị trí xuất hiện của
phần tử có giá trị k trong dãy a hoặc đưa ra 1 nếu
không có phần tử nào bằng k.
Dữ liệu vào từ file TIMKIEM.INP có dạng:
Dòng đầu là số nguyên n và k
Dòng thứ hai gồm n số
Kết quả ra file TIMKIEM.OUT có dạng: vị trí của k
trong dãy số.
Ví dụ:
TIMKIEM.INP
- Bài toán
Yêu cầu: Cho dãy số nguyên a chứa các số đôi
một khác nhau đã sắp xếp tăng dần. Quy ước vị
trí của phần tử đầu tiên là 0. Tìm vị trí xuất hiện
của phần tử có giá trị k trong dãy a hoặc đưa ra 1
nếu không có phần tử nào bằng k.
Dữ liệu vào từ file TIMKIEM.INP có dạng:
Dòng đầu là số nguyên n và k
Dòng thứ hai gồm n số
Kết quả ra file TIMKIEM.OUT có dạng: vị trí của k
trong dãy số.
Ví dụ:
TIMKIEM.INP
- Tìm kiếm nhị phân
(binary search)
Áp dụng trong trường hợp dãy đã được sắp xếp
Ý tưởng: Tìm k tại điểm giữa của mảng, nếu
chưa tìm thấy thì thì tìm bên trái hoặc bên phải
(nhị phân) của mảng (so với điểm giữa)
- k = 8 1 2 3 4 8 9
left = 0, right = 5, mid = 2
1 2 3 4 8 9
left = 3, right = 5, mid = 4
Đã tìm
Output được
4
- k = 3 1 2 3 4 7 9 10 12
left = 0, right = 7, mid = 3
1 2 3 4 7 9 10 12
left = 0, right = 2, mid = 1
1 2 3 4 7 9 10 12
left = 2, right = 2, mid = 2
Output Đã tìm
2 được
- Begin
Nhập dãy số,
k
left = 0, right = n – 1 left k
mid
left = mid+1 right = mid1
End
- bool BinarySearch(int A[MAX], int n, int k)
{
int i=0, j=n1, m;
while(iA[m]) i=m+1;
else j=m1;
}
return false;
}
- ĐỘ PHỨC TẠP
Tốt nhất: T(n) = O(1)
Xấu nhất: T(n) = O(log2n)
Trung bình: T(n) = O(log2n)
- ĐỊNH NGHĨA GIẢI THUẬT SẮP
XẾP
- Các giải thuật sắp xếp
Insertion Sort, Selection Sort, Bubble Sort
Quick Sort, Heap Sort, Merge Sort
Counting Sort, Bucket Sort
- Bài Toán
Yêu cầu: Cho dãy số nguyên gồm n phần tử. Hãy sắp
xếp dãy số theo thứ tự tăng dần.
Dữ liệu vào từ file SAPXEP.INP gồm 2 dòng:
+ Dòng 1 chứa số nguyên dương n (n
- Chọn trực tiếp (selection sort)
Chọn phần tử nhỏ nhất trong A[i…n] và hoán
vị cho phần tử đầu tiên A[i]
Bắt đầu với i=1 và lặp lại cho đến khi i=n1
- 3 5 2 1 7 i = 1 k = 4
1 5 2 3 7 i = 2 k = 3
1 2 5 3 7 i = 3 k = 4
1 2 3 5 7 i = 4 k = 4
1 2 3 5 7
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
