CHƯƠNG 5
KỸ THUẬT TÌM KIẾM và
SẮP XẾP
(6 tiết)

MỤC TIÊU
Sau chương này bạn có thể:
•
Giải thích được giải thuật tìm kiếm tuyến
tính.
•
Giải thích được giải thuật tìm kiếm nhị
phân.
•
Giải thích được một số thuật toán sắp thứ
tự: Selection sort, Bubble sort, Insertion
sort.

NỘI DUNG
Ôn tập.
3.1- Giới thiệu
3.2- Kỹ thuật tìm kiếm.
3.3- Một số kỹ thuật sắp thứ tự
3.4- Một số phép toán trên ma trận
Tóm tắt.

Ôn tập
•
Quản lý mảng tĩnh: Tính toán được vùng nhớ
cho mảng ngay lúc biên dịch (tĩnh)

•
Khai báo: int a[100] , n;
Số phần tử tối đa. Dựa trên số phần
tử này và kích thước của kiểu phần
tử. Vùng nhớ cho mảng được ấn
định ngay lúc biên dịch
Số phần tử thực tê đangdùng.
Nhờ trị của n chúng ta viết
code để duyệt mảng đúng giải
thuật
•
Nhược điểm của mảng tĩnh
Hiệu suất sử dụng bộ nhớ thấp- Khai báo tối
đa 100 phần tử nhưng có thể chỉ dùng 5 phần
tử  Hiệu suất sử dụng bộ nhớ là 5%

Ôn tập- Chương trình minh họa
mảng tĩnh
Viết chương trình:
nhập 1 mảng int, xuất mảng đã nhập

Ôn tập
•
Quản lý mảng động: Không tính toán
được vùng nhớ cho mảng ngay lúc biên
dịch (tĩnh) mà chỉ tính toán được khi
chạy chương trình.
•
Khai báo: int *a , n;
•

Ưu điểm của mảng động: Hiệu suất sử
dụng bộ nhớ 100%

Ôn tập- Chương trình minh họa
mảng động
Viết chương trình:
nhập 1 mảng int, xuất mảng đã nhập

Ôn tập- Ma trận động
•
Viết chương trình nhập xuất 1 ma trận số
int.

3.1- Giới thiệu
•
Hầu hết các dữ liệu của các bài toán là
nhóm trị mà một phần tử có thể có cấu
trúc mô tả khác nhau .
•
Nhu cầu tìm kiếm/sắp xếp thông tin là nhu
cầu tự nhiên của con người.

Giới thiệu
•
Các điều kiện của qúa trình tìm kiếm:
–
Đã có một nhóm trị.
–
Một chút thông tin đã biết về nội dung cần tìm (dữ
liệu khóa- Key ).

•
Thí dụ 1: Lấy lý lịch (tìm) của nhân viên có mã số
“NV008”
•
Thí dụ 2: Lấy lý lịch (tìm) của nhân viên có tên “Nguyễn
Văn Xoài”.
•
Khi Key tìm kiếm là duy nhất, qúa trình tìm kiếm cho tối
đa một kết qủa (thí dụ 1).
•
Khi Key tìm kiếm không duy nhất, qúa trình tìm kiếm có
thể cho nhiều kết qủa (thí dụ 2, trong tổ chức có thể có
nhiều người tên “Nguyễn Văn Xoài”).

Giới thiệu
•
Kết qủa tìm kiếm là vị trí có thông tin cần tìm.
•
Vấn đề mô tả kết qủa của qúa trình tìm kiếm :
–
Nếu chỉ số nhận diện phần tử là 1 số nguyên:
thì kết qủa là 1 số nguyên ( trị -1 mô tả cho
kết qủa “không tìm thấy”, kết quả là tập các số
int nếu là tìm kiếm đa trị).
–
Nếu chỉ số nhận diện phần tử là 1 pointer: thì
kết qủa là 1 pointer ( pointer NULL mô tả cho
kết qủa “không tìm thấy”, kết qủa là tập các
pointer nếu là tìm kiếm đa trị)
•

Đếm số lần xuất hiện của một dữ liệu là một
“biến thể” của tác vụ tìm kiếm.

Giới thiệu
•
Mục tiêu của việc sắp xếp:
(1)Tạo khả năng tìm kiếm nhanh,
(2)Trình bầy dữ liệu cho đẹp mắt.
•
Bản chất của qúa trình sắp thứ tự là thay
đổi vị trí lưu trữ dữ liệu của mỗi phần tử
trong nhóm.
•
Có nhiều kỹ thuật sắp thứ tự.

3.2- Kỹ thuật tìm kiếm
•
Bài toán tìm kiếm tổng quát: Cho tập
record R
0
, R
1
, R
2
, , R
n-1
. Mỗi R
i
được kết
hợp với một khóa K

i
(field thứ i của mô tả
record). Tìm (các) vị trí record có khoá là
X đã biết.
•
Hai thuật toán tìm kiếm:
–
Tìm kiếm tuần tự (tuyến tính, Sequential
Searching).
–
Tìm kiếm nhị phân (Binary Searching).

3.2.1-Kỹ thuật tìm kiếm tuần tự
•
Bài toán: Có mảng a chứa 5 số int. Tìm vị
trí đầu có mặt trị x=3 trong mảng này.
Phát hiện a[4]=x , ngưng tìm , Kết qủa: 4
•
Trường hợp tốt nhất (x=8): Chỉ tốn 1 lần so sánh.
•
Trường hợp xấu nhất: x ở cuối mảng hoặc x không có
trong mảng: Tốn 5 lần so sánh.
•
Độ phức tạp O(n)
•
Kỹ thuật cổ điển nhưng hay dùng.

Cài đặt kỹ thuật tìm kiếm tuần tự
•
Thuật toán chung cho việc tìm tới

Đi từ phần tử đầu mảng a đến phần tử cuối
Nếu (a[i].K == x) return i;
return -1; // trường hợp không tìm thấy
•
Thuật toán chung cho việc tìm lui
Đi ngược từ phần tử cuối mảng a đến phần tử
đầu
Nếu (a[i].K == x) return i;
return -1; // trường hợp không tìm thấy

Cài đặt kỹ thuật tìm kiếm tuần tự
•
Tìm vị trí đầu có int x trong mảng int*a đang có int n
phần tử
int IndexOf (int x, int*a, int n)
{ for (register int i = 0; i<n ; i++)
if (a[i]==x) return i;
return -1;
}
•
Tìm vị trí cuối có int x trong mảng int*a đang có int n
phần tử
int LastIndexOf (int x, int*a, int n)
{ for (register int i = n-1 ; i>=0 ; i )
if (a[i]==x) return i;
return -1;
}

Cài đặt kỹ thuật tìm kiếm tuần tự
•

Mô tả 1nhân viên: Employee:<Code, Name,
Salary>
•
Cài đặt: Tìm vị trí đầu có nhân viên mang mã số
aCode trong danh sách List đang có int n nhân
viên
struct Employee
{ char Code[6], Name[40], long Salary; };
int Search (char* aCode , Employee* List, int n)
{ for (register int i=0; i<n; ++i)
if (strcmp(List[i].Code, aCode)==0) return i;
return -1;
}
Dữ liệu chuỗi ký tự nên phải so sánh
bằng hàm strcmp trong string.h

Cài đặt kỹ thuật tìm kiếm tuần tự
•
Xuất danh sách nhân viên có lương long
Sal trong danh sách List đang có int n
nhân viên.
void PrintSal (long Sal, Employee* List, int
n)
{ for (register int i=0; i<n; ++i)
if (List[i].Salary==Sal)
printf(“%-7s%-45s%10\n”, List[i].Code,
List[i].Name,
List[i].Salary);
}
Gióng hàng trái

cho đẹp

Cài đặt kỹ thuật tìm kiếm tuần tự
•
Đếm số lần có int x trong mảng int *a, int n
int Count (int x, int*a, int n)
{ register int Result=0;
for (register int i=0; i<n; ++i)
if (a[i]== x) Result++;
return Result;
}
Bài tập làm tại chỗ:
Đếm số nhân viên có lương trên 1000000.

Cài đặt kỹ thuật tìm kiếm tuần tự
•
Đếm số lần có int x trong ma trận int **m, có int d, c
dóng cột
int Count (int x, int**m, int d, int c)
{ register int Result=0 , i, j;
for (i=0; i<d; i++)
for (j=0; j<c; j++)
if (m[i][j]== x) Result++;
return Result;
}
Bài tập làm tại chỗ:
Tìm dòng cột đầu tiên có trị int x trong ma trận vuông m
chứa các số int. Gợi ý: Trả về 1 pointer chỉ đến 1 cấu
trúc mô tả vị trí.


Bài tập có hướng dẫn
Viết chương trình nhập 1 mảng số int , xuất mảng đã nhập,
nhập 1 trị int x, xuất số lần có x trong mảng.
void main()
{ int*a, n , x, c ;
Input(a,n);
printf(“Content of the array:”); Output(a,n);
printf(“Input an integer:”);
scanf(“%d”,&x);
c= Count(x,a,n,);
if (c==0) printf(“%d is not existed!”, x);
else printf(“%d was existed %d times”,x,c);
getch();
}
#include <stdio.h>
#include <conio.h>
void Input(int*& a, int &n)
{ }
void Output(int*a, int n)
{ }
int Count (int x, int*a, int n)
{ }

Bài tập
•
Viết chương trình: Nhập 1 ma trận các số
int, Nhập trị int x. Hãy cho biết x xuất hiện
trong ma trận bao nhiều lần, Hãy cho biết
dòng cột đầu tiên có x.
•

Viết chương trình nhập 1 danh sách nhân
viên <Code,Name,Salary>. Hãy xuất
danh sách <Code, Name,Salary> của các
nhân viên có Salary trên 1000000

3.2.2- Kỹ thuật tìm kiếm nhị phân
•
Nhóm trị nguồn đã
có thứ tự, giả sử
tăng dần.
•
Tại 1 thời điểm
giảm ½ số phần tử
trong tập trị cần
tìm.
•
Thí dụ bên đây chỉ
tốn 4 lần so sánh
đã xác định được
kết qủa là 7

Kỹ thuật tìm kiếm nhị phân
•
Thí dụ bên đây chỉ
mất 5 lần đã xác
định được x
không có trong
mảng

Kỹ thuật tìm kiếm nhị phân

•
Số lần so sánh tối đa log
2
n + 1
•
Nếu n = 2
m
thì
•
Lần Số phần tử được xét Số phép so
sánh
•
1 2
m
1
•
2 2
m-1
1
•
3 2
m-2
1
•
4 2
m-3
1
•
i 2
m-i-1

1
•
m+1 2
m-m
= 1 1
•
Độ phức tạp của kỹ thuật tìm kiếm nhị phân O
(log
2
n)