Hướng dẫn giải nhanh Tin học 11 định hướng Khoa học máy tính KNTT bài 21: Các thuật toán sắp xếp đơn giản

MỞ ĐẦU

Câu 1: 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ử.

Trả lời:

• Duyệt qua từng phần tử 

• 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 

• Tiếp tục cho đến khi không còn phần tử nào cần hoán đổi.

• Lặp lại cho đến khi toàn bộ dãy được sắp xếp.

Hoặc:

• Duyệt qua từng phần tử 

• Lưu giá trị của phần tử hiện tại vào biến tạm thời.

• So sánh phần tử hiện tại với các phần tử bên trái, phần tử nào lớn hơn phần tử hiện tại thì dời sang phải một vị trí.

• Chèn giá trị của phần tử hiện tại vào vị trí đúng sau khi dời các phần tử.

• Tăng vị trí phần tử hiện tại lên 1 và lặp lại cho đến khi toàn bộ dãy được sắp xếp.

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

Câu 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.

Trả lời:

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 của dãy con đã sắp xếp là các phần tử phía trước vị trí đang duyệt. 

Câu hỏi

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

Trả lời:

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 a[0] đến a[i-1] để chèn a[i] vào.

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.

Câu 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?

Trả lời:

không thực hiện thay đổi nào vì mỗi phần tử trong dãy đã đứng đúng vị trí của nó. Cụ thể:

Xác định phần tử đầu tiên trong dãy là phần tử thứ 2 (i = 1), không cần thực hiện bất kỳ thay đổi nào vì phần tử này đã đứng đúng vị trí 

Kiểm tra phần tử thứ 3 (i = 2) so với các phần tử trước nó trong dãy. Phần tử này đã đứng đúng vị trí, không cần thực hiện thay đổi nào.

Tiếp tục kiểm tra và so sánh, thấy đã đứng đúng vị trí, không cần thực hiện thay đổi nào.

Sau khi kiểm tra hết các phần tử trong dãy, thuật toán kết thúc mà không có bất kỳ thay đổi nào, vì dãy đã được sắp xếp.

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

Câu 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.

Trả lời:

Tại mỗi bước lặp, 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.

Câu hỏi

Câu 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.

Trả lời:

• Bước 1: i = 0;

• Bước 2: Tìm a[min] nhỏ nhất trong dãy 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 gán i = i+1; lặp lại bước 2, ngược lại -> Dừng.

Câu 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?

Trả lời:

Đúng vì 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 trong dây A[i]. A[i+1]..... A[n-1] và đổi chỗ với A[i].

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âu 1: 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.

Trả lời:

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

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

Trả lời:

• Từ vị trí đầu tiên của danh sách (bên trái), so sánh các cặp số với nhau, không đúng thứ tự nhỏ-lớn thì đảo vị trí.

• Tới cuối danh sách, 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í.

Câu 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 đỏ?

Trả lời:

• 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 theo thứ tự tăng dần hoặc giảm dần và không cần thực hiện bất kỳ hoán đổi nào nữa.

• Các phần tử trong mảng sẽ được so sánh với phần tử tiếp theo, nếu không được sắp xếp đúng thứ tự thì chúng sẽ hoán đổi cho nhau, lặp lại và các hoán đổi sẽ tiếp tục được thực hiện cho đến khi tất cả các phần tử đều được sắp xếp theo thứ tự đúng.

LUYỆN TẬP

Câu 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.

Trả lời:

• 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)

• 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)

• 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)

Câu 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.

Trả lời:

# Nhập dãy số 

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

Câu 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.

Trả lời:

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] ->  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 ->  i = i + 1, quay lại bước 2

• Sai -> dừng lại

Câu 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.

Trả lời:

ý nghĩa thực tế:

• Tối ưu hóa thời gian thực thi: giảm bớt thời gian chờ đợi và tăng hiệu quả hoạt động của hệ thống. 

• Tạo độ thứ tự: dễ dàng tìm kiếm, tra cứu, phân tích hoặc xử lý dữ liệu sau này. 

• Áp dụng trong nhiều lĩnh vực: còn được sử dụng trong nhiều lĩnh vực khác như khoa học máy tính, công nghệ thông tin, tài chính, thương mại điện tử, kho dữ liệu, v.v. 

• Nền tảng cho các thuật toán phức tạp hơn: Các thuật toán sắp xếp đóng vai trò là nền tảng cho nhiều thuật toán phức tạp.