Cấu trúc dữ liệu và giải thuật - Chương 2 - Tìm kiếm và sắp xếp ppsx

1

Cấu trúc dữ liệu và giải thuật

(Data structure and Algorithms)

2

Tìm kiếm và sắp xếp

Chương II.

3

I. CÁC GIẢI THUẬT TÌM KIẾM NỘI

1. Tìm kiếm tuyến tính

2. Tìm kiếm nhị phân

II. CÁC GIẢI THUẬT SẮP XẾP NỘI

1. Chọn trực tiếp (Selection sort)

2. Chèn trực tiếp (Insertion sort)

3. Đổi chỗ trực tiếp (Interchange sort)

4. Nổi bọt (Buble sort)

5. Sắp xếp cây (Heap sort)

6. Sắp xếp dựa trên phân hoạch (Quick sort)

7. Sắp xếp trộn trực tiếp (Merge sort )

4

I. CÁC GIẢI THUẬT TÌM KIẾM NỘI

1. Tìm kiếm tuyến tính

2. Tìm kiếm nhị phân

5

* Bài toán tìm kiếm

• Cho dãy n phần tử, giả sử chúng được lưu trữ dưới dạng mảng a[1],

a[2], …., a[n], và các phần tử là số tự nhiên.

• Hãy tìm vị trí của phần tử có giá trị là x trong mảng

•Có 2 phương pháp tìm kiếm:

Tìm kiến tuyến tính

Tìm kiếm nhị phân

6

1. Tìm kiếm tuyến tính

Các bước tiến hành như sau:

Bước 1: i:=1; // bắt đầu từ phần tử đầu tiên của dãy

Bước 2: So sánh a[1] với x, có 2 khả năng

a[i]=x: Tìm thấy. Dừng

a[i] <>x: Sang Bước 3

Bước 3: i:=i+1; // xét tiếp phần tử kế trong mảng

Nếu i>n: Hết mảng không tìm thấy. Dừng

Ngược lại: Lặp lại Bước 2.

a. Tư tưởng giải thuật

Tiến hành so sánh x lần lượt với phần tử thứ nhất, thứ 2, …., của mảng cho đến

khi gặp được phần tử có khoá cần tìm, hoặc tìm hết mảng mà không thấy x.

7

1. Tìm kiếm tuyến tính

Các bước tiến hành như sau:

b. Ví dụ:

Cho dãy số a:

12 2 8 5 1 6 4 15

Hãy tìm phần tử x=8

8

1. Tìm kiếm tuyến tính

b. Ví dụ:

12 2 8 5 1 6 4 15

X=8

i=1 : a[1]<>8

9

1. Tìm kiếm tuyến tính

b. Ví dụ:

12 2 8 5 1 6 4 15

X=8

i=2 : a[2]<>8

10

1. Tìm kiếm tuyến tính

b. Ví dụ:

12 2 8 5 1 6 4 15

X=8

i=3 : a[3]=8=x

• Kết quả: Tìm thấy x=8 ở vị trí thứ 3 !

11

c. Thuật toán

1. Tìm kiếm tuyến tính

Function TuyenTinh (A, n, X)

{Nếu tìm thấy X, hàm trả về giá trị là vị trí của x trong dãy, ngược lại trả về giá trị 0}

Begin

1) { Khởi đầu}

i:=1;

2) {Tìm khoá x trong dãy}

While (a[i] <>x)and (i<n) do i:=i+1;

3) {Tìm thấy hay không}

If i=n+1 then return(0)

Else return(i)

End;

12

d. Nhận xét

1. Tìm kiếm tuyến tính

Mỗi lần thực hiện lặp while phải tiến hành kiểm tra 2 điểm kiện i<n và a[i]<>x.

Nhưng thực ra chỉ cần kiểm tra điều kiện a[i]<>x bằng cách sử dụng kỹ thuật lính

canh.

Thuật toán cải tiến

Kỹ thuật lính canh: Đặt thêm phần tử x vào cuối mảng, như vậy bảo đảm luôn

tìm được x trong mảng, sau đó dựa vào vị trí tìm để kết luận

12 2 8 5 1 6 4 15 8

Phần tử lính canh

13

e. Đánh giá giải thuật

1. Tìm kiếm tuyến tính

Giả sử xác suất các phần tử trong mảng nhận giá trị

x là như nhau

Trung bình (N+1)/2

Xấu nhất N+1 Phần tử cuối cùng có giá trị x hoặc không tìm thấy x

Tốt nhất 1 Phần tử đầu tiên có giá trị x

Trường hợp Số lần so sánh Giải thích

Độ phức tạp thuật toán T(n)=O(n)

14

a. Tư tưởng giải thuật

2. Tìm kiếm nhị phân

• Áp dụng với những dãy đã có thứ tự (giả sử thứ tự tăng), các

phần tử trong dãy có quan hệ ai-1<=ai<=ai+1

- Dãy a1, a2, …, an đã được sắp xếp tăng dần, để tìm phần tử x, có thể

tiến hành như sau:

•Nếu x>ai: Thì x có thể xuất hiện trong đoạn [ai+1, an]

•Nếu x<ai: Thì x có thể xuất hiện trong đoạn [a1, ai-1]

- Giải thuật tìm kiếm nhị phân sẽ tìm cách giới hạn phạm vi tìm kiếm x sau

mỗi lần so sánh với 1 phần tử trong dãy. Ý tưởng của giải thuật là tại mỗi

bước tiến hành so sánh x với phần tử nằm ở vị trí giữa của dãy hiện

hành, dựa vào kết qủa so ánh này để quyết định giới hạn dãy tìm kiếm ở

bước kế tiếp là nửa trên hay nửa dưới của dãy hiện hành.

15

a. Tư tưởng thuật toán

2. Tìm kiếm nhị phân

- Giả sử dãy tìm kiếm gồm các phần tử a[Left], …, a[Right] các

bước tiến hành như sau:

Bước 1: left:=1; right:=N // Tìm kiếm trên tất cả các phần tử

Bước 2: mid:= (left+right) div 2 // lấy mốc so sánh

So sánh a[mid] với x có 3 khả năng

a[mid]=x: Tìm thấy. Dừng

a[i] >x: Tìm tiếp x trong dãy con trái a[Left], …, a[mid-1]

Right:=mid-1;

a[i] <x: Tìm tiếp x trong dãy con phải a[mid+1], …, a[right]

Left:=mid+1;

Bước 3: Nếu left<=right // còn phần tử chưa xét tìm tiếp

Lặp lại bước 2

Ngược lại: Dừng // Đã xét hết tất cả các phần tử