BÀI 21: CÁC THUẬT TOÁN SẮP XẾP ĐƠN GIẢN | Tin học 11 - Định hướng khoa học máy tính | Chủ đề 6: Kỹ thuật lập trình - Lớp 11 - Kết Nối Tri Thức Với Cuộc Sống


(Trang 99)

SAU BÀI HỌC NÀY EM SẼ:

  • Biết và thực hiện được một số thuật toán sắp xếp đơn giản.

Bài học trước cho em thấy việc tìm kiếm trên một dãy đã sắp xếp nhanh hơn so với việc tìm kiếm tuần tự. Vì vậy bài toán tìm kiếm liên quan mật thiết đến bài toán sắp xếp. Bài toán sắp xếp cơ bản có dạng như sau:

Cho dãy A gồm n phần tử: Α[0], A[1], A[n-1] Cần xếp dãy A theo thứ tự tăng dần: A[0] ≤ A[1] ≤ ... ≤ A[n-1] (1) (2)

Em hãy trình bày ý tưởng của mình để giải bài toán sắp xếp với dãy có bốn phần tử.

1. THUẬT TOÁN SẮP XẾP CHÈN

Hoạt động 1 Tìm hiểu ý tưởng thuật toán sắp xếp chèn

Quan sát sơ đồ mô phỏng, trao đổi, thảo luận về ý tưởng chính của thuật toán sắp xếp chèn.

hinh-anh-bai-21-cac-thuat-toan-sap-xep-don-gian-13073-0

Vòng lập 1

Vòng lặp 2

Vòng lặp 3

Cho dãy A = [5, 3, 9, 7, 2]. Sơ đồ sau mô phỏng các bước của thuật toán sắp xếp chèn.

hinh-anh-bai-21-cac-thuat-toan-sap-xep-don-gian-13073-1

Chỉ số của dãy

0

1 2 3 4

Vòng lặp 1, i = 1

Duyệt phần từ thứ hai, vì 3 nhỏ hơn 5 nên chèn 3 vào trước vị trí số 5

Sau vòng lặp

3 5 9 7 2
Vòng lặp 2, i = 2 Duyệt phần từ thứ ba, vì 9 đã lớn hơn 3 và 5 nên giữ nguyên vị trí
Sau vòng lặp 3 5 9 7 2
Vòng lặp 3, i = 3 Duyệt phần từ thứ tư, vì 5 < 7 < 9 nên chèn 7 vào giữa vị trí của 5 và 9
Sau vòng lặp 3 5 7 9 2
Vòng lặp 4, i = 4 Duyệt phần từ thứ năm, vì 2 < 3 nên chèn 2 vào trước vị trí số 3
Kết thúc 2 3 5 7 9

Hình 21.1. Mô phỏng thuật toán sắp xếp chèn

(Trang 99)

Quan sát sơ đồ mô phỏng và trả lời các câu hỏi sau:

1) So sánh số bước lặp với độ dài của dãy số ban đầu.

2) Vị trí xuất phát của mũi tên màu đỏ có quan hệ gì với chỉ số bước lặp?

3) Khi kết thúc lặp ta thu được kết quả gì?

Ý tưởng của thuật toán sắp xếp chèn là cho chỉ số i chạy từ 1 (phần tử thứ hai của dãy) đến n - 1 (phần tử cuối của dãy). Mỗi vòng như vậy sẽ "chèn" phần tử A[i] vào vị trí đúng của dãy con đã sắp xếp A[0], A[1]...., A[i-1]. Như vậy sau n - 1 bước lặp thì dãy được sắp xếp xong.

Thao tác "chèn" A[i] vào vị trí đúng trong dãy con A[0], A[1],..., A[i-1] có thể được mô tả bằng cách "nhấc" A[i] lên và chuyền các phần tử bên trái A[i] nhưng lớn hơn A[i] sang phải, sau đó đặt A[i] vào vị trí đúng.

hinh-anh-bai-21-cac-thuat-toan-sap-xep-don-gian-13073-2 

1 value = A[i]

2 j = 1-1

3 while j >= 0 and A[j] > value:

4 Dịch A[j] sang vị trí liền kề bên phải

5 jj-1

6 A[j+1] = value

Thuật toán sắp xếp chèn có thể mô tả bằng hàm InsertionSort(A) như sau:

hinh-anh-bai-21-cac-thuat-toan-sap-xep-don-gian-13073-3

1 def Insertion Sort (A):

2 n = len(A)

3 for i in range(1,n):

4 value = A[i]

5 j = 1-1

6 while j >= 0 and A[j] > value:

7 A[j+1] = A[j]

8 jj-1

9 A[j+1] = value

Ý tưởng của thuật toán sắp xếp chèn là thực hiện vòng lặp duyệt từ phần tử thứ hai đến cuối dãy. Sau mỗi bước lặp phần tử tương ứng sẽ được của dây c chèn vào vị trí đúng của dãy con đã sắp xếp là các phần tử phía trước vị trí đang duyệt.

1. Mô phỏng chi tiết các bước lặp sắp xếp chèn dãy A = [5, 0, 4, 2, 3].

2. Nếu dãy ban đầu đã được sắp xếp thì thuật toán sắp xếp chèn sẽ thực hiện như thế nào?

2. THUẬT TOÁN SẮP XẾP CHỌN

Hoạt động 2 Tìm hiểu ý tưởng thuật toán sắp xếp chọn

Quan sát sơ đồ mô phỏng, trao đổi, thảo luận về ý tưởng chính của thuật toán sắp xếp chọn.

Xét dãy A = [5, 3, 9, 7, 2]. Sơ đồ sau mô phỏng các bước thực hiện thuật toán sắp xếp chọn. Quan sát sơ đồ và trả lời các câu hỏi sau:

1) Có bao nhiêu vòng lặp? Chỉ số i bắt đầu bằng bao nhiêu?

2) Tại mỗi vòng lặp đều có một thao tác đồi chỗ hai phần tử, đó là các phần tử nào?

3) Khi kết thúc vòng lặp ta thu được kết quả gì?

(Trang 101)

hinh-anh-bai-21-cac-thuat-toan-sap-xep-don-gian-13073-4

Chỉ số của dãy

0 1 2 3 4

Trước vòng lặp

5 3 9 7 2

Vòng lặp 1, i = 0

2 là phần tử nhỏ nhất, đổi chỗ 2 với 5
Sau vòng lặp 2 3 9 7 5
Vòng lặp 2, i = 1 3 là phần tử nhỏ nhất không tính phần từ đầu tiên, giữ nguyên vị trí dãy số
Sau vòng lặp 2 3 9 7 5
Vòng lặp 3, i = 2 5 là phần tử nhỏ nhất không tính hai phần từ đầu tiên, đồi chỗ 5 và 9
Sau vòng lặp 2 3 5 7 9
Vòng lặp 4, i = 3 7 là phần từ nhỏ nhất không tỉnh 3 phần tử đầu tiên, giữ nguyên vị trí dãy số
Kết thúc 2 3 5 7 9

Hình 21.2. Mô phỏng thuật toán sắp xếp chọn

Ý tưởng của thuật toán sắp xếp chọn là cho chỉ số i chạy từ 0 (phần tử đầu tiên) đến n - 2 (phần tử gần cuối). Tại mỗi bước lặp, cần tìm phần tử nhỏ nhất nằm trong dãy A[i], A[i+1], ..., A[n-1] và đổi chỗ phần tử nhỏ nhất này với A[i]. Mô tả thuật toán chọn như sau:

hinh-anh-bai-21-cac-thuat-toan-sap-xep-don-gian-13073-5

1 for i in range (n-1):

2 Chọn phần tử nhỏ nhất trong dãy A[i], A[i+1], ..., A[n-1]

3 Đối chỗ phần tử này với A[i]

Bước chọn phần tử tại dòng 2 và đổi chỗ tại dòng lệnh 3 có thể viết như sau:

hinh-anh-bai-21-cac-thuat-toan-sap-xep-don-gian-13073-6

1 iMini

2 for j in range(i+1,n):

3 if A[j] < A[iMin]:

4 iMin = j

5 Đổi chỗ A[i] và A[iMin]

Ở đây sử dụng biến iMin đề lưu chỉ số phần tử nhỏ nhất của dãy A[i], A[i+1], ..., A[n-1]. Thuật toán sắp xếp chọn có thể được mô tả bằng hàm SelectionSort(A) như sau:

hinh-anh-bai-21-cac-thuat-toan-sap-xep-don-gian-13073-7

1 def SelectionSort(A):

2 n = len(A)

3 for i in range(n-1):

4 iMin = i

5 for j in range(i+1,n):

6 if A[j] < A[iMin]:

7 iMin = j

8 A[i], A[iMin] = A[iMin], A[i]

(Trang 102)

Thuật toán sắp xếp chọn thực hiện một vòng lặp với chỉ số i chạy từ 0 (phần tử đầu tiên) đến n - 2 (phần tử gần cuối). Tại mỗi bước lặp, chọn phần từ nhỏ nhất nằm trong dãy A[i], A[i+1]....., A[n-1] và đổi chỗ phần tửnày với A[i].

1. Thực hiện mô phỏng sắp xếp theo thuật toán sắp xếp chọn dãy sau: 4, 5, 2, 1, 3.

2. Theo thuật toán sắp xếp chọn, sau mỗi bước thứ i thì các phần tử A[0], A[1],..., A[i] đã được sắp xếp đúng. Đúng hay sai?

3. THUẬT TOÁN SẮP XẾP NỔI BỌT

Hoạt động 3 Tìm hiểu các ý tưởng thuật toán sắp xếp nổi bọt

Cùng trao đổi, thảo luận về các ý tưởng của thuật toán sắp xếp nổi bọt.

Thuật toán sắp xếp nổi bọt lấy ý tưởng từ hiện tượng "nồi bọt" của không khí dưới nước. Các bọt khí nổi dần lên mặt nước. Ý tưởng của thuật toán nổi bọt là liên tục đổi chỗ hai phần tử cạnh nhau nếu chúng chưa được sắp thứ tự đúng.

Thuật toán này sẽ thực hiện nhiều vòng lặp. Quan sát vòng lặp sau đề hiều cách thực hiện: chỉ số j chạy từ 0 đến n - 2 và kiểm tra hai phần tử liền nhau A[j], A[j+1], nếu chúng chưa sắp thứ tự đúng thì đồi chỗ.

hinh-anh-bai-21-cac-thuat-toan-sap-xep-don-gian-13073-8

1 for j in range(n-1):

2 if A[j] > A[j+1]:

3 Đổi chỗ A[j], A[j+1]

Quan sát vòng lặp đầu tiên của thuật toán nổi bọt để thấy sau vòng lặp này, phần tử lớn nhất được chuyển về cuối dãy A

Chỉ số của dãy:

0 1 2 3 4  

Trước vòng lặp

5 3 9 7 2  
Bước lặp 1, j = 0 5 3 9 7 2 So sánh phần từ thứ nhất và phần từ thứ hai
Bước lặp 2, j = 1 3 5 9 7 2 So sánh phần từ thứ hai và phần từ thứ ba
Bước lặp 3, j = 2 3 5 9 7 2 So sánh phần từ thứ ba và phần từ thứ tư
Bước lặp 4, j = 3 3 5 7 9 2 So sánh phần tử thứ tư và phần tử thứ năm
Kết thúc vòng 1 3 5 7 2 9  

Trong sơ đồ trên, mũi tên màu đỏ cho biết có đồi chỗ hai phần tử, mũi tên màu tím cho biết không thay đồi vị trí.

hinh-anh-bai-21-cac-thuat-toan-sap-xep-don-gian-13073-9

Hình 21.3. Mô phỏng thuật toán sắp xếp nổi bọt

(Trang 103)

Sau vòng lặp thứ nhất, phần tử lớn nhất được chuyền về cuối dãy. Sau vòng lặp thứ hai, phần tử lớn thứ hai được chuyền về đúng vị trí ở cuối dãy. Cứ như vậy, sau n – 1 vòng lặp thì dãy được sắp xếp. Có thể mô tả thuật toán nồi bọt như sau:

hinh-anh-bai-21-cac-thuat-toan-sap-xep-don-gian-13073-10

Quan sát dòng 2, ta thấy không cần phải có đủ n – 1 bước lặp vì sau i vòng lặp thì i phần tử lớn nhất đã chuyển về đúng vị trí ở cuối dãy, nên với chỉ số i thì vòng lặp ở dòng 2 chỉ cần n – 1 – i bước lặp. Thuật toán sắp xếp nổi bọt được mô tả bằng hàm BubbleSort(A) như sau:

hinh-anh-bai-21-cac-thuat-toan-sap-xep-don-gian-13073-11

1 def BubbleSort(A):

2 n = len(A)

3 for i in range(n-1):

4 for j in range(n-1-i):

5 if A[j] > A[j+1]:

6 Aj], A[j+1]=A[j+1],A[j]

Thuật toán sắp xếp nổi bọt thực hiện nhiều vòng lặp, kiểm tra hai phần tử cạnh nhau, nếu chúng chưa sắp xếp đúng thì đổi chỗ. Có nhiều cách thể hiện thuật toán này, nhưng cách thường dùng là sử dụng hai vòng lặp lồng nhau, vòng lặp trong thực hiện thao tác đổi chỗ hai phần tử cạnh nhau cho đến khi dãy được sắp xếp xong.

1. Mô tả các ăn sắp xếp nổi bọt của bước thuật toán sắp xếp nổi bọt của dãy A = [4, 3, 1, 2].

2. Khi nào thì các mũi tên ở tất cả các bước trong sơ đồ mô phỏng thuật toán sắp xếp nổi bọt đều có màu đỏ?

LUYỆN TẬP

1. Cho dãy A = [5, 8, 1, 0, 10, 4, 3]. Viết các chương trình sắp xếp dãy A theo thứ tự tăng dần theo các thuật toán sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt.

2. Viết chương trình nhập một dãy số từ bàn phím, các số cách nhau bởi dấu cách, thực hiện sắp xếp dãy đã nhập theo một trong các thuật toán sắp xếp rồi in kết quả ra màn hình.

VẬN DỤNG

1. Viết lại các thuật toán sắp xếp trong bài theo thứ tự giảm dần.

2. Nêu ý nghĩa thực tế của các thuật toán sắp xếp đã học, chẳng hạn sắp xếp các học sinh trong lớp theo chiều cao tăng dần.

Tin tức mới


Đánh giá

BÀI 21: CÁC THUẬT TOÁN SẮP XẾP ĐƠN GIẢN | Tin học 11 - Định hướng khoa học máy tính | Chủ đề 6: Kỹ thuật lập trình - Lớp 11 - Kết Nối Tri Thức Với Cuộc Sống

Tổng số sao của bài viết là: 5 trong 1 đánh giá
Xếp hạng: 5 / 5 sao

Bình Luận

Để Lại Bình Luận Của Bạn

Tin học 11 - Định hướng khoa học máy tính

  1. Chủ đề 1: Máy tính và xã hội tri thức
  2. Chủ đề 2: Tổ chức lưu trữ, tìm kiếm và trao đổi thông tin
  3. Chủ đề 3: Đạo đức, pháp luật và văn hóa trong môi trường số
  4. Chủ đề 4: Giới thiệu các hệ cơ sở dữ liệu
  5. Chủ đề 5: Hướng nghiệp với tin học
  6. Chủ đề 6: Kỹ thuật lập trình

Tin tức mới

Môn Học Lớp 11 - Kết Nối Tri Thức Với Cuộc Sống

Giải bài tập Toán 11 Tập 1

Âm Nhạc

Công Nghệ

Công Nghệ Công Nghệ Cơ Khí

GDTC_Cầu Lông

Giáo dục Kinh Tế và Pháp Luật

Giáo dục Thể Chất Bóng Chuyền

GDTC Bóng Đá

GDTC_Bóng Rổ

Hoạt động trải nghiệm hướng nghiệp

Lịch sử

Mỹ Thuật Điêu Khắc

Mỹ Thuật Đồ Hoạ_Tranh in

Mỹ Thuật Hội Hoạ

Mỹ Thuật Kiến Trúc

Mỹ Thuật Thiết Kế Công Nghiệp

Mỹ Thuật Thiết Kế Đa Phương Tiện

Mỹ Thuật Thiết Kế Đồ Hoạ

Mỹ Thuật Thiết Kế Sân Khấu Điện Ảnh

Mỹ Thuật Thiết Kế Thời Trang

Mỹ Thuật_Lý Luận Và Lịch Sử Mỹ Thuật

Ngữ Văn Tập 1

Ngữ Văn Tập 2

Sinh Học

Địa Lý

Tin Học

Toán tập 1

Toán tập 2

Vật lý

Tin học 11 - Định hướng khoa học máy tính

Giải bài tập Toán 11 Tập 2

Giải bài tập Vật lý 11

Giải bài tập Sinh học 11

Giải bài tập Hóa học 11

Bộ Sách Lớp 11

Giáo Dục Việt Nam

Bộ Sách Giáo Khoa của Nhà Xuất Bản Giáo Dục Việt Nam

Tài liệu học tập

Đây là tài liệu tham khảo hỗ trợ trong quá trình học tập

Global Success & Bộ Giáo Dục - Đào Tạo

Bộ sách Global Success & Bộ Giáo Dục - Đào Tạo là sự kết hợp giữa ngôn ngữ Tiếng Anh theo lối giảng dạy truyền thống và cập nhật những phương thức quốc tế

Cánh Diều

Bộ sách giáo khoa của Nhà xuất bản Cánh Diều

Kết Nối Tri Thức Với Cuộc Sống

Sách giáo khoa của nhà xuất bản Kết Nối Tri Thức Với Cuộc Sống

Sách Kết Nối Tri Thức Với Cuộc Sống

Lớp 1

Sách giáo khoa dành cho lớp 1

Lớp 6

Sách giáo khoa dành cho lớp 6

Lớp 5

Sách giáo khoa dành cho lớp 5

Lớp 4

Sách giáo khoa dành cho lớp 4

Lớp 2

Sách giáo khoa dành cho lớp 2

Lớp 3

Sách giáo khoa dành cho lớp 3

Lớp 7

Sách giáo khoa dành cho lớp 7

Lớp 8

Sách giáo khoa dành cho lớp 8

Lớp 9

Sách giáo khoa dành cho lớp 9

Lớp 10

Sách giáo khoa dành cho lớp 10

Lớp 11

Sách giáo khoa dành cho lớp 11

Lớp 12

Sách giáo khoa dành cho lớp 12

Liên Kết Chia Sẻ

** Đây là liên kết chia sẻ bới cộng đồng người dùng, chúng tôi không chịu trách nhiệm gì về nội dung của các thông tin này. Nếu có liên kết nào không phù hợp xin hãy báo cho admin.