CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1

CÁC THUẬT TOÁN TÌM KIẾM VÀ SẮP XẾP CƠ BẢN

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

Nội dung trình bày

2

Giới thiệu các giải thuật tìm kiếm

Tìm kiếm tuần tự

Tìm kiếm nhị phân

Đánh giá và tổng kết

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

1. Giới thiệu thuật toán tìm kiếm

3

 Tìm kiếm là thao tác rất phổ biến trong cuộc

sống hàng ngày.  Các loại tìm kiếm:

 Tìm kiếm tuần tự (Sequential/ Linear Search)  Tìm kiếm nhị phân (Binary Search)  ……  Mục tiêu:

 Tìm hiểu về 2 giải thuật tìm kiếm cơ bản.  Phân tích thuật toán để lựa chọn thuật toán

phù hợp với dữ liệu đầu vào.

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

2.1. Tìm kiếm tuần tự - Vét cạn

 Minh họa:

4  Ý tưởng: So sánh x lần lượt với các phần tử của mảng A cho đến khi gặp được phần tử có giá trị x cần tìm, hoặc đã tìm đến hết mảng mà không thấy x. x = 28 x = 27

Có x trong Không tìm thấy x mảng trong mảng

25

7

3

12 27

5

9

8

61

28 27

28 27

28 27

28 27

28 27

28

28

28

28

28

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

2.1. Tìm kiếm tuần tự - Vét cạn

5

 Input:

 Mảng A.  n phần tử.  Giá trị x cần tìm

 Output:

 Nếu x xuất hiện trong A, trả về 1.  Ngược lại, trả về 0.

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

2.1. Tìm kiếm tuần tự - Vét cạn

6

 Bước 1: Bắt đầu từ phần tử đầu tiên: i = 0  Bước 2: so sánh i và n

 Nếu chưa hết mảng (i=n), kết thúc.Trả về 0.

 Bước 3: So sánh giá trị A[i] với x

 Nếu A[i] bằng x: kết thúc. Trả về 1.  Nếu A[i] khác x, tăng i thêm 1 và quay lại

bước 2.

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

2.1. Tìm kiếm tuần tự - Vét cạn

7

Bắt đầu

Lưu đồ thuật toán

Nhập A, n, x

i = 0

Đ i>=n Kết thúc

S

Đ

A[i] = x

S

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

i = i+1

2.1. Tìm kiếm tuần tự - Vét cạn

8

 Mỗi vòng lặp, có 2 điều kiện cần kiểm tra:  Kiểm tra đã duyệt hết mảng? (bước 2)  Kiểm tra phần tử hiện tại có bằng x?(bước 3)

 Số phép so sánh trung bình: 2(1+2+3+…+n)/n = n+1  Số phép so sánh tăng/giảm tuyến tính theo số phần tử.

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

2.1. Tìm kiếm tuần tự - Vét cạn

9

 Độ phức tạp của thuật toán:

 Tốt nhất: O(1)  Trung bình: O(n)  Xấu nhất: O(n)

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

2.2. Tìm kiếm tuần tự - Lính canh

10

 Có thể bỏ qua việc kiểm tra điều kiện cuối

mảng bằng cách dùng “lính canh”.

 Lính canh là phần tử có giá trị bằng với

phần tử cần tìm và được đặt ở cuối mảng.

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

2.2. Tìm kiếm tuần tự - Lính canh

11

Ví dụ: A = {25, 6, 18, 4}; x = 7 (1)

25 18 4 6 7 25 6 18 4 7 (2)

x=7 x=7

(3) 25 6 18 4 7 (4) 25 6 18 4 7

x=7 x=7

i = 4 (i>n)

25 6 18 4 7 (5)

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

x=7

2.2. Tìm kiếm tuần tự - Lính canh

12

 Bước 1: Bắt đầu từ phần tử đầu tiên: i = 0  Bước 2: So sánh giá trị A[i] với giá trị x

 Nếu A[i] khác x, tăng i thêm 1 và quay lại bước 2.  Nếu A[i] bằng x:

• Nếu i=n: kết thúc, trả về 0.

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

Task

13

 Task 1: Cài đặt thuật toán tìm kiếm theo

cách vét cạn và sử dụng lính canh.

 Task 2: Xây dựng thuật toán và cài đặt

chương trình tìm những vị trí mà x xuất hiện trong mảng cho trước.

 Task 3: Xây dựng thuật toán và cài đặt

chương trình tìm xem trong mảng cho trước có phần tử nào là số chẵn hay không?

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

3. Tìm kiếm nhị phân (Binary Search)

14

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

Thuật toán tìm kiếm nhị phân

15

 Với dãy A được sắp xếp tuần tự (tăng/giảm) thì độ phức tạp của thuật toán tìm kiếm tuần tự không đổi.

 Tận dụng thông tin của mảng đã được sắp

xếp để giới hạn vùng tìm kiếm của giá trị cần tìm trong mảng.

 Thuật toán tìm kiếm nhị phân.

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

Thuật toán tìm kiếm nhị phân

16

 Input:

 Mảng A với n phần tử đã được sắp xếp.  Giá trị x cần tìm.

 Output:

 Nếu x xuất hiện trong A, trả về 1.  Ngược lại, trả về 0.

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

Thuật toán tìm kiếm nhị phân

17

Ý tưởng:  So sánh x với giá trị của phần tử chính giữa của

mảng A.

 Nếu x là phần tử chính giữa thì dừng.  Nếu không, xác định xem x thuộc nửa trái

hay nửa phải của phần tử chính giữa.  Lặp lại 2 bước trên với nửa đã được xác định.

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

Thuật toán tìm kiếm nhị phân

18

 Bước 1: left = 0; right = n-1;  Bước 2: mid = (left + right)/2; So sánh A[mid] với x có 3 khả năng:

 A[mid] = x: Tìm thấy. Dừng.  A[mid] > x: right = mid - 1;  A[mid] < x: left = mid + 1;

 Bước 3: Nếu left <= right: lặp lại Bước 2.

Ngược lại: Dừng.

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

Thuật toán tìm kiếm nhị phân

19

mid=(0+2)/2=1 mid=(0+6)/2=3 mid mid

Minh họa: A[] = {4, 8, 15, 17, 32, 59, 72}, x = 8. Index

0 1 2 3 4 5 6

8 15 17 32 59 72 A[i] 4

Lần 2

right right Lần 1 left left

x

x=A[1]

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

Đã tìm thấy x trong A, kết thúc

Thuật toán tìm kiếm nhị phân

20

Minh họa: A[] = {4, 8, 15, 17, 32, 59, 72},

x = 73 x = 72

mid=(6+6)/2=6 mid mid=(4+6)/2=5 mid=(0+6)/2=3 mid mid

1 2 3 4 5 0 Index 6

8 15 17 32 59 4 A[i] 72

Lần 1

right right left left

left right Lần 2

x>A[3]

x>A[5]

Lần 3

x=A[6] left>right x>A[6]

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

Tìm thấy x trong Không tìm thấy x A, kết thúc trong A, kết thúc

Thuật toán tìm kiếm nhị phân

21

Phân tích thuật toán:  Mỗi lần lặp thì chiều dài của mảng con giảm

đi ½ so với chiều dài mảng trước đó.  Chia mảng A đến khi còn 1 phần tử: ((…(((n/2)/2)/2)…)/2) = n/2k n/2k =1; n = 2k ; log2n= log2n; k = log2n Số lần thực hiện vòng lặp while khoảng k lần, mỗi vòng lặp thực hiện 1 phép so sánh.

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

Thuật toán tìm kiếm nhị phân

22

Phân tích thuật toán:  Trường hợp tốt nhất: k = 1  x là phần tử

chính giữa của mảng.

 Trường hợp xấu nhất: k = log2n  x không

thuộc mảng hoặc x là phần tử thuộc biên của mảng.

 Số phép so sánh tăng theo hàm logarit.

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

Thuật toán tìm kiếm nhị phân

23

Độ phức tạp của tìm kiếm nhị phân: Trường hợp tốt nhất: O(1) Trường hợp trung bình: O(log2n/2) Trường hợp xấu nhất: O(log2n)

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

So sánh hiệu suất

24

So sánh trường hợp xấu nhất của 2 thuật toán tìm kiếm:

Trường hợp xấu nhất

Kích thước mảng Nhị phân Tuần tự

100.000 100.000 16

200.000 200.000 17

400.000

400.000

18

800.000 800.000 19

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

1.600.000 1.600.000 20

4. Tổng kết

25

 Thuật toán tuần tự:  Tìm kiếm cho đến khi tìm thấy giá trị cần tìm

hoặc hết mảng.

 Hiệu suất của tìm kiếm tuần tự trong trường hợp

xấu nhất là 1 hàm tuyến tính theo số phần tử của mảng.

 Tìm kiếm nhị phân:  Dùng kết quả của phép so sánh để thu hẹp vùng

tìm kiếm kế tiếp.

 Hiệu suất của tìm kiếm nhị phân là một hàm

logarit theo số phần tử của mảng.

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

LinearSearch

26

return kq;

if(a[i]==x) kq = false;

int kq = true; for(int i=0; i

bool LinearSearch(int a[], int n, int x) { }

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

BinarySearch

27

return kq;

right=mid-1;

mid=(left+right)/2; if(x==a[mid]) else if(x

int left=0, right=n-1,mid; bool kq=true; do{ } while(left

Bool BinarySearch(int a[], int n, int x) { }

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015

28

1. Sử dụng thuật toán tìm kiếm tuần tự trên mảng 1 chiều, cài đặt các hàm xử lý các yêu cầu sau:

- Đếm số lượng của x có trong mảng. - Xuất ra các vị trí của x trong mảng. 2. Sử dụng thuật toán tìm kiếm nhị phân với mảng bất kỳ.

Các thuật toán tìm kiếm và sắp xếp cơ bản

8/27/2015