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

Chia sẻ: Bạch Đăng Kỳ | Ngày: | Loại File: PDF | Số trang:56

Thêm vào BST

Báo xấu

14
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

1 TÌM KIẾM & SẮP XẾP Bài giảng Cấu trúc dữ liệu và Giải thuật
Nộ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ếm 3 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ếm 4 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 p 8 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ân 9 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ình 10 int BinarySearch(int a[], int n, int x) { int l = 0, r = n-1; while ( (l
Tìm kiếm nhị phân 11 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ân 12 Đá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 p 13 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ếp 14 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ị trí hai phần tử)
Sắp xếp 15 Các giải thuật Các phương pháp sắp xếp thông dụng: Bubble Sort Selection Sort Insertion Sort QQuick Sort Merge Sort Shell Sort Heap Sort Radix Sort
Bubble sort 16 Giải thuật: Xuất phát từ cuối (đầu) dãy, đổi chỗ các cặp phần tử kế cận để đưa pphần tử nhỏ hơn về vị trí đúng g đầu dãyy hiện hành. Sau đó không xét đến nó ở bước kế tiếp. Lần xử lý thứ i sẽ có vị trí đầu dãy là i. Lặp lại cho đến khi không còn cặp phần tử nào để xét. Ví dụ: sắp xếp dãy A: 15 2 8 7 3 6 9 17
Bubble sort 17 Ví dụ i=0 j=4 15 2 8 7 3 6 9 17 i=0 j=3 15 2 8 3 7 6 9 17 i=0 j=1 15 2 3 8 7 6 9 17 i=1 j=5 2 15 3 8 7 6 9 17 i=1 j=4 2 15 3 8 6 7 9 17 i=1 j=2 2 15 3 6 8 7 9 17 i=2 j=5 2 3 15 6 8 7 9 17 i=2 j=3 2 3 15 6 7 8 9 17
Bubble sort 18 Ví dụ (tt) i=3 j=4 2 3 6 15 7 8 9 17 i=4 j=5 2 3 6 7 15 8 9 17 i=5 j=6 2 3 6 7 8 15 9 17 i=6 j=7 2 3 6 7 8 9 15 17 2 3 6 7 8 9 15 17
Bubble sort 19 Chương trình void BubbleSort(int a[], int n){ for(int i=0; ii; j--){ if( [j]< [j 1])// ế sai if(a[j]
Bubble sort 20 Bài tập Mô tả tình trạng dãy A sau mỗi bước chạy với thuật toán Bubble sort. A = {2, {2 9, 9 5, 5 12, 12 20, 20 15 15, -8 8, 10}