Bài giảng Cấu trúc dữliệu và giải thuật: Tìm kiếm và sắp xếp - Đậu Ngọc Hà Dương

Bài giảng Cấu trúc dữliệu và giải thuật: Tìm kiếm và sắp xếp - Đậu Ngọc Hà Dương có nội dung trình bày về tìm kiếm tuần tự và tìm kiếm nhị phân; sắp xếp bubble sort, selection sort, insert sort, quick sort,... Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữliệu và giải thuật: Tìm kiếm và sắp xếp - Đậu Ngọc Hà Dương 1TÌM KIẾM & SẮP XẾPBài giảng Cấu trúc dữ liệu và Giải thuậtNội d dung‰ Tì kiếm Tìm kiế ƒ Tuần tự ƒ Nhị phân‰ Sắp xếp ƒ Bubble sort ƒ Selection sort ƒ Insert sort ƒ Quick sort Tìm kiếm3 … Tìm kiếm: duyệt một danh sách và lấy ra phần tử thoả tiêu chuẩn cho trước. … Là thao tác phổ biến trên máy tính: † Tìm mẫu tin trong cơ sở dữ liệu † Tìm kiếm thông tin trên Internet… … Khảo sát việc tìm kiếm trên mảng/danh sách. Tìm kiếm4 Giải thuật … Input: put: † Mảng A gồm n phần tử † Giá trị x cần tìm … Trả về: † Vị trí phần tử x trong A hoặc –1 nếu x không xuất hiện … Thao tác cơ bản: † So sánh Tìm kiếm tuần tự5 Giải thuật … Giải thuật: † Lần lượt so sánh x với các phần tử của mảng A cho đến khi gặp được phần tử cần tìm, hoặc hết mảng. … Ví dụ: A = {1, 25, 6, 5, 2, 37, 40}, x = 6 x = 6 1 25 6 5 2 37 40 x = 6 1 25 6 5 2 37 40 x = 6 1 25 6 5 2 37 40 Dừng Tìm kiếm tuần tự6 Đánh giá … Đánh giá (thao tác so sánh): † Tốtnhất: O(1) Hiếm khi xảy ra. Tại sao? † Xấu nhất: O(n) † Trung bình: „ Giả sử dữ liệu phân bố đều, xác suất bắt gặp x tại mỗi vị trí đều như nhau. „ Mỗi vòng lặp thực hiện 2 thao tác so sánh. Tại sao? „ Số thao tác = 2*(1 + 2 + … + n) = n + 1 „ Độ phức tạp: O(n) Tìm kiếm tuần tự7 Phần tử lính canh … Mỗi vòng lặp cần 2 thao tác so sánh: † Kiểm tra hết mảng † Kiểm tra phần tử hiện tại có bằng x … Phần tử lính canh: đặt giá trị x vào cuối mảng ⇒ không cần kiểm tra điều kiện hết mảng. … Ví dụ: A = {1, 25, 5, 2, 37}, x = 6 1 25 5 2 37 6 … Trả về: ề: n nếu nế không tìm thấ thấy Tìm kiếm nhịị phân p8 … Khi mảng gồm các phần tử được sắp, sắp tận dụng điều kiện này để giảm số thao tác. … Ý tưởng: † Xétphần tử giữa A[m] † Nếu A[m] = x, trả về m † Nếu A[m] > x, x tìm trong các phần tử bên trái của m † Nếu A[m] < x, tìm trong các phần tử bên trái của m Tìm kiếm nhị phân9 Ví dụ minh hoạ … A = {2, {2 3, 3 6, 6 7, 7 10 10, 16, 16 18}, 18} x = 16 2 3 6 7 10 16 18 [0] [1] [2] [3] [4] [5] [6] [4] [5] [6] 2 3 6 7 10 16 18 Tìm kiếm nhị phân Chương trình10 int BinarySearch(int a[], int n, int x) { int l = 0, r = n-1; while ( (l Tìm kiếm nhị phân11 Bài tập … Thực hiện việc tìm kiếm đối với các bài tập sau: †A= {1, 2, 6, 26, 28, 37, 40}, x = 40 †A= {1, 2, 6, 26, 28, 37, 40}, x = -7 Tìm kiếm nhị phân12 Đánh giá … Mỗi lần lặp lặp, chiều dài mảng con phải xét được giảm ½ so với mảng trước đó. … Mảng ban đầu được chia tối đa k lần với k = ⎣log2n⎦. … Tối đa k vòng lặp được thực hiện trong đó mỗi vòng lặp thực hiện 1-2 phép so sánh. … Độ phức tạp: O(log2n) … Mảng cần được sắp xếp trước!!! Sắp p xếp p13 … Sắp xếp: tổ chức các phần tử trong một danh sách theo thứ tự. … Là bài toán phổ biến trên máy tính. … Nhiều giải thuật sắp xếp đã ra đời. đời … Khảo sát Khả át vàà đánh đá h giá iá hiệu hiệ quảả một ột số ố giải iải thuật th ật sắp ắ xếp thông dụng dựa trên mảng. Sắp xếp14 Giải thuật … Input: † Mảng A gồm n phần tử. … Output: † Một hoán vị của A sao cho: A0 ≤ A1 ≤ … ≤ An-1 (sắp xếp p tăngg dần). ) … Thao tác cơ bản: † Sosánh † Hoán vị (đổi vị ...