I. Định nghĩa:
II. Các thuật toán cơ bản:
! Các thuật toán:
CHƯƠNG II: CÁC THUẬT TOÁN TÌM KIẾM
– Tìm kiếm tuyến tính – Tìm kiếm nhị phân
! Tìm kiếm là kỹ thuật tìm kiếm một phần tử x bất kỳ có mặt trong một dãy các phần tử đã có hay không? – Tìm thấy trả lại vị trí – Không tìm thấy trả lại giá trị -1
X = 5
2
3
4
5
6
7
8
X = 9
8/4/16
1
2
4
8/4/16
CTDL –
CNTH – Viện ĐH Mở
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
c. Cài đặt thuật toán:
b. Minh họa thuật toán
1. Thuật toán tìm kiếm tuyến tính:
! Đ/n hàm LineSearch – Input:
9 Chưa Đã tìm hết thấy tại mảng vị trí 4
! Minh họa tìm x =9 9 6 0
2
5 11 41 9 32 13 8 14 3 9 5 1
6
3
4
7
8
a. Ý tưởng: ! Lần lượt duyệt từ đầu mảng đến cuối mảng, mỗi lần so sánh phần tử cần tìm x với phần tử tương ứng của mảng (a[i])
! phần tử x ! mảng a có n phần tử.
– Output:
! Minh họa tìm x =27
27
! vị trí đầu tiên tìm thấy phần tử x ! hoặc trả lại giá trị -1 nếu không tìm thấy.
Chưa Đã hết hết mảng mảng
6
6 0
5 11 41 9 32 13 8 14 3 9 5 1
6
2
3
4
7
8
5
6
7
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
d. Đánh giá thuật toán:
b. Minh họa thuật toán
2. Thuật toán tìm kiếm nhị phân
! Độ phức tạp là: O(n)
x x x
Minh họa tìm x = 41 3 14 16 19 22 41 46 51 63 71 3 14 16 19 22 41 46 51 63 71 3 14 16 19 22 41 46 51 63 71 3 14 16 19 22 41 46 51 63 71 10 10 1 1 10 1 10 1
2 2 2 2
3 3 3 3
4 4 4 4
5 5 5 5
6 6 6 6
7 7 7 7
8 8 8 8
9 9 9 9
l m m r Tìm thấy x tại vị trí 6
A. Ý tưởng ! Xét dãy đã có thứ tự (tăng hoặc giảm) ! So sánh giá trị x với phần tử giữa của dãy tìm kiếm hiện hành. Dựa vào giá trị này sẽ quyết định giới hạn dãy tìm kiếm ở bước kế tiếp là nửa trước hay nửa sau của dãy hiện hành
m
10
8
9
10
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
* Các bước thực hiện thuật toán:
c. Mô tả thuật toán:
! Input:
x – là giá trị cần tìm n – số phần tử mảng a – mảng chứa các phần tử đã được sắp
x x x x
Minh họa tìm x = 45 3 14 16 19 22 41 46 51 63 71 3 14 16 19 22 41 46 51 63 71 3 14 16 19 22 41 46 51 63 71 3 14 16 19 22 41 46 51 63 71 3 14 16 19 22 41 46 51 63 71 10 1 10 1 10 1 10 1 10 1
3 3 3 3 3
2 2 2 2 2
4 4 4 4 4
5 5 5 5 5
6 6 6 6 6
7 7 7 7 7
8 8 8 8 8
9 9 9 9 9
xếp tăng dần
left, right – là chỉ số đầu và chỉ số cuối
! Bước 1: Khởi đầu tìm kiếm trên tất cả các phần tử của dãy (left = 0 và right = n – 1) ! Bước 2: Tính middle = (left + right)/2. So sánh a[middle] với x. Có 3 khả năng: " a[middle] = x ⇒ Tìm thấy => Dừng " a[middle] > x ⇒ right = middle – 1 (tìm trong nửa đầu) " a[middle] < x ⇒ left = middle + 1 (tìm trong nửa cuối)
của mảng thực hiện tìm
! Bước 3:
l m m r
! Output:
vị trí chứa phần tử x (nếu có)
m l > r: Kết thúc Không tìm thấy
m " Nếu left ≤ right ⇒ quay lại bước 2 để tìm kiếm tiếp " Ngược lại ⇒ Dãy hiện hành hết phần tử (không tìm thấy) và dừng thuật toán
11
11
12
13
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
III. Bài tập áp dụng:
e. Ví dụ minh họa:
d. Cài đặt thuật toán:
8
9
5
6
8
2
! Đ/n hàm BinarySearch – Input:
10
4
8
9
! phần tử x ! mảng a có n phần tử.
! Cho dãy số a: a = 2 3 4 5 6 7 tìm xem phần tử x = 8 có trong dãy không? Yêu cầu mô tả chạy từng bước theo thuật toán
– Output:
! Tìm phần tử x=4 trong dãy sau: 4 7 ! Tìm phần tử x = 2 trong dãy sau: 6 1 Yêu cầu: mô tả từng bước thuật toán tìm kiếm nhị phân
! vị trí đầu tiên tìm thấy phần tử x ! hoặc trả lại giá trị -1 nếu không tìm thấy.
Left Right Middle Trạng thái
14
15
18
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
CHƯƠNG III: CÁC THUẬT TOÁN SẮP XẾP
# Nhận xét: – Giải thuật tìm nhị phân dựa vào quan hệ giá trị của các phần tử mảng để định hướng trong quá trình tìm kiếm, do vậy chỉ áp dụng được cho những dãy đã có thứ tự. – Giải thuật tìm nhị phân tiết kiệm thời gian hơn rất nhiều so với giải thuật tìm tuần tự do Tnhị phân (n) = O(log 2 n) < Ttuần tự (n) = O(n).
# Nhận xét: – Khi muốn áp dụng giải thuật tìm nhị phân cần phải xét đến thời gian sắp xếp dãy số để thỏa điều kiện dãy số có thứ tự. Thời gian này không nhỏ, và khi dãy số biến động cần phải tiến hành sắp xếp lại => khuyết điểm chính cho giải thuật tìm nhị phân. – Cần cân nhắc nhu cầu thực tế để chọn một trong hai giải thuật tìm kiếm trên sao cho có lợi nhất.
8/4/16
21
19
20
I. Định nghĩa:
II. Các thuật toán cơ bản
1. Sắp xếp chọn trực tiếp
! Cho các phần tử a1, a2, …, an bất kỳ ! Sắp xếp là quá trình bố trị lại các phần tử theo một thứ tự thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thông tin lưu giữ tại mỗi phần tử.
a. Ý tưởng: ! Tại mỗi bước chọn ra phần tử nhỏ nhất hoặc lớn nhất trong số các phần tử chưa xét và đưa về vị trí thích hợp, cố định phần tử này không xét lại nữa.
! Sắp xếp chọn trực tiếp – Selection Sort ! Sắp xếp chèn trực tiếp – Insertion Sort ! Sắp xếp nổi bọt – Bubble Sort ! Sắp xếp phân hoạch – Quick Sort ! Sắp xếp đổi chỗ trực tiếp – Interchange Sort ! Sắp xếp với số bước giảm dần – Heap Sort ! Sắp xếp trộn – Meger Sort
22
23
24
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
b. Minh Họa Thuật Toán Chọn Trực Tiếp
Hoandoi( a[0], a[4] )
Hoandoi(a[1], a[1])
Hoandoi(a[2], a[6])
Vị trí nhỏ nhất trong đoạn(0,7)
Vị trí nhỏ nhất trong đoạn(1,7)
Vị trí nhỏ nhất trong đoạn(2,7)
min
min
min
12 2 8 5 1 6 4 15 8 5 12 6 4 15 2 1
12
15
8
1
2
5
6
4
0 1 2 3 4 5 6 7 2 3 4 5 6 7 1 0
2
0
3
4
5
6
7
i
1 i
i
25
26
27
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
Hoandoi(a[3], a[3])
Hoandoi (a[4], a[5])
Vị trí nhỏ nhất trong đoạn(3, 7)
Vị trí nhỏ nhất trong đoạn (4, 7)
Vị trí nhỏ nhất trong đoạn(6, 7)
min
min
min
15 1 2 4 6 8 15 1 2 4 5 6 12 5 12 12 15 15 8
12
5
1
2
4
6
8
0 1 2 5 6 7 4 3 0 1 2 3 4 6 7 5
3
0
1
4
5
6
7
i i
2 i
28
29
31
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
8/4/16
CTDL – Khoa CNTH – Viện ĐH Mở
c. Mô tả thuật toán:
d. Cài đặt thuật toán:
void SelectionSort_Asc( int a[ ], int n ) {
! Định nghĩa hàm SelectionSort_Asc – Input
! Mảng a gồm n phần tử (nguyên)
– Output
int min, i, j, tg;
for( i=0 ; i min = i;
for( j=i+1 ; j ! Mảng đã sắp xếp (tăng dần). ! Tổng quát sắp xếp tăng dần
! Bước 1: i = vị trí đầu (i = 0)
! Bước 2: tìm chỉ số min là phần tử nhỏ nhất
trong dãy hiện hành từ a[i] đến a[n-1]
! Bước 3: Hoán vị a[i] với a[min]
! Bước 4: • nếu i if( min != i ) //Hoán đổi a[min] với a[i]
{
tg=a[min]; a[min]=a[i]; a[i]=tg;
} } } 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở ! Độ phức tạp là O(n2) ! Cho dãy số sau:
a = 5 6 2 10 1 3
Yêu cầu mô tả từng bước sắp xếp dãy tăng dần,
giảm dần bằng thuật toán SelectionSort I Min Hoán đổi Kết quả I = 0 I = 1 I = 2 I = 3 I = 4 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 2 3 4 5 6 7 0 1 0 1 3 4 5 6 7 2 0 1 2 4 5 6 7 3 7 5 7 7 3 9 2 1 5 3 9 2 1 5 9 2 1 3 i=1 i=2 i=3 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 0 1 2 3 5 6 7 4 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 5 7 3 5 2 3 3 2 1 9 2 7 9 1 1 5 7 9 i=4 i=7 i=8 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở ! Định nghĩa hàm InsertionSort_Asc
– Input ! Mảng a gồm n phần tử (nguyên) ! Bước 1: i = 1
! Bước 2:
– x = a[i],
– tìm vị trí pos thích hợp trong đoạn từ a[0] đến a[i-1] để chèn a[i] vào – Output ! Bước 3: dịch chuyển các phần tử từ a[pos] đến a[i-1] ! Mảng đã sắp xếp (tăng dần). sang phải một vị trí để được vị trí chèn a[i] vào ! Bước 4: chèn a[i] vào vị trí pos vừa tìm được bằng Vừa tìm vị trí để chèn vừa
dịch chuyển các phần tử ra
cuối dãy một vị trí (a[pos] = x) //chèn x vào dãy ! Bước 5: i = i+1 - Nếu i => Lặp lại bước 2
=> Dừng thuật toán 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở ! ! Cho dãy số sau:
a = 5 3 2 7 4 1
Mô tả tùng bước sắp xếp dãy tăng dần – giảm dần
bằng InsertionSort ! Tự lấy bộ 7 phần tử ngẫu nhiên
! Thực hiện sắp xếp bằng Selection và
Insertion tăng dần và giảm dần
! Mô phỏng từng bước $ lập bảng I Pos Dịch chuyển phải Kết quả I = 1 I = 2 I = 3 I = 4 I = 5 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 1 1 i i 5 2 i 7 5 5 3 7 7 9 3 2 9 3 2 9 1 j j j 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 1 1 1 2 2 2 3 3 3 i 5 5 i 5 7 i 7 7 9 9 9 j j j 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 1 1 2 2 3 3 ! Bước 1: i = 0
! Bước 2: j = n - 1
Trong khi j>i thực hiện
{ 5 5 7 7 nếu a[j] < a[j-1] thì hoán đổi hai phần tử
j = j – 1 9 9 } i ! Bước 3: i = i + 1 i j Nếu i > n-2: dừng thuật toán
Ngược lại: lặp lại bước 2 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở ! Định nghĩa hàm BubbleSort_Asc
– Input ! Mảng a gồm n phần tử (nguyên) – Output ! Mảng đã sắp xếp (tăng dần). tg = a[ j ];
a[ j ] = a[ j-1];
a[ j-1 ] = tg; for( j = n-1 ; j>i ; j-- )
if ( a[ j ] < a[ j-1] )
{
} int i,j,tg;
for( i = 0 ; i ! Cho dãy số sau:
a = 5 6 2 1 9 3
Mô tả từng bước thực hiện sắp xếp dãy tăng dần – giảm
dần bằng BubbleSort I J Hoán đổi Kết quả 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở right right left left ! Mọi phần tử nhỏ hơn “chốt” được xếp vào vị trí trước
! Mọi phần tử lớn hơn “chốt” được xếp vào vị trí sau Không nhỏ hơn x Không lớn hơn x Không nhỏ hơn x Không lớn hơn x 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 83 84 right right right left left left Không nhỏ hơn x Không lớn hơn x 85 86 87 i = 0, j = 7 i = 3, j = 7 x x L L R R 2 3 5 7 3 1 5 10 9 2 15 1 9 7 15 10 0 3 1 2 4 5 6 7 0 1 2 4 3 6 7 5 i j i j L=0
R=7 Đoạn 2 Đoạn 1 Đoạn 2 L=3
R=7
L=0
R=2 L = 0
R = 2 L = 3
R = 7 L = 3
R = 3 L = 4
R = 7 Đoạn cần sắp xếp Đoạn cần sắp xếp 88 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở x i = 4, j = 7 i = 5, j = 7 i = 5, j = 6 x x L L L R R R 0 1 2 3 4 0 1 2 3 4 5 6 7 5 6 7 0 1 2 3 5 6 4 7 2 3 2 3 2 3 1 5 7 1 5 7 9 1 5 7 9 10 10 15 10 9 i j i j i j L=5
R=6 L=5
R=7 L=4
R=7 L=3
R=3 L=3
R=3 L=3
R=3 Đoạn 1 Đoạn 2 L=0
R=2 L=0
R=2 L=0
R=2 L = 5
R = 6 L = 5
R = 7 Đoạn cần sắp xếp Đoạn cần sắp xếp Đoạn cần sắp xếp 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở x i=0, j=2 i=3, j=3 L L x R 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 3 0 1 2 4 5 6 7 3 2 3 2 3 2 1 5 7 9 1 5 7 9 5 1 7 9 R i j L=3
R=3 L=0
R=2 L=0
R=2 Đoạn cần sắp xếp Đoạn cần sắp xếp Đoạn cần sắp xếp 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở (cid:1)Phân hoạch bài toán: ! Được thực hiện gồm hai phần: j = R; i = L; ! Định nghĩa hàm QuickSort_Asc
– Input – Phân hoạch bài toán
– Sắp xếp trên từng phân hoạch ! Bước 1: chọn tùy ý phần tử chốt x = a[k] trong dãy aL, a2,…,aR.
(k = (L+R)/2 )
! Bước 2: phát hiện và điều chỉnh các phần tử a[i] và a[j] sai vị
trí: ! Mảng a gồm n phần tử (nguyên)
! Chỉ số đầu (Left) và chỉ số cuối (Right) – Output a. Trong khi a[i] ! Mảng đã sắp xếp (tăng dần). - Hoán vị a[i] và a[j]
- i++;
j--;
! Bước 3:
- Nếu i 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở a = 12 2 8 5 1 6 4 15 Mô tả từng bước Sắp xếp dãy tăng dần – giảm dần ! Cho dãy số a: int QuickSort( int a[ ], int L , int R )
{ if (L void quickSort( int a[], int L, int R)
{
int mid = PhanHoach(a, L, R);
if (L< mid - 1)
quickSort(a, L, mid - 1);
if (mid< R)
quickSort(a, mid, R);
} Hoanvi( a[i] , a[j] );
i++; j--; while ( a[i] < x ) i++;
while ( a[j] > x ) j--;
if ( i <= j )
{
} int i,j,x;
x = a[(L+R)/2];
i = L; j = R;
do
{
} while(i<=j); 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở ! Là thuật toán đảm bảo trường hợp xấu nhất
thời thời gian cũng là O(nlogn)
! Ý tưởng: thực hiện sắp xếp thông qua việc
tạo ra các cây Heap tại mỗi bước
– Cây Heap là cây nhị phân mà khóa ở nút cha
bao giờ cũng lớn hơn các khóa ở nút con ! Các bước thực hiện:
1. Tạo cây Heap từ dãy ban đầu
2. Sắp xếp dựa trên cây Heap đã được tạo 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở ! Ví dụ: cho dãy gồm: 35, 20, 52, 101, 9, 28.
Thực hiện sắp xếp dãy bằng HeapSort
– Giảm dần
– Tăng dần 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở ! Khai báo cấu trúc SV gồm: mã SV, Họ tên, Tuổi, Điểm trung bình
! Viết các CTC thực hiện: 7, 4, 8, 9, 3, 1, 6, 2 ! Sắp xếp danh sách L gồm 8 phần tử 7, 4, 8, 9, 3, 1,
6, 2 7, 4, 8, 9 3, 1, 6, 2 ! Ý tưởng:
– Tìm cách phân hoạch dãy ban đầu thành các dãy con.
Sau khi phân hoạch xong, ta trộn từng cặp dãy con của
hai dãy phụ thành một dãy con của dãy ban đầu. 7, 4 8, 9 3, 1 6, 2 7 4 8 9 3 1 6 2 4, 7 8, 9 1, 3 2, 6 – Nhập vào một mảng các sinh viên
– In lại mảng các sinh viên đã nhập
– Lưu DSSV vào File
– Đọc DSSV tư File
– Tìm kiếm sinh viên có mã là x bằng tt tìm kiếm tuyến tính
– Tìm kiếm sinh viên có tên là x
– SX dãy danh sách SV giảm dần theo ĐTB bằng một trong các TT
sắp xếp
– SX dãy DSSV tăng dần theo Tuổi bằng một trong các TT SX ! Áp dụng: 4, 7, 8, 9 1, 2, 3, 6 ! Thuật toán:
– Với dãy ban đầu có n phân tử, ta cứ phân hoạch thành n
dãy con. Vì rằng mỗi dãy con chỉ có 1 phần tử nên nó là
dãy có thứ tự.
– Sau đó trộn các dãy con lại với nhau theo nguyên tắc sắp
xếp – Áp dụng lại các CTC trên 1, 2, 3, 4, 6, 7, 8, 9 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở ! Đọc và nghiên cứu trước giáo trình phần:
– Thuật toán sắp xếp (Bubble – Quick - Interchange)
– Mỗi thuật toán xác định: ! Xem lại ngôn ngữ Lập trình C
– Khai báo biến
– Các cấu trúc điều khiển cơ bản
– Cấu trúc – struct
– … ! Ý tưởng
! Các bước thực hiện
! Đánh giá độ phức tạp thuật toán
! Lấy ví dụ minh họa ! Bài tập lớn – viết ra giấy
– Xác định đối tượng dữ liệu đầu vào cần quản lý (các thành
phần và kiểu tương ứng)
– Lấy bộ dữ liệu mẫu có ý nghĩa (tối thiêu 10 bộ)
– Làm theo nhóm (ghi rõ họ tên + lớp) 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở ! Cài đặt bài tập lớn bằng mảng
! Yêu cầu: – Xây dựng cấu trúc đối tượng được quản lý
– Cài đặt các thao tác với danh sách (mỗi thao tác tương ứng với
một CTC) – email: trinhxuan@gmail.com
– Subject: CTDL - ! Nhập 1 đối tượng - In 1 đối tượng
! Nhập 1 mảng đối tượng - In lại 1 mảng đối tượng
! Tìm kiếm một đối tượng nào đó theo mã, …
! In danh sách các đối tượng theo điều kiện nào đó
! Sắp xếp các đối tượng theo tiêu chí nào đó
! Đếm các phần từ theo một điều kiện nào đó
! … (tối thiểu 10 CTC khai thác) – Chương trình chính (áp dụng các CTC đã cài đặt trên) 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở 8/4/16 CTDL – Khoa CNTH – Viện ĐH Mở32
34
35
f. Ví dụ minh họa
2. Sắp xếp chèn trực tiếp
e. Đánh giá giải thuật
a. Ý tưởng
! Cho dãy ban đầu a0, a1 ,... ,ai-1 đã được
sắp xếp
! Xét phần tử ai
! Tìm trong dãy a0, a1 ,... ,ai-1 vị trí thích hợp
để chèn ai vào sao cho dãy a0, a1 ,... ,ai-1, ai
được sắp xếp
36
36
37
39
b. Minh họa thuật toán
Tìm vị trí chèn cho phần tử thứ a[1]
Tìm vị trí chèn cho phần tử thứ a[2]
Tìm vị trí chèn cho phần tử thứ a[3]
10
10
15
10
15
15
41
42
40
40
41
42
Tìm vị trí chèn cho phần tử thứ a[4]
Tìm vị trí chèn cho phần tử thứ a[7]
Kết thúc
10
15
10
15
10
15
43
46
47
43
46
47
c. Mô tả thuật toán:
d. Cài đặt thuật toán:
a[pos+1] = a[pos];
pos--;
x = a[i];
pos = i-1;
while((pos>=0)&&(a[pos]>x))
{
}
a[pos+1] = x;
void InsertionSort( int a[ ], int n )
{
int pos,i,x;
for(i=1;i
48
50
51
f. Ví dụ minh họa:
Bài tập về nhà
3. Sắp xếp nổi bọt - BubbleSort
a. Ý tưởng
xuất phát từ đầu dãy (hoặc cuối dãy) và tiến hành
đổi chỗ cặp phần tử kế cận nhau để đưa phần
tử nhỏ hơn hoặc lớn hơn về vị trí cao nhất hay
thấp nhất trong dãy. Sau khi đã chuyển vị trí này
không xét nữa
53
54
57
10
0
0
0
10
1
1
1
10
2
2
2
3
3
3
4
4
4
5
5
5
15
6
6
6
15
15
7
7
7
66
68
67
66
67
68
0
0
0
1
1
1
2
2
2
10
3
3
3
10
4
4
4
10
5
5
5
6
6
6
15
15
15
7
7
7
69
71
70
69
70
71
c. Mô tả thuật toán:
0
0
1
1
2
2
3
3
Kết
thúc
4
4
5
5
10
10
6
6
15
15
7
7
72
73
72
73
74
d. Cài đặt thuật toán:
f. Ví dụ minh họa:
void BubbleSort(int a[ ], int n)
{
76
77
79
4. Sắp xếp QuickSort
b. Minh họa thuật toán
Phân hoạch dãy
Phân hoạch dãy
X
X
5
5
i
0
1
2
3
4
5
6
j
7
0
i
1
2
3
4
j
5
6
7
12
2
8
5
1
6
4
15
4
2
8
5
1
6
12
15
a. Giới thiệu:
! QuickSort là phương pháp sắp xếp tốt nhất
! ý tưởng:
– Chọn một phần tử ngẫu nhiên nào đó của dãy làm
“chốt”,
– Các phần tử của dãy được so sánh với “chốt” và đổi
chỗ cho nhau
STOP
STOP
STOP
STOP
82
Phân hoạch dãy
X
6
1
0
3
i
4
5
6
7
j
2
0
1
2
3
5
6
j
7
i
4
0
1
2
3
j
4
i
5
6
7
2
4
5
8
6
12
15
1
1
2
4
5
6
12
15
8
1
2
4
5
6
8
12
15
Sắp xếp đoạn 3
Sắp xếp đoạn 3
STOP
STOP
0
1
2
3
4
5
6
7
12
1
2
4
5
6
8
1
5
Đoạn 1
90
91
90
91
15
15
92
93
94
92
93
94
10
15
10
15
10
15
Không còn đoạn
nào cần sắp xếp!
Kết thúc
95
96
97
95
96
97
c. Mô tả thuật toán
d. Cài đặt thuật toán:
98
99
100
e. Ví dụ minh họa:
101
104
105
6. Sắp xếp kiểu vun đống - HeapSort
*Nguyên tắc tạo cây Heap
*Thực hiện sắp xếp trên cây Heap
! Lấy phần tử đầu (là phần tử lớn nhất của
cây) và thay thế bằng phần tử cuối của cây.
– Có thể làm vi phạm định nghĩa Heap cần phải
chỉnh lại cây Heap ngay
– Nguyên tắc: Thay thế nút vi phạm với nút con
lớn hơn. Nếu cây vẫn vi phạm định nghĩa Heap
thì lặp lại quá trình cho tới khi nó lớn hơn cả 2
nút con hoặc trở thành nút lá
! Phần tử đầu tiên trong mảng trở thành phần
tử gốc của Heap ban đầu,
! Lần lượt lấy từng phần tử của mảng bổ sung
lần lượt vào nhánh trái và nhánh phải của
Heap.
! Mỗi khi bổ sung kiểm tra thỏa mãn tính chất
của Heap (phần tử gốc phải lớn hơn các
phần tử con của Heap).
– Nếu vi phạm vị trí nào thì thực hiện hoán đổi
! Quá trình lặp liên tiếp đến khi lấy hết các
phần tử của cây.
123
124
125
Tạo cây Heap: 35, 20, 52, 101, 9, 28, 56, 64
126
127
128
7. Sắp xếp Mergesort
Bài tập về nhà
131
132
134
Bài tập về nhà buổi 2
Bài tập về nhà buổi 3
135
136
137
– Cách thức nộp bài:
! Viết ra giấy: nộp cho GV đầu giờ học buổi
03/10/13
! Hoặc Viết code: gửi mail trước trước 21h - ngày
02/10/13
138
139
