Cấu trúc dữ liệu - Phần 3

Chia sẻ: Nguyen Nguyen | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

156
lượt xem 24
download

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

Tài liệu tham khảo bài giảng môn Cấu trúc dữ liệu - Phần 3 Tìm kiếm và sắp xếp

Chủ đề:

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

Lưu

Nội dung Text: Cấu trúc dữ liệu - Phần 3

12/6/2010 Tìm kiếm và sắp xếp GVGD: Trương Phước Hải LOGO Nội dung 1. Bài toán tìm kiếm và sắp xếp 2. Một số phương pháp tìm kiếm 3. Một số phương pháp sắp xếp 2 Bài toán tìm kiếm và sắp xếp  Tìm kiếm và sắp xếp là 2 bài toán rất kinh điển trong tin học  Tìm kiếm là thao tác được thực hiện nhiều nhất trong các hệ thống lưu trữ và quản lý dữ liệu Tra từ điển, tìm kiếm sinh viên, tìm kiếm khách hàng, …  Thao tác tìm kiếm sẽ thực hiện hiệu quả khi dữ liệu được tổ  chức theo một trật tự nào đó  Sắp xếp dữ liệu cũng là yêu cầu cần phải có trong các hệ thống thông tin quản lý, … 3 1
12/6/2010 Bài toán tìm kiếm và sắp xếp  Bài toán tìm kiếm Cho một tập gồm N phần tử dữ liệu. Cho biết sự tồn tại  hoặc chỉ ra vị trí xuất hiện của một phần tử nào đó với thông tin xác định được cho trước  Bài toán sắp xếp Cho một tập gồm N phần tử dữ liệu. Sắp xếp các phần tử  dữ liệu có thứ tự (tăng hoặc giảm dần) theo một tiêu chí cho trước 4 Bài toán tìm kiếm và sắp xếp  Tính hiệu quả của các phương pháp tìm kiếm và sắp xếp phụ thuộc vào tính chất của CTDL  Các phương pháp tìm kiếm và sắp xếp cũng phụ thuộc vào dữ liệu lưu trữ ở bộ nhớ trong hay bộ nhớ ngoài  Các giải thuật được trình bày dành cho dữ liệu lưu trữ ở bộ nhớ trong 5 Nội dung 1. Bài toán tìm kiếm và sắp xếp 2. Một số phương pháp tìm kiếm 3. Một số phương pháp sắp xếp 6 2
12/6/2010 Bài toán tìm kiếm  Bài toán Cho mảng 1 chiều A gồm N phần tử nguyên. Cho biết số  nguyên x có tồn tại trong A hay không? Nếu có thì cho biết 1 vị trí xuất hiện của x trong A Input: Mảng A gồm N phần tử nguyên, số nguyên x  Ouput:  p ≥ 0 là vị trí xuất hiện của x trong A  p < 0 nếu x không tồn tại trong A  7 Tìm kiếm tuần tự  Ý tưởng Xét lần lượt từng phần tử trong toàn bộ không gian tìm  kiếm để tìm ra 1 phần tử thỏa tiêu chí hoặc không tìm thấy phần tử nào thỏa tiêu chí Thao tác dừng lại ngay khi tìm thấy phần tử đầu tiên thỏa  tiêu chí hoặc xét hết tất cả phần tử 8 Tìm kiếm tuần tự  Giải thuật Bắt đầu N, A[0], A[1], .., A[N-1], x i=0 F T i
12/6/2010 Tìm kiếm tuần tự  Cài đặt int LinearSearch(int A[], int N, int x) { for (int i = 0; i < N; i++) { if (A[i] == x) return i; } return -1; } 10 Tìm kiếm tuần tự  Đánh giá Dựa trên số phép so so sánh của giải thuật  Trường hợp Số phép so sánh Diễn giải Tốt nhất 1 x nằm ở đầu mảng Xấu nhất N x không thuộc mảng Độ phức tạp tính toán cấp N: T(N) = O(N)  11 Tìm kiếm nhị phân  Ý tưởng Điều kiện thực thi giải thuật: không gian tìm kiếm phải  được sắp thứ tự (tăng dần hoặc giảm dần) theo tiêu chí tìm kiếm Dựa vào tiêu chí có thứ tự để thu hẹp một nửa không gian  tìm kiếm sau mỗi bước thực hiện 12 4
12/6/2010 Tìm kiếm nhị phân  Giải thuật Bước 1: đặt L = 0, R = N – 1 (L: đầu dãy; R: cuối dãy)  Bước 2:   Nếu L < R đúng thì đến bước 3  Ngược lại đến bước 4 Bước 3:   Đặt M = (L + R)/2 (M: vị trí giữa dãy)  Trường hợp x = A[M] thì tìm thành công. Đến bước 4  Trường hợp x < A[M] thì đặt R = M – 1  Trường hợp A[M] < x thì đặt L = M + 1  Quay về bước 2 Bước 4: kết thúc  13 Tìm kiếm nhị phân  Minh họa x=9 1 2 4 5 9 12 15 x=9 1 2 4 5 9 12 15 x=9 1 2 4 5 9 12 15 0 1 2 3 4 5 6 15 Tìm kiếm nhị phân  Cài đặt int BinSearch(int A[], int N, int x) { int L = 0, R = N – 1; while (L < R) { int M = (L + R)/2; if (A[M] == x) return M; if (x < A[M]) R = M – 1; else L = M + 1; } return -1; } 16 5
12/6/2010 Tìm kiếm nhị phân  Đánh giá Trường hợp Số phép so sánh Diễn giải Tốt nhất 1 x nằm ở giữa mảng Xấu nhất log2N x không thuộc mảng T(N) = O(log2N)  17 Nội dung 1. Bài toán tìm kiếm và sắp xếp 2. Một số phương pháp tìm kiếm 3. Một số phương pháp sắp xếp 18 Bài toán sắp xếp  Bài toán Cho mảng 1 chiều A gồm N phần tử nguyên. Hãy sắp xếp  mảng A sao cho các phần tử của A có thứ tự không giảm (A[0] ≤ A[1] ≤ … ≤ A[N - 1]) Input: Mảng A gồm N phần tử nguyên  Ouput: Mảng A gồm N phần tử nguyên với thứ tự không  giảm 19 6
12/6/2010 Bài toán sắp xếp  Một số phương pháp thực hiện Chọn trực tiếp (selection sort)  Đổi chỗ trực tiếp (interchange sort)  Nổi bọt (bubble sort)  Shaker sort  Chèn trực tiếp (insertion sort)  Shell Sort  Heap sort  Quick sort  Merge sort  20 Phương pháp chọn trực tiếp  Ý tưởng Chọn đúng phần tử lớn thứ i và đưa về vị trí i trong dãy  Thực hiện đưa lần lượt N – 1 phần tử về đúng vị trí của nó  để có được dãy có thứ tự 21 Phương pháp chọn trực tiếp  Giải thuật Bước 1: đặt i = 0  Bước 2: đặt min = vị trí của phần tử nhỏ nhất trong dãy từ  i đến N – 1 (cuối mảng) Bước 3:   Hoán vị A[i] và A[min]  Đặt i = i + 1 Bước 4:   Nếu i < N – 1 đúng quay về bước 2  Ngược lại kết thúc 22 7
12/6/2010 Phương pháp chọn trực tiếp  Minh họa 10 2 6 4 7 1 19 3 i=0 i=1 1 2 6 4 7 10 19 3 i=2 1 2 6 4 7 10 19 3 i=3 1 2 3 4 7 10 19 6 0 1 2 3 4 5 6 7 24 Phương pháp chọn trực tiếp  Minh họa 1 2 3 4 7 10 19 6 i=4 i=5 1 2 3 4 6 10 19 7 i=6 1 2 3 4 6 7 19 10 i=7 1 2 3 4 6 7 10 19 0 1 2 3 4 5 6 7 25 Phương pháp chọn trực tiếp  Cài đặt void SelectionSort(int A[], int N) { for (int i = 0; i < N - 1; i++) { int min = i; for (int j = i + 1; j < N; j++) if (A[j] < A[min]) min = j; HoanVi(A[i], A[min]); } } 26 8
12/6/2010 Phương pháp đổi chỗ trực tiếp  Minh họa i=0 10 2 6 4 7 1 19 3 2 10 6 4 7 1 19 3 1 10 6 4 7 2 19 3 0 1 2 3 4 5 6 7 31 Phương pháp đổi chỗ trực tiếp  Minh họa i=1 1 10 6 4 7 2 19 3 1 6 10 4 7 2 19 3 1 4 10 6 7 2 19 3 1 2 10 6 7 4 19 3 0 1 2 3 4 5 6 7 32 Phương pháp đổi chỗ trực tiếp  Minh họa i=2 1 2 10 6 7 4 19 3 1 2 6 10 7 4 19 3 1 2 4 10 7 6 19 3 1 2 3 10 7 6 19 4 0 1 2 3 4 5 6 7 33 10
12/6/2010 Phương pháp đổi chỗ trực tiếp  Minh họa i=3 1 2 3 10 7 6 19 4 1 2 3 7 10 6 19 4 1 2 3 6 10 7 19 4 1 2 3 4 10 7 19 6 0 1 2 3 4 5 6 7 34 Phương pháp đổi chỗ trực tiếp  Minh họa i=4 1 2 3 4 10 7 19 6 1 2 3 4 7 10 19 6 1 2 3 4 6 10 19 7 0 1 2 3 4 5 6 7 35 Phương pháp đổi chỗ trực tiếp  Minh họa i=5 1 2 3 4 6 10 19 7 1 2 3 4 6 7 19 10 0 1 2 3 4 5 6 7 36 11
12/6/2010 Phương pháp nổi bọt  Ý tưởng Xét từ đáy (cuối mảng) lên mặt nước (đầu mảng) và cho  nổi bọt những cặp phần tử liền kề nhau, phần tử nhẹ hơn (có giá trị nhỏ hơn) sẽ được nổi lên trên Sau mỗi đợt nổi bọt, phần tử nhẹ nhất sẽ được nổi lên trên  mặt nước (đầu mảng) 40 Phương pháp nổi bọt  Giải thuật Bước 1: đặt i = 0 (i là mức mặt nước)  Bước 2: đặt j = N – 1 (xuất phát từ đáy nước, j là đáy)   Nếu j > i //nếu chưa đến mặt nước  Nếu A[j] < A[j – 1] thì đổi chỗ A[j] và A[j – 1]  j = j – 1 //nổi dần lên mặt nước Bước 3: i = i + 1 //hạ thấp mức mặt nước   Nếu i < N – 1 thì quay về bước 2  Ngược lại kết thúc 41 Phương pháp nổi bọt  Minh họa i=0 10 2 6 4 7 1 19 3 10 2 6 4 7 1 3 19 1 10 2 6 4 7 3 19 1 2 3 4 5 6 7 43 13
12/6/2010 Phương pháp nổi bọt  Minh họa i=1 1 10 2 6 4 7 3 19 1 10 2 3 6 4 7 19 1 2 10 3 6 4 7 19 0 1 2 3 4 5 6 7 44 Phương pháp nổi bọt  Minh họa i=2 1 2 10 3 6 4 7 19 1 2 10 3 4 6 7 19 1 2 3 10 4 6 7 19 0 1 2 3 4 5 6 7 45 Phương pháp nổi bọt  Minh họa i=3 1 2 3 10 4 6 7 19 1 2 3 4 10 6 7 19 0 1 2 3 4 5 6 7 i=4 1 2 3 4 10 6 7 19 1 2 3 4 6 10 7 19 0 1 2 3 4 5 6 7 46 14
12/6/2010 Phương pháp Shaker Sort  Ý tưởng Là phương pháp cải tiến, khắc phục những nhược điểm của  phương pháp nổi bọt  Tại mỗi bước sắp xếp, phần tử nhẹ nổi lên rất nhanh nhưng phần tử nặng chìm xuống rất chậm Thực hiện cho phần tử nhẹ nổi lên và phần tử nặng chìm  xuống  Tại mỗi bước sắp xếp s ẽ thực hiện cho nổi phần tử nhẹ lên trên, sau đó đẩy phần tử nặng xuống Ghi nhận lại những đoạn đã có thứ tự để tránh các phép  so sánh thừa 50 Phương pháp Shaker Sort  Cài đặt void ShakerSort(int A[], int N) { int l = 0, r = N – 1, k = N - 1, j; while (l < r) { for (j = r; j > l; j --)//nhẹ nổi lên { if (A[j] < A[j – 1]) { HoanVi(A[j], A[j – 1]); k = j; //lưu lại nơi xảy ra hoán vị } } l = k; //cập nhật đầu dãy chưa có thứ tự //còn tiếp... 51 Phương pháp Shaker Sort  Cài đặt //...tiếp tục for (j = l; j < r; j ++)//nặng chìm xuống { if (A[j] > A[j + 1]) { HoanVi(A[j], A[j + 1]); k = j; //lưu lại nơi xảy ra hoán vị } } r = k; //cập nhật cuối dãy chưa có thứ tự } //kết thúc while } //kết thúc hàm 52 16
12/6/2010 Phương pháp Shaker Sort  Đánh giá Shaker sort thực hiện một cải tiến tối ưu đơn giản là đẩy  các phần tử về 2 phía Một số phần tử trong dãy sẽ được đưa về đúng vị trí nhanh  hơn phương pháp nổi bọt Shaker sort có độ phức tạp tương đồng với phương pháp  nổi bọt nhưng sẽ chạy nhanh hơn trong một số trường hợp 53 Phương pháp chèn trực tiếp  Ý tưởng Giả sử dãy đã có thứ tự tăng dần, chèn thêm 1 phần tử vào  để dãy mới cũng có thứ tự tăng dần Dãy có 1 phần tử cũng được xem là dãy có thứ tự tăng dần  54 Phương pháp chèn trực tiếp  Giải thuật Bước 1: đặt i = 1 (đoạn từ 0 đến i – 1 đã được sắp thứ tự)  Bước 2: đặt x = A[i], gọi pos là vị trí chèn x vào để dãy mới  vẫn có thứ tự Bước 3: dời các phần tử từ vị trí pos đến i – 1 sang phải 1  vị trí Bước 4: gán giá trị x cho phần tử ở vị trí pos  Bước 5: i = i + 1   Nếu i < N thì quay về bước 2  Ngược lại kết thúc 55 17
12/6/2010 Phương pháp chèn trực tiếp  Minh họa i=1 10 2 6 4 7 1 19 3 i=2 2 10 6 4 7 1 19 3 i=3 2 6 10 4 7 1 19 3 i=4 2 4 6 10 7 1 19 3 0 1 2 3 4 5 6 7 57 Phương pháp chèn trực tiếp  Minh họa i=5 2 4 6 7 10 1 19 3 i=6 1 2 4 6 7 10 19 3 i=7 1 2 4 6 7 10 19 3 i=8 1 2 3 4 6 7 10 19 0 1 2 3 4 5 6 7 58 Phương pháp chèn trực tiếp  Cài đặt void InsertionSort(int A[], int N) { for (int i = 1; i < N; i++) { int x = A[i], pos = i - 1; while (pos >= 0 && A[pos] > x) { A[pos + 1] = A[pos]; pos--; } A[pos + 1] = x; } } 59 18
12/6/2010 Phương pháp Shell Sort  Ý tưởng Với mỗi bước h, áp dụng thuật toán sắp xếp chèn trực tiếp  cho từng dãy con Làm mịn dần các dãy con bằng cách giảm độ dài của bước  nhảy h Phải đảm bảo độ dài h được giảm dần về 1, khi đó dãy  được sắp thứ tự 63 Phương pháp Shell Sort  Giải thuật Bước 1: đặt len là chiều dài các bước nhảy giảm dần lần  lượt có giá trị h[0], h[1], .., h[k - 1] Bước 2:   Chia dãy ban đầu thành len dãy con (các phần tử cách nhau len vị trí trong dãy ban đầu) Sắp xếp từng dãy con bằng phương pháp chèn trực tiếp  Bước 3: Xét len có độ dài là giá trị h[i] tiếp theo và lặp lại  bước 2 cho đến khi xét đến độ dài len = h[k – 1] 64 Phương pháp Shell Sort  Minh họa h=3  10 4 19 2 7 3 6 1 15 0 1 2 3 4 5 6 7 8 68 20