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ộid
Tì kiế
Nội
d
ung
Tì
m
kiế
m
Tuần tự
Nhịphân
Nhị
phân
Sắp xếp
Bubble sort
Bubble
sort
Selection sort
Insert sort
Insert
sort
Quick sort
Tìm kiếm
3
Tìm kiếm: duyệtmột danh sách và lấyraphầntử
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
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
Giảithuật
Giải
thuật
4
In
put:
put:
Mảng A gồm n phần tử
Giá trị xcần tìm
Trả về:
Vị trí phần tử xtrong A hoặc –1 nếu xkhông xuất hiện
Thao tác cơ bản:
So sánh
Tìm kiếm tuần tự
Giảithuật
Giải
thuật
5
Giảithuậ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
x = 6
1 25 6 5 2 37 40
Dừng
1 25 6 5 2 37 40