BÀI 21. CÁC THUẬT TOÁN SẮP XẾP ĐƠN GIẢN

PHẦN I. HỆ THỐNG CÂU HỎI, BÀI TẬP TRONG SGK

KHỞI ĐỘNG

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 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ử:

A[0],A[1],….,A[n-1] (1)

Cần sắp xếp dãy A theo thứ tự tăng dần:

A[0] ≤ A[1] ≤  ...  ≤ A[n-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ó 4 phần tử.

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

Hoạt động 1: 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.

Câu hỏi 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]

Câu hỏi 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: 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.

Câu hỏ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, 8, 2, 1, 3.

Câu hỏi 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: 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.

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

Câu hỏi 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

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.

Luyện tập 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

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.

Vận dụng 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.

PHẦN II. 5 PHÚT TRẢ LỜI CÂU HỎI, BÀI TẬP SGK

KHỞI ĐỘNG

Đáp án KD:

Duyệt qua từng phần tử của dãy từ đầu đến cuối ® So sánh hai phần tử liền kề, nếu phần tử sau lớn hơn phần tử trước thì hoán đổi chúng ® Tiếp tục duyệt qua các phần tử còn lại cho đến khi không còn phần tử nào cần hoán đổi ® Lặp lại quá trình trên cho đến khi toàn bộ dãy được sắp xếp.

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

Đáp án HD1: 

Ý tưởng 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 chèn vào vị trí đúng. 

Đáp án CH1: 

• Bước 1: i = 1;//giả sử có đoạn a[0] đã được sắp xếp
• Bước 2: x = a[i];
• Bước 3: Tìm vị trí pos thích hợp trong đoạn a[0] đến a[i-1] để chèn a[i] vào danh sách. Dời chỗ các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chổ cho a[i].
• Bước 4: a[pos] = x;//chèn x, có đoạn a[0],…,a[i] đã được sắp.
• Bước 5: i = i+1; nếu i < n ® lặp lại bước 2, ngược lại ® Dừng.

Đáp án CH2: 

Thuật toán sắp xếp chèn sẽ không thực hiện thay đổi nào trên dãy. 

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

Đáp án HD2: 

Tại mỗi bước lặp của thuật toán, phần tử nhỏ nhất ở mảng con chưa được sắp xếp sẽ được di chuyển về đoạn đã sắp xếp.

Đáp án CH1: 

• Bước 1: i = 0;

• Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n-1].

• Bước 3: Đổi chỗ a[min] và a[i].

• Bước 4: Nếu i < n-1 thì gán i = i+1; rồi lặp lại bước 2, ngược lại -> Dừng.

Đáp án CH2: 

Đúng

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

Đáp án HD3: 

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ỗ.

Đáp án CH1: 

Bắt đầu từ vị trí đầu tiên, so sánh các cặp số với nhau, nếu không đúng thứ tự thì đảo vị trí. Sau khi chạy tới cuối danh sách, tiếp tục chạy lại từ vị trí đầu danh sách cho đến khi hoàn thành so sánh và đảo vị trí.

Đáp án CH2: 

Thuật toán sắp xếp nổi bọt so sánh các phần tử kế tiếp trong danh sách và hoán đổi chúng nếu chúng không được sắp xếp theo thứ tự. Vì vậy khi màu của tất cả các mũi tên đều đỏ trong sơ đồ mô phỏng thì có nghĩa là không còn phần tử nào được sắp xếp và không cần hoán đổi nữa.

LUYỆN TẬP

Đáp án LT1: 

• Thuật toán sắp xếp chèn (Insertion Sort):

def insertion_sort(arr):

  for i in range(1, len(arr)):

   key = arr[i]

   j = i - 1

   while j >= 0 and arr[j] > key:

    arr[j + 1] = arr[j]

    j -= 1

   arr[j + 1] = key

  return arr

A = [5, 8, 1, 0, 10, 4, 3]

sorted_A = insertion_sort(A)

print("Dãy A sau khi sắp xếp chèn:", sorted_A)

• Thuật toán sắp xếp chọn (Selection Sort):

def selection_sort(arr):

  for i in range(len(arr)):

   min_idx = i

   for j in range(i + 1, len(arr)):

    if arr[j] < arr[min_idx]:

     min_idx = j

   arr[i], arr[min_idx] = arr[min_idx], arr[i]

  return arr

A = [5, 8, 1, 0, 10, 4, 3]

sorted_A = selection_sort(A)

print("Dãy A sau khi sắp xếp chọn:", sorted_A)

• Thuật toán sắp xếp nổi bọt (Bubble Sort):

def bubble_sort(arr):

  n = len(arr)

  for i in range(n - 1):

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

    if arr[j] > arr[j + 1]:

     arr[j], arr[j + 1] = arr[j + 1], arr[j]

  return arr

A = [5, 8, 1, 0, 10, 4, 3]

sorted_A = bubble_sort(A)

print("Dãy A sau khi sắp xếp nổi bọt:", sorted_A)

Đáp án LT2: 

# Nhập dãy số từ bàn phím

lst = list(map(int, input("Nhập dãy số cách nhau bởi dấu cách: ").split()))

# Sắp xếp dãy số theo thuật toán sắp xếp chọn

for i in range(len(lst)):

   min_idx = i

   for j in range(i+1, len(lst)):

       if lst[j] < lst[min_idx]:

           min_idx = j

   lst[i], lst[min_idx] = lst[min_idx], lst[i]

# In kết quả ra màn hình

print("Dãy số đã sắp xếp:", lst)

VẬN DỤNG

Đáp án VD1:

1. Gán i = 0
2. Gán j = i + 1 và min = A[i]
3. Nếu j < n:
   • Nếu A[j] < A[min] thì min = j
   • j = j + 1
   • Quay lại bước 3
4. Đổi chỗ A[min] và A[i]
5. Nếu i < n – 1:
   • Đúng thì i = i + 1 và quay lại bước 2
   • Sai thì dừng lại

Đáp án VD2:

Ý nghĩa: Tối ưu hóa thời gian thực thi, tạo độ thứ tự, áp dụng trong nhiều lĩnh vực, nền tảng cho các thuật toán phức tạp hơn.