Câu hỏi 1:
Sắp xếp là một hoạt động quen thuộc không chỉ trong tin học mà còn trong đời sống hằng ngày.
Em hãy nêu một ví dụ thực tế mà em từng gặp có liên quan đến việc sắp xếp dữ liệu hoặc đồ vật, và cho biết mục đích của việc sắp xếp đó là gì?
Câu hỏi 2:
Trong lập trình, có rất nhiều thuật toán sắp xếp khác nhau, mỗi thuật toán có ưu điểm và cách hoạt động riêng.
Em hãy kể tên một hoặc vài thuật toán sắp xếp mà em đã được học hoặc từng nghe qua, và nêu ngắn gọn điều em nhớ nhất về chúng.
Nhiệm vụ: Tương tác với mô phỏng bên dưới.
Thử chạy Interchange Sort, Selection Sort, Bubble Sort, Insertion Sort và Merge Sort với số lượng phần tử lớn.
Câu hỏi 1: Trong các thuật toán vừa xem, em đã học hay nghe qua thuật toán nào?
Câu hỏi 2 (Vấn đề): Giả sử em cần sắp xếp điểm của 1.165.289 thí sinh thi THPT Quốc gia 2025.
Em sẽ chọn thuật toán nào (Interchange Sort, Selection Sort, Bubble Sort, Insertion Sort, hay Merge Sort) để tối ưu nhất?
Nếu sắp xếp với một dữ liệu quá lớn, lên đến hàng triệu phần tử thì các thuật toán sắp xếp thông thường với độ phức tạp O(n^2) sẽ tốn rất nhiều thời gian để hoàn thành.
Vì vậy cần một thuật toán tối ưu hiệu suất hơn, đó là Sắp xếp trộn (Merge Sort).
Nhiệmvụ: Chơi trò chơi! Tương tác với mô phỏng để "trộn" 2 mảng đã sắp xếp
thành một mảng mới vẫn duy trì thứ tự.
Sau khi trộn hai mảng đã được sắp xếp tăng dần vào một mảng mới cũng tăng dần, chúng ta nhận thấy được việc tạo một mảng mới nhanh hơn rất nhiều vì chỉ cần dựa vào hai phần tử đầu tiên (nhỏ nhất) của hai mảng để thêm vào mảng mới.
Nhiệm vụ: Xem video chi tiết thuật toán Merge Sort.
Hãy chú ý cách nó "Chia" (Split) mảng ra và "Trộn" (Merge) chúng lại.
Nhiệm vụ: Thực hành trải nghiệm mô phỏng chi tiết thuật toán Merge Sort.
Thuật toán sắp xếp trộn gồm 3 bước (Kĩ thuật "Chia để trị"):
Từ dãy gốc ban đầu chúng ta tách chia đôi làm hai dãy con. Tiếp tục chia cho đến khi tất cả các dãy con thu được đều chỉ còn một phần tử.
-> Đây là bước Divide (Chia) trong kĩ thuật Chia để trị.
Khi tất cả các dãy con chỉ còn một phần tử, chúng hiển nhiên đều đã được sắp xếp đúng.
-> Đây là bước Conquer (Trị) trong kĩ thuật Chia để trị.
Từ các dãy đã sắp xếp xong, chúng ta sẽ "trộn" chúng lại với nhau (như Hoạt động 3), 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.
-> Đây là bước Combine (Kết hợp) trong kĩ thuật Chia để trị.
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, tiếp tục cho đến khi nhận được các dãy con đã sắp xếp đúng (Trị) thì tiến hành Trộn các dãy này để nhận được kết quả cuối cùng (Kết hợp). Các bước trên chính là kĩ thuật "Chia để trị".
Dựa vào kiến thức đã học, hãy điền các giá trị đúng vào các ô trống để hoàn thành quy trình sắp xếp trộn.
Nhiệm vụ: Dựa vào kiến thức đã học, hãy điền các giá trị đúng vào các ô trống để hoàn thành quy trình sắp xếp trộ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ảm ơn các em đã chú ý lắng nghe và tham gia các hoạt động trong bài giảng!
Chúc các em học tập tốt và hẹn gặp lại trong các bài giảng tiếp theo!