2
KHOA CÔNG NGHỆ THÔNG TIN
3
KHOA CÔNG NGHỆ THÔNG TIN
// a[0], a[1] là cặp nghịch thế
34
3
4
8
4
KHOA CÔNG NGHỆ THÔNG TIN
5
KHOA CÔNG NGHỆ THÔNG TIN
6
KHOA CÔNG NGHỆ THÔNG TIN
7
KHOA CÔNG NGHỆ THÔNG TIN
• Cho 1 dãy các phần tử như sau: {5, 1, 6, 2, 4, 3}
Lượt 2 Lượt 1 Lượt 3
1
2
5
4
3
6
3
4
2
1
5
6
1 5 2 4 3 6 1 6 2 4 5 3 4 3 2 1 5 6
5 6 2 4 1 3
1 2 4 5 3 6 3 4 2 1 5 6 5 2 6 4 1 3
1
5
2
4
6
3
3 4 2 1 5 6 1 2 4 3 5 6
1 5 2 4 3 6 1 2 4 3 5 6 1 2 3 4 5 6
8
KHOA CÔNG NGHỆ THÔNG TIN
Input: Dãy các đối tượng (Các số chưa sắp xếp): A[0], A[1],…,A[n-1]. Output: Dãy các đối tượng đã được sắp xếp (Các số tăng dần): A[0], A[1],…,A[n-1] Actions:
void BubbleSort(int a[],int n)
{
int
i, j;
for (i = 0 ; i< n-1 ; i++)
for (j =i ; j > n-1 ; j ++)
if(a[j]< a[j1]) // nếu sai vị trí thì đổi chỗ
Swap(a[j], a[j+1]);
9
} End KHOA CÔNG NGHỆ THÔNG TIN
#Giải thuật Nổi bọt - Bubble Sort:
B.1: Gán i = 0
B.2: Gán j = 0
//danh sách có n phần tử a0,a1,a2…,an-1
B.3: Nếu A[j] > A[j + 1] thì Hoán đối chỗ giữa A[j] và A[j + 1]
B.4: Nếu (j < n – i – 1):
-Đúng thì j = j + 1 và quay lui bước 3
-Sai thì chuyển sang bước 5
B.5: Nếu (i < n – 1):
-Đúng thì i = i + 1 và quay lui bước 2
-Sai thì dừng Kết Thúc.
10
KHOA CÔNG NGHỆ THÔNG TIN
11
KHOA CÔNG NGHỆ THÔNG TIN
Bài tập 2: Áp dụng giải thuật sắp xếp Nổi bọt – Bubble Sort. Thực hiện sắp xếp mảng: A = [39, 25, 16, 20]
12
KHOA CÔNG NGHỆ THÔNG TIN
* Đánh giá độ phức tạp - thuật toán Bubble Sort
void BubbleSort() {
int i, j ; for (i = 2; i <= n; i++)
if (a[j-1] > a[j]) //hoán chuyển
for ( j = n; j >= i; j--)
}
swap(&a[j-1], &a[j]);
13
KHOA CÔNG NGHỆ THÔNG TIN
14
KHOA CÔNG NGHỆ THÔNG TIN
-Sắp xếp chèn là một giải thuật sắp xếp dựa trên so sánh tại chỗ.
-Một danh sách con luôn luôn được duy trì dưới dạng đã qua sắp
xếp. Sắp xếp chèn là chèn thêm một phần tử vào danh sách con đã
qua sắp xếp.
-Phần tử được chèn vào vị trí thích hợp sao cho vẫn đảm bảo rằng
danh sách con đó vẫn sắp xếp theo thứ tự.
-Giải thuật này không thích hợp sử dụng với các tập dữ liệu lớn khi
độ phức tạp trường hợp xấu nhất và trường hợp trung bình là Ο(n2)
với n là số phần tử.
15
KHOA CÔNG NGHỆ THÔNG TIN
Ví dụ: cho một mảng gồm các phần tử không có thứ tự: 14 – 33 – 27 – 10 – 35 – 19 – 42 - 44 -Giải thuật sắp xếp chèn so sánh hai phần tử đầu tiên: 14 – 33 – 27 – 10 – 35 – 19 – 42 - 44 -Giải thuật tìm ra rằng cả 14 và 33 đều đã trong thứ tự tăng dần. Bây giờ, 14 là trong danh sách con đã qua sắp xếp. 14 – 33 – 27 – 10 – 35 – 19 – 42 - 44 -Giải thuật sắp xếp chèn tiếp tục di chuyển tới phần tử kế tiếp và so sánh 33 và 27. 14 – 33 – 27 – 10 – 35 – 19 – 42 - 44 -Và thấy rằng 33 không nằm ở vị trí đúng. 14 – 33 – 27 – 10 – 35 – 19 – 42 - 44 -Giải thuật sắp xếp chèn tráo đổi vị trí của 33 và 27. Kiểm tra tất cả phần tử trong danh sách con đã sắp xếp. Thấy rằng trong danh sách con này chỉ có một phần tử 14 và 27 là lớn hơn 14. Do vậy danh sách con vẫn giữ nguyên sau khi đã tráo đổi. 14 – 27 – 33 – 10 – 35 – 19 – 42 - 44 -Danh sách con chúng ta có hai giá trị 14 và 27. Tiếp tục so sánh 33 với 10. 14 – 27 – 33 – 10 – 35 – 19 – 42 - 44
16
KHOA CÔNG NGHỆ THÔNG TIN
-Hai giá trị này không theo thứ tự. 14 – 27 – 33 – 10 – 35 – 19 – 42 - 44 -Vì thế chúng ta tráo đổi chúng. 14 – 27 – 10 – 33 – 35 – 19 – 42 - 44 -Việc tráo đổi dẫn đến 27 và 10 không theo thứ tự. 14 – 27 – 10 – 33 – 35 – 19 – 42 - 44 -Vì thế chúng ta cũng tráo đổi chúng. 14 – 10 – 27 – 33 – 35 – 19 – 42 - 44 -Chúng ta lại thấy rằng 14 và 10 không theo thứ tự. 14 – 10 – 27 – 33 – 35 – 19 – 42 - 44 -Và chúng ta tiếp tục tráo đổi hai số này. Cuối cùng, sau vòng lặp thứ 3 chúng ta có 4 phần tử. 10 – 14 – 27 – 33 – 35 – 19 – 42 - 44 -Tiến trình trên sẽ tiếp tục diễn ra cho tới khi tất cả giá trị chưa được sắp xếp được sắp xếp hết vào trong danh sách con đã qua sắp xếp. Tiếp theo chúng ta cùng tìm hiểu khía cạnh lập trình của giải thuật sắp xếp chèn. 10 – 14 – 19 – 27 – 33 – 35 – 42 - 44
17
KHOA CÔNG NGHỆ THÔNG TIN
Giải thuật sắp xếp chèn - Insertion Sort Bước 1: Kiểm tra nếu phần tử đầu tiên đã được sắp xếp. trả về 1 Bước 2: Lấy phần tử kế tiếp Bước 3: So sánh với tất cả phần tử trong danh sách con đã qua sắp xếp Bước 4: Dịch chuyển tất cả phần tử trong danh sách con mà lớn hơn giá trị để được sắp xếp Bước 5: Chèn giá trị đó Bước 6: Lặp lại cho tới khi danh sách được sắp xếp
18
KHOA CÔNG NGHỆ THÔNG TIN
19
KHOA CÔNG NGHỆ THÔNG TIN
#thuật toán tìm kiếm sắp xếp chọn – Selection_Sort
Step 1 – duyệt mảng từ vị trí thứ 0 Step 2 − tìm kiếm p.tu min trong mảng Step 3 − hoán đổi giá trị với ptu min Step 4 – tăng p.tu kế tiếp giá trị với p.tu min Step 5 − lặp lại cho đến khi mảng được sắp xếp
20
KHOA CÔNG NGHỆ THÔNG TIN
#minh họa – giải thuật sắp xếp chọn
arr[] = 65 – 27 – 16 – 24 - 3 // Tìm phần tử nhỏ nhất trong trong arr[0...4] // và đổi chỗ nó với phần tử đầu tiên [3] – 27 – 16 – 24 – 65 // Tìm phần tử nhỏ nhất trong trong arr[1...4] // và đổi chỗ nó với phần tử đầu tiên của arr[1...4] 3 - [16] – 27 – 24 - 65 // Tìm phần tử nhỏ nhất trong trong arr[2...4] // và đổi chỗ nó với phần tử đầu tiên của arr[2...4] 3 – 16 - [24] – 27 – 65 // Tìm phần tử nhỏ nhất trong trong arr[3...4] // và đổi chỗ nó với phần tử đầu tiên của arr[3...4] 3 – 16 – 24 - [27] – 65
21
KHOA CÔNG NGHỆ THÔNG TIN
#Bài tập:
Thực hiện tính toán từng bước theo giải thuật sắp xếp chọn – Selection Sort. Cho mảng: A = [30, 65, 100, 20, 40, 75]
22
KHOA CÔNG NGHỆ THÔNG TIN
Câu 1: cho một mảng gồm các phần tử không có thứ tự:
14 – 33 – 27 – 110 – 19
a)Biểu diễn Giải thuật sắp xếp nổi bọt b)Biểu diễn giải thuật sắp xếp chèn c)Biểu diễn giải thuật sắp xếp chọn
23
KHOA CÔNG NGHỆ THÔNG TIN
#Ôn tập:
24
KHOA CÔNG NGHỆ THÔNG TIN
#Thực hành 1.1:
#Nhắc lại kiến thức – Giải thuật nổi bọt
25
KHOA CÔNG NGHỆ THÔNG TIN
# Thực hành 1.2:
for j in range(len(arr) - 1):
#Bubble Sort >>> def bubble_sort(arr): ?? for i in range(len(arr)): ??
arr[j], arr[j+1] = arr[j+1], arr[j] ??
if arr[j] > arr[j+1]:
#Nhan xet: input & output cua Giai thuat tren?
#Yêu cầu – comment vào dấu note, bước lặp, vòng lặp của giải thuật
>>> arr = [39, 25, 16, 20] >>> bubble_sort(arr) >>> print(arr)
26
KHOA CÔNG NGHỆ THÔNG TIN
# Thực hành 2:
>>> def insertion_Sort(arr):
for i in range(1, len(arr)):
insert = arr[i] j = i-1 while (j >= 0 and insert < arr[j]) :
arr[j + 1] = arr[j] j -= 1
arr[j + 1] = insert
>>> arr = [14, 33, 27, 10, 35, 19, 42, 44] >>> insertion_Sort(arr) >>> for i in range(len(arr)): print ("% d" % arr[i])
#Nhận xét: input, output của giải thuật sắp xếp chèn
#Nhắc lại kiến thức – Giải thuật sắp xếp chọn
27
KHOA CÔNG NGHỆ THÔNG TIN
#Nhận xét: input, output của giải thuật sắp xếp chọn
#Nhắc lại kiến thức – Giải thuật sắp xếp chọn
# Thực hành 3.1:
28
KHOA CÔNG NGHỆ THÔNG TIN
# Thực hành 3.2:
for i in range(len(arr)): ??
>>> def selection_sort(arr):
min = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min]: ??
min = j
arr[min], arr[i] = arr[i], arr[min] ??
>>> arr = [65, 27, 16, 24, 3] >>> selection_sort(arr)
#Nhận xét: input, output của giải thuật sắp xếp chọn
#Yêu cầu – comment vào dấu note, bước lặp, vòng lặp của giải thuật
return arr
29
