THÂN CHÀO TẬP THỂ LỚP VÀ QUÝ THẦY CÔ GIÁO






BÀI 4: GIỚI THIỆU THUẬT TOÁN
Tiết 13: Bài toán sắp xếp



GVTH: Nguyễn Ngọc Giao Ngôn


Giới thiệu bài toán sắp xếp
Những việc hằng ngày liên quan đến sắp xếp :
Sắp xếp sách vở .
Xếp hàng chào cờ .
Sắp xếp tên học sinh .
Xếp điểm trung bình của học sinh .
. . . . . .
Làm sao máy tính sắp xếp được như chúng ta ?
Nạp chương trình sắp xếp vào máy.
Xây dựng thuật toán sắp xếp cho máy.
Giới thiệu bài toán sắp xếp
Ta xét bài toán dạng đơn giản sau :
Cho dãy số nguyên A gồm n phần tử :
a1 , a2 , a3 , . . . , an
?Vấn đề đặt ra là cần bố trí lại các phần tử của A sao cho sau khi sắp xếp xong thì A trở thành dãy không giảm , nghĩa là điều kiện ai ai+1 với 0 ?Ví dụ : dãy A có 6 phần tử :15 ; 8 ; 12 ; 11 ; 13 ; 9
dãy sau khi sắp xếp: 8 ; 9 ; 11 ; 12 ; 13 ; 15
15
8
12
11
13
9
Nhận xét:
Tiến hành duyệt từ trái sang với hai số đứng liền kề nhau nếu số đứng sau bé hơn số đứng trước thì tiến hành đổi chỗ.
Sau mỗi lần đổi chỗ ,Phần tử lớn nhất sẽ chuyển dần về cuối dãy.
Sau một lần duyệt ,Phần tử lớn nhất sẽ nằm ở cuối dãy.
Việc đó lặp đi lặp lại cho đến khi mọi phần tử trong dãy đều đã xếp đúng thứ tự (số đứng sau không bé hơn số đứng trước)


Quan sát và cho nhận xét cách sắp xếp trên


15
8
12
11
13
9
15
8
12
11
13
9
Nhập vào N và dãy N phần tử.
Dùng biến i để thực hiện việc so sánh các phần tử kề nhau từ trái qua ,Nếu ai>ai+1 thì tráo đổi và tăng i lên để so sánh với phần tử tiếp theo.
Dùng biến M để kiểm tra quá trình sắp xếp ,ban đầu M=N,khi i > M thì kết thúc một lần duyệt ;sau một lần duyệt thì số phần tử chưa sắp xếp giảm đi 1 tức là M giảm đi 1.
Khi M=1 (chỉ còn một phần tử chưa sắp xếp),đưa ra dãy đã sắp xếp rồi kết thúc.







Bước 1: Nhập N và các số hạng a1 , a2 ,. . . , aN
Bước 2: M N
Bước 3: Nếu M < 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc.
Bước 4: M M-1 ; i 0
Bước 5: i i+1
Bước 6: Nếu i > M thì quay lại bước 3.
Bước 7: Nếu ai>ai+1 thì hoán đổi ai và ai+1 cho nhau.
Bước 8: Quay lại bước 5.












Nhập N và
a1 ,a2 ,. . . . ,an
Hoán vị ai và ai+1
Đưa ra A rồi kết thúc
Đúng
Sai
M < 2
i > M ?
ai > ai+1
Sai
Đúng
Sai
Đúng
Đưa ra A rồi kết thúc
M < 2
i > M ?
M =
M = ; i =
i =
Dãy 6 phần tử 15;8;12;11;13;9
6
a1 > a2
Hoán vị a1 và a2
15
8
5
0
5
15
8
12
11
13
9
1
2
a2 > a3
Hoán vị a2 và a3
15
12
3
a3 > a4
Hoán vị a3 và a4
15
11
4
a4 > a5
Hoán vị a4 và a5
15
13
a5 > a6
Hoán vị a5 và a6
15
9
6
4
1
a1 > a2
8
12
2
a2 > a3
Hoán vị a2 và a3
12
11
3
a3 > a4
12
13
4
a4 > a5
Hoán vị a4 và a5
13
9
5
3
1
a1 > a2
8
11
2
a2 > a3
11
12
3
a3 > a4
Hoán vị a3 và a4
12
9
4
2
1
a1 > a2
8
11
2
a2 > a3
Hoán vị a2 và a3
11
9
3
1
1
a1 > a2
8
9
2
CỦNG CỐ
Giả sử ta có danh sách tên học sinh của một tổ học tập là:
Tuấn ; Phan ; Nam ; Hà ; Lan ; Bình ; Xuân.
Câu 1: Danh sách nào dưới đây là kết quả sau lần duyệt thứ nhất khi thực hiện thuật toán sắp xếp Bubble sort.
a. Tuấn ; Phan ; Nam ; Hà ; Lan ; Bình ; Xuân.
b. Phan ; Tuấn ; Hà ; Nam ; Bình ; Lan ; Xuân.
c. Phan ; Nam ; Hà ; Lan ; Bình ; Tuấn ; Xuân.
d. Xuân ; Tuấn ; Phan ; Nam ; Hà ; Lan ; Bình.

Nam
Hà
Lan
Bình
Xuân
Tuấn
Phan
Trả lời
Đáp án : C
Câu 2: Với danh sách trên ,thuật toán cần phải thực hiện bao nhiêu lần duyệt danh sách ?

Nam
Hà
Lan
Bình
Xuân
Tuấn
Phan
LẦN DUYỆT THỨ
ĐÁP ÁN : D
A. 4 lần
C. 6 lần
B. 5 lần
D. 7 lần