Giáo án điện tử chuyên đề Khoa học máy tính 11 kết nối Bài 9: Sắp xếp trộn

XIN MỜI CÁC EM

ĐẾN VỚI BÀI HỌC NGÀY HÔM NAY!

KHỞI ĐỘNG

Ta đã biết tìm kiếm nhị phân trên các dãy đã sắp xếp có độ phức tạp thời gian tốt hơn so với các thuật toán tìm kiếm trên dãy chưa sắp xếp. Chính vì thế, việc sắp xếp thông tin theo một trình tự nào đó luôn đóng vai trò quan trọng trong các bài toán tìm kiếm thông tin. Tuy nhiên, một số thuật toán sắp xếp mà em đã biết như sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt, ... đều có độ phức tạp thời gian O (n2 ) (n - kích thước dãy cần sắp xếp). Câu hỏi đặt ra là: Liệu có hay không một cách sắp xếp dãy với thời gian tốt hơn O (n2)?

Liệu kĩ thuật chia để trị có thể áp dụng cho bài toán sắp xếp được không? Nếu có thì có làm tăng hiệu quả của sắp xếp được không?

BÀI 9.

SẮP XẾP TRỘN

NỘI DUNG BÀI HỌC

1

Ý tưởng thuật toán

2

Mô tả thuật toán

3

Đánh giá thuật toán

PHẦN 1. Ý TƯỞNG THUẬT TOÁN

Hoạt động 1

Tìm hiểu ý tưởng sắp xếp trộn

Quan sát và thực hiện các bước theo ý tưởng của thuật toán sắp xếp trộn để biết thuật toán này là mô hình kĩ thuật chia để trị.

Em có nhận xét gì về đặc thù của các giai đoạn 1, 2, 3 trong sơ đồ dưới đây?

Bước chia

Giai đoạn 1: Tách chia đôi làm hai dãy con, mỗi dãy con có kích thước bằng ½ kích thước của dãy gốc.

Bước trị

Giai đoạn 2: Khi các dãy con thu được đều chỉ còn một phần tử. Tất cả các dãy này hiển nhiên đều đã được sắp xếp đúng.

Kết hợp

Giai đoạn 3: Từ các dãy đã sắp xếp xong, chúng ta sẽ trộn chúng lại với nhau, mỗi lần trộn hai dãy đã sắp xếp để tạo thành một dãy lớn hơn cũng được sắp xếp đúng.

Ý nghĩa của việc trộn

Trộn hai dãy đã sắp xếp thành một dãy lớn hơn cũng sẽ được sắp xếp.

KẾT LUẬN

Ý tưởng của thuật toán sắp xếp trộn được thực hiện qua 3 bước: Chia nhỏ dãy gốc thành các dãy với kích thước nhỏ hơn (bằng ½ dãy ban đầu), tiếp tục cho đến khi nhận được các dãy con đã sắp xếp đúng thì tiến hành trộn các dãy này để nhận được kết quả cuối cùng. Các bước trên chính là kĩ thuật chia để trị.

Đọc thông tin và trả lời các câu hỏi sau đây:

• Câu 1: Hãy thực hiện thao tác trộn hai dãy sau: B = 1, 4, 7; C = 2, 3, 6.
• Câu 2: Thực hiện sắp xếp dãy 3, 2, 7, 1, 6, 5 theo các bước tương tự trên.

1

• Thực hiện bằng tay trộn hai dãy B = 1, 4, 7 và C = 2, 3, 6.
• Mỗi bước sau mô tả một thao tác đơn thực hiện trộn hai dãy B, C, kết quả trả về dãy mới A.

Bước 1. Đưa 1 vào A.

Bước 2. Đưa 2 vào A.

Bước 3. Đưa 3 vào A.

Bước 4. Đưa 4 vào A.

Bước 5. Đưa 6 vào A.

Bước 6. Đưa 7 vào A.

Kết thúc dãy A sẽ là 1, 2, 3, 4, 6, 7.

2

Thực hiện sắp xếp trộn dãy 3, 2, 7, 1, 6, 5 theo sơ đồ.

PHẦN 2. MÔ TẢ THUẬT TOÁN

Hoạt động 2

Tìm hiểu các bước thực hiện sắp xếp trộn

Cùng thực hiện các bước cụ thể triển khai ý tưởng và cài đặt chương trình cho thuật toán sắp xếp trộn.

a) Thuật toán trộn hai dãy (merge algorithm)

Giả sử cho trước hai dãy đã được sắp thứ tự B và C có số phần tử lần lượt là m, n. Thuật toán merge(B, C) sẽ được thực hiện "trộn" hai dãy trên và đưa kết quả vào dãy A.

1 def merge(B,C):

2 m = len(B)

3 n = len(C)

4 A = [0] * (m+n) # Thiết lập dãy A bao gồm m+n số 0

5 i = j = k = 0

6 while i < m and j < n:

7 if B[i] <= c[j]

8 A[k] = B[i]

9 i= i + 1

10 else:

11 A[k] = c[j]

12 j = j + 1

13 k = k + 1

14 if i == m:

15 while j < n:

16 A[k] = c[j]

17 j=j+ 1

18 k = k + 1

19 else:

20 while i < m:

21 A[k] = B[i]

22 i = i + 1

23 k = k + 1

24 return A

Bắt đầu duyệt tại đây

Nếu đã duyệt xong B thì đưa nốt phần còn lại của C vào A

16 A[k] = c[j]

17 j=j+ 1

18 k = k + 1

19 else:

20 while i < m:

21 A[k] = B[i]

22 i = i + 1

23 k = k + 1

24 return A

Nếu đã duyệt xong C thì đưa nốt phần còn lại của B vào A

b) Thuật toán sắp xếp trộn (mergeSort)

Thuật toán sắp xếp trộn được mô tả bởi hàm mergeSort(A) trong chương trình sau:

1 def mergeSort(A):

2 if len(A) <= 1:

3 return A

4 else:

5 k = len(A)//2

6 B = mergeSort(<dãy con A từ 0 đến k>)

7 C = mergeSort(<dãy con A từ k+1 đến len(A)-1>)

8 return merge(B, C)

• Đoạn chương trình sau sẽ thực hiện sắp xếp dãy A và đưa kết quả đã sắp xếp vào dãy B. Lời gọi hàm đệ quy là:

1 A = [2, 1, 10, 0, -7, -20, 19, 100, -3, -2, 9, 11]

2 B = mergeSort(A)

KẾT LUẬN

Thuật toán sắp xếp trộn sẽ bao gồm một hàm mergeSort(), hàm này sẽ tiến hành các bước chính của thuật toán và gọi hàm trộn hai dãy đã sắp xếp merge() khi thực hiện bước kết hợp.

Đọc thông tin và trả lời các câu hỏi sau đây:

• Câu 1: Trong chương trình 1 (trộn hai dãy B, C), vòng lặp tại dòng 6 có nhiều nhất là bao nhiêu bước lặp?
• Câu 2: Mô tả các bước thực hiện chương trình 2 nếu dãy gốc A chỉ có một phần tử.

HƯỚNG DẪN THỰC HIỆN

1

Vòng lặp 6 có nhiều nhất là m + n bước lặp.

2

Nếu dãy gốc có 1 phần tử thì thuật toán sắp xếp trộn sẽ không thực hiện gì và trả về ngay dãy gốc.

PHẦN 3. ĐÁNH GIÁ THUẬT TOÁN

Hoạt động 3

Tìm hiểu đánh giá độ phức tạp thời gian của sắp xếp trộn

Phân tích, trao đổi, thảo luận để tính độ phức tạp thời gian của thuật toán sắp xếp trộn.

• Gọi T(n) là thời gian chạy của thuật toán sắp xếp trộn.
• Với n = 1, dòng lệnh 2 trả lại ngay dãy gốc A, do đó T(1) = 1.

Phân tích

Trường hợp tổng quát

• Tại bước chia, cần O(1) thời gian để thực hiện.
• Các dòng 6,7 sẽ mất 2T(n/2) thời gian.
• Dòng lệnh 8 thực hiện trộn hai dãy với thời gian O(n).

Các công thức sau tính thời gian T(n).

T(1) = 1

T(n) = 2T(n/2) + O(n), n > 1 (1)

T(n) = 2T(n/2) + Cn, n > 1 (2)

Công thức truy hồi để tính toán độ phức tạp của thời gian T(n)

T(n) = O(nlogn)

KẾT LUẬN

Thuật toán sắp xếp trộn sử dụng kĩ thuật chia để trị có độ phức tạp thời gian O(nlogn), bậc thời gian này là tốt hơn hẳn các thuật toán sắp xếp mà chúng ta đã biết (sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt).

Đọc thông tin và trả lời các câu hỏi sau đây:

• Câu 1: Tính thời gian chạy của thuật toán sắp xếp trộn nếu A = [3,1].
• Câu 2: Mô tả thực hiện các bước của sắp xếp trộn với dãy A = [5, 1, 7, 4]. Trường hợp này T(4) sẽ được tính như thế nào?

HƯỚNG DẪN THỰC HIỆN

1

Tính thời gian chạy thuật toán sắp xếp trộn với A = [3, 1]. Chúng ta sẽ phân tích và tính theo số đơn vị thời gian.

• Kiểm tra tại dòng 2, mất 1 đơn vị thời gian.
• Thực hiện lệnh tại dòng 5, mất 1 đơn vị thời gian.
• Các dòng 5, 6 mỗi dòng chỉ mất 1 đơn vị thời gian do B và C đều là mảng 1 phần tử.
• Dòng 8 sẽ mất 2 đơn vị thời gian.

2

Các bước thực hiện sắp xếp trộn với A = [5, 1, 7, 4] như sau:

• Bước 1: Dòng 5, tính k = 2.
• Bước 2: Tính B = [5,1]
• Bước 3: Tính C = [4,7]
• Bước 4: Trộn B, C và trả về dãy [1,4,5,7]

Thời gian chạy

Kiểm tra tại dòng lệnh 1, mất 1 đơn vị thời gian.

• (1) tốn 1 đơn vị thời gian.
• (2), (3) mỗi bước mất 6 đơn vị thời gian (xem câu 1).
• (4) tốn 4 đơn vị thời gian.

LUYỆN TẬP

Bài 1: Viết chương trình thực hiện công việc sau:

- Dữ liệu được nhập từ tệp văn bản Data.inp bao gồm hai dòng, mỗi dòng là một dãy các số nguyên đã được sắp xếp theo thứ tự tăng dần, các số cách nhau bởi dấu cách. Hai dãy này có thể không bằng nhau về kích thước.

- Chương trình sẽ thực hiện trộn hai dãy trên và đưa kết quả dãy được trộn ra tệp Data.out theo một hàng ngang.

1 fi = "Data.inp"

2 def NhapDL(fi):

3 f = open(fi)

4 B = [int(x) for x in f.readline()split()]

5 C = [int(x) for x in f.readline()split()]

6 f.close()

7 return B,C

8

9 def merge(B,C):

10 m = len (B)

11 n = len(C)

12 A = [0]*(m+n)

13 i = j = k = 0

14 while i < m and j < n:

15 if B[i] < c[j]:

16 A[k] = B[i]

17 i=i+1

18 else:

19 A[k] = c[j]

20 j=j+1

21 k = k + 1

22 if i == m:

23 while j < n:

24 A[k] = c[j]

25 j = j+1

26 k = k+1

27 else:

28 while i < m:

29 A[k] = B[i]

30 i=i +1

31 k = k + 1

32 return A

33 #Chương trình chính

34 B,C = NhapDL(fi)

35 A = merge (B,C)

36 print(A)

13 i = j = k = 0

14 while i < m and j < n:

15 if B[i] < c[j]:

16 A[k] = B[i]

17 i=i+1

18 else:

19 A[k] = c[j]

20 j=j+1

21 k = k + 1

22 if i == m:

23 while j < n:

24 A[k] = c[j]

25 j = j+1

26 k = k+1

27 else:

28 while i < m:

29 A[k] = B[i]

30 i=i +1

31 k = k + 1

32 return A

33 #Chương trình chính

34 B,C = NhapDL(fi)

35 A = merge (B,C)

36 print(A)

25 j = j+1

26 k = k+1

27 else:

28 while i < m:

29 A[k] = B[i]

30 i=i +1

31 k = k + 1

32 return A

33 #Chương trình chính

34 B,C = NhapDL(fi)

35 A = merge (B,C)

36 print(A)

Bài 2: Viết lại chương trình hoàn chỉnh thực hiện sắp xếp trộn với dãy A cho trước trên một tệp văn bản. Kết quả đưa ra màn hình.

1 fi = "Data1.inp"

2 def NhapDL(fi):

3 f = open(fi)

4 B = [int(x) for x in f.readline()split()]

5 f.close()

6 return A

7

8 def merge(B,C):

9 m = len(B)

10 n = len (C)

11 A = [0]*(m+n)

12 i = j = k = 0

13 while i < m and j < n:

14 if B[i] < c[j]:

15 A[k] = B[i]

16 i=i +1

17 else:

18 A[k] = c[j]

19 j= j + 1

20 k = k + 1

21 if i == m:

22 while j < n:

23 A[k] = c[j]

24 j = j+1

25 k = k+1

26 else:

27 while i < m:

28 A[k] = B[i]

29 i=i +1

30 k = k + 1

31 return A

32

33 def mergeSort(A):

34 if len(A) <= 1:

35 return A

36 else:

37 k = len(A)//2

38 B = mergeSort(A[0:k])

39 C = mergeSort(A[k:len(A)])

40 return merge(B,C)

41

42 #Chương trình chính

43 A = NhapDL(fi)

44 print(A)

45 A = mergeSort(A)

46 print(A)

--------------- Còn tiếp ---------------