SẮP XẾP VÀ TÌM KIẾM
TRÊN CTDL MẢNG
Nhóm 2:
Nguyễn Khắc Duy
Nguyễn Thị Lan Ngọc
Võ Hoàng YếnGIỚI THIỆU
CTDL mảng là một trong số những CTDL thông dụng
nhất.
Mảng là một tập hợp có thứ tự các giá trị có cùng cấu trúc
được lưu trữ liên tiếp nhau trong bộ nhớ.(Mảng là một
danh sách tuyến tính).CÁC THUẬT TOÁN
TÌM KIẾM VÀ SẮP XẾPTÌM KIẾM

Trong hầu hết các hệ lưu trữ, quản lí dữ liệu, thao tác
tìm kiếm thường được thực hiện nhất để khai thác thông
tin.

VD: tra cứu từ điển, tìm sách thư viện

Việc xây dựng các giải thuật cho phép tìm kiếm nhanh
i=2
Tìm thấy rồi
i=0 i=1
12 2 8 5 1
X=8
Vị trí của x cần tìm là:212 2 8 5
X=7
i=0
12 2 8 5
X=7
i=1
12 2 8 5
X=7
i=2
12 2 8 5
X=7
i=3
KHÔNG TÌM
THẤY !i=2
KHÔNG
TÌM
THẤY !!!!!

RỒI !
Phần tử cần tìm là 8:
Quá trình tìm:
L=0,R=7M=3
L=4,R=7M=5NHẬN XÉT

Giải thuật tìm kiếm nhị phân chỉ áp dụng cho những mảng
đã được sắp xếp.

Tiết kiệm thời gian rất nhiều so với tìm kiếm tuần tự.

Độ phức tạp: T(n)=O(log
2
n).SẮP XẾP

Sắp xếp là quá trình xử lí một danh sách để chúng theo
một thứ tự thỏa mãn một tiêu chuẩn nào đó.

Sắp xếp dữ liệu là một nhu cầu thường thấy và cần
thiết. Chẳng hạn, trước khi tìm kiếm nhị phân, mảng
cần được sắp xếp.CÁC GIẢI THUẬT SẮP XẾP


Nhận xét

Độ phức tạp : T(n)=O(n
2
).

Số phép so sánh không phụ thuộc tình trạng
mảng ban đầu.

Số lần hoán vị phụ thuộc tình trạng mảng ban
đầu.
Trường hợp Số lần so
sánh
Số phép gán
Tốt nhất n(n-1)/2 0
Xấu nhất n(n-1)/2 3n(n-1)/2INSERTSORT
(Chèn trực tiếp)

Ý tưởng: lần lượt chèn phần tử a[i] vào vị trí thích hợp
của đọan đã được sắp để được dãy mới a[1],a[2],…,a[i]
có thứ tự.12 2 8 5 1
i=1 i=2 i=3 i=4
HOÀN TẤT !
Nhận xét

Độ phức tạp: T(n)=O(n
2
)

BubbleSort có khuyết điểm: không nhận diện
được dãy đã có thứ tự hoặc thứ tự từng phần;
các phần tử lớn được đưa về vị trí rất chậm.
Trường hợp Số phép so sánh Số phép gán
Tốt nhất n(n-1)/2 0
Xấu nhất n(n-1)/2 n(n-1)/2