11_Lesson_sapxep1

1. Bài toán sắp xếp

Thuật ngữ sắp xếp đề cập đến việc tổ chức lại một tập hợp dữ liệu theo một tiêu chí sắp xếp (đáp ứng tiêu cầu về cụ thể về trình tự).

⚡Ví dụ. Cho dãy số, yêu cầu sắp xếp "theo thứ tự tăng dần (giảm dần)".

- Đầu vào: Dãy n số a₀, a₁,..., a_n-1

- Đầu ra: Dãy được sắp xếp theo thứ tự tăng dần (giảm dần).

​Lập trình một số thuật toán sắp xếp

1. Bài toán sắp xếp

Sắp xếp tại chỗ và không tại chỗ

Sắp xếp tại chỗ khi không phải dùng thêm một dãy khác ở bên ngoài dãy ban đầu để thực hiện sắp xếp (chỉ đổi chỗ các phần tử trong dãy ban đầu).

Nếu sử dụng một dãy khác ở bên ngoài dãy ban đầu để chứa kết quả thì gọi là sắp xếp không tại chỗ.

Nghịch thế

Nếu i < j mà a_i > a_j thì cặp hai phần tử (a_i, a_j) gọi là một nghịch thế. Dãy số chưa sắp đúng thứ tự khi còn ít nhất một nghịch thế.

​Lập trình một số thuật toán sắp xếp

Multiple Choice

Phương án nào sau đây nêu đúng cặp giá trị nghịch thế trong dãy số a₀ < a₁ < ... < a_n-1?

• a_i = a_i+1

• a_i > a_i+1

• a_i < a_i+1

• a_i - a_j+1

Multiple Choice

Phương án nào sau đây nêu đúng đặc điểm của sắp xếp đổi tại chỗ?

• Chỉ đổi chỗ nếu hai giá trị bằng nhau.

• Dãy tồn tại ít nhất hai cặp nghịch thế.

• Không cần một dãy khác bên ngoài.

• Hai phần tử cần đổi chỗ là kiểu kí tự.

Multiple Choice

Tại sao việc sắp xếp dữ liệu là quan trọng trong tin học?

• Để làm cho dữ liệu đẹp hơn

• Để dễ dàng tìm kiếm và truy xuất thông tin

• Để giảm kích thước của dữ liệu

• Để bảo vệ dữ liệu khỏi bị mất

Multiple Choice

Nghịch thể trong một dãy số được định nghĩa như thế nào?

• Hai phần tử có cùng giá trị

• Hai phần tử có giá trị khác nhau

• Hai phần tử có thứ tự không đúng

• Hai phần tử ở cùng một vị trí

2. Thuật toán sắp xếp nổi bọt

Kí hiệu thể hiện thao tác đổi chỗ khi có nghịch thế.

​Lập trình một số thuật toán sắp xếp

2. Thuật toán sắp xếp nổi bọt

Mô tả thuật toán

Ý tưởng: Thực hiện nhiều vòng lặp. 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 xếp đúng thứ tự thì đổi chỗ.
Cài đặt thuật toán

​Lập trình một số thuật toán sắp xếp

3. Thuật toán sắp xếp chèn tuyến tính

​Lập trình một số thuật toán sắp xếp

3. Thuật toán sắp xếp chèn tuyến tính
a. Mô tả thuật toán 

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

​Lập trình một số thuật toán sắp xếp

3. Thuật toán sắp xếp chèn tuyến tính
Cài đặt thuật toán

​Lập trình một số thuật toán sắp xếp

Multiple Choice

Cho danh sách A = [4, 3, 1, 2], khi áp dụng thuật toán sắp xếp nổi bọt một lượt từ trái sang phải, nếu hai phần tử cạnh nhau xếp không đúng thì đổi vị trí, thu được dãy

• [3, 1, 2, 4].

• [3, 1, 2, 4].

• [3, 1, 4, 2].

• [3, 4, 1, 2].

Multiple Choice

Sắp xếp các bước sắp xếp chèn danh sách A = [5, 0, 4, 2, 3].

1.Chèn phần tử 4 vào trước 5, dãy thu được: [0, 4, 5, 2, 3].

2.Chèn phần tử 0 vào trước 5, dãy thu được: [0, 5, 4, 2, 3].

3.Chèn phần tử 3 vào trước 4, dãy thu được: [0, 2, 3, 4, 5].

4.Chèn phần tử 2 vào trước 4, dãy thu được: [0, 2, 4, 5, 3].

• 2,1,4,3

• 1,2,3,4

• 2,1,3,4

• 1,3,2,4

Multiple Choice

Ý tưởng chính của thuật toán sắp xếp chèn là gì?

• Tìm phần tử nhỏ nhất và chuyển nó vào vị trí đầu tiên.

• So sánh từng cặp phần tử liền kề và hoán đổi nếu chúng không đúng thứ tự.

• Chèn từng phần tử vào đúng vị trí trong một mảng con đã sắp xếp.

• Chia mảng thành hai phần và sắp xếp từng phần đệ quy.

Multiple Choice

Mục đích của vòng lặp bên trong trong thuật toán sắp xếp nổi bọt là gì?

• Tìm phần tử lớn nhất và đưa nó về đúng vị trí.

• Tìm phần tử nhỏ nhất và đưa nó về đúng vị trí.

• So sánh và hoán đổi các phần tử liền kề nếu chúng không đúng thứ tự.

• Chia mảng thành các phần nhỏ hơn để sắp xếp.

Multiple Choice

Trường hợp tốt nhất của thuật toán sắp xếp nổi bọt là gì?

• Mảng được sắp xếp ngược lại.

• Mảng đã được sắp xếp.

• Mảng chứa tất cả các phần tử giống nhau.

• Mảng chỉ có hai phần tử.

Multiple Choice

Phát biểu nào sai về thuật toán sắp xếp nổi bọt?

• Thuật toán ổn định, có nghĩa là nó giữ nguyên thứ tự của các phần tử bằng nhau

• Thuật toán tại chỗ, tức là nó sử dụng bộ nhớ phụ không đáng kể.

• Thực hiện số lượng so sánh giống nhau, bất kể thứ tự của đầu vào.

• Số lượng so sánh trong sắp xếp nổi bọt có thể thay đổi tùy thuộc vào mức độ sắp xếp của mảng đầu vào.

Multiple Choice

Trong thuật toán sắp xếp chèn, thuật toán xác định vị trí để chèn phần tử như thế nào trong mỗi lần lặp?

• Bằng cách tìm phần tử ở giữa và chèn vào đó.

• Bằng cách dịch chuyển các phần tử lớn hơn phần tử hiện tại sang bên phải.

• Bằng cách hoán đổi các phần tử liền kề cho đến khi phần tử hiện tại ở đúng vị trí.

• Bằng cách chia mảng ra đệ quy.

Multiple Choice

Cho dãy A = [5, 8, 1, 0, 10, 4, 3], thuật toán sắp xếp chèn sẽ hoạt động như thế nào?

• Sắp xếp từng phần tử vào vị trí đúng trong dãy con đã sắp xếp.

• Đổi chỗ phần tử nhỏ nhất trong dãy còn lại với phần tử đang xét.

• Kiểm tra từng cặp phần tử liền kề và đổi chỗ nếu không đúng thứ tự.

• So sánh từng phần tử và hoán đổi nếu chúng không đúng vị trí.

Multiple Choice

Trong thuật toán sắp xếp chèn, tại sao chúng ta phải dịch chuyển các phần tử lớn hơn giá trị đang xét lên một vị trí?

• Để tìm vị trí chính xác của phần tử mới

• Để giảm số lần so sánh

• Để giảm số lần trao đổi

• Để tăng tốc độ sắp xếp

Multiple Choice

Khi nào chúng ta sử dụng thuật toán sắp xếp nổi bọt?

• Khi số lượng phần tử trong danh sách rất lớn

• Khi cần sắp xếp một danh sách ngẫu nhiên có số lượng nhỏ hoặc trung bình

• Khi danh sách đã được sắp xếp hoàn toàn

• Khi không yêu cầu hiệu suất cao

Multiple Choice

Phát biểu nào sau đây đúng về thuật toán chèn trong sắp xếp danh sách?

• Luôn tìm phần tử lớn nhất và đưa về đầu danh sách

• Thực hiện hoán đổi phần tử ở vị trí đầu và cuối

• Thực hiện sắp xếp dãy theo thứ tự ngẫu nhiên

• Thực hiện dịch chuyển phần tử lớn hơn sang phải để tạo khoảng trống cho phần tử chèn vào

Multiple Choice

Để sắp xếp các mặt hàng trong kho theo số lượng tăng dần, bước nào là cần thiết để thực hiện sắp xếp chèn?

• So sánh từng phần tử với phần tử liền sau nó

• Di chuyển phần tử lớn nhất lên đầu danh sách

• In ra số lượng mặt hàng theo thứ tự ngẫu nhiê

• Tìm vị trí đúng của từng phần tử trong dãy đã sắp xếp

Multiple Choice

Các nhiệm vụ để thực hiện việc sắp xếp gồm:

• So sánh.

• Đổi chỗ.

• So sánh và đổi chỗ.

• Đổi chỗ và xoá.

Multiple Choice

Trong thuật toán sắp xếp nổi bọt, ta thực hiện hoán đổi giá trị các phần tử liền kề khi nào?

• Giá trị của chúng tăng.

• Giá trị của chúng giảm.

• Giá trị của chúng không đúng thứ tự.

• Giá trị của chúng không bằng nhau.

Multiple Choice

Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách hoán đổi các phần tử liền kề bao nhiêu lần?

• Mười lần.

• Nhiều lần.

• Hai lần.

• Một lần.

Multiple Choice

Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách?

• Hoán đổi nhiều lần các giá trị liền kề nếu giá trị của chúng không đúng thứ tự.

• Chèn phần tử vào vị trí thích hợp để đảm bảo danh sách theo đúng thứ tự.

• Chọn phần tử có giá trị lớn nhất đặt vào đầu danh sách

• Chọn phần tử có giá trị bé nhất đặt vào đầu danh sách

Multiple Choice

Cho dãy số: 6, 4, 5, 3. Nếu sử dụng thuật toán sắp xếp nổi bọt để sắp xếp dãy tăng dần thì sau bao nhiêu vòng lặp thì thuật toán kết thúc?

• 2

• 3

• 4

• 5

Multiple Choice

Cho dãy số: 15, 1, 31, 9, 78, 42. Nếu sử dụng thuật toán sắp xếp nổi bọt để sắp xếp dãy trên tăng dần thì sau bao nhiêu lượt đổi chỗ thì thuật toán kết thúc?

• 2

• 3

• 4

• 5

Multiple Choice

Mục đích của thuật toán sắp xếp nổi bọt là gì?

• Tìm kiếm phần tử lớn nhất trong dãy

• Loại bỏ các nghịch thể trong dãy số

• Đếm số phần tử trong dãy

• Tăng kích thước mảng

Multiple Choice

Trong thuật toán sắp xếp chèn tuyến tính, khi nào thì dãy con được coi là có thứ tự?

• Khi dãy con có một phần tử

• Khi dãy con có ít nhất hai phần tử

• Khi dãy con đã được sắp xếp hoàn toàn

• Khi dãy con không có phần tử nào

Multiple Choice

Trong thuật toán sắp xếp nổi bọt, điều gì sẽ xảy ra nếu trong một vòng lặp không có bất kỳ lần đổi chỗ nào?

• Thuật toán tiếp tục chạy mãi mãi

• Thuật toán dừng lại vì dãy đã được sắp xếp

• Thuật toán quay lại vòng lặp trước đó

• Thuật toán chỉ sắp xếp một phần của dãy

Multiple Choice

Trong thuật toán sắp xếp chèn tuyến tính, phần tử nào sẽ được chèn vào dãy đã được sắp xếp?

• Phần tử nhỏ nhất

• Phần tử lớn nhất

• Phần tử tại vị trí đầu tiên của dãy

• Phần tử hiện tại mà đang được xem xét

Multiple Choice

Khi sử dụng hàm sorted() trong Python, kết quả sẽ là gì?

• Dãy số sẽ được sắp xếp tại chỗ

• Dãy số sẽ bị xóa

• Hàm không làm gì cả

• Hàm trả về một dãy mới đã được sắp xếp

Multiple Choice

Khi nào thuật toán sắp xếp nổi bọt (Bubble Sort) được cho là đã hoàn thành?

• Khi không còn cặp phần tử nào là nghịch thế.

• Khi tất cả các phần tử trong dãy đều bằng nhau.

• Khi đã thực hiện đủ n vòng lặp.

• Khi không xảy ra bất kỳ thao tác đổi chỗ nào trong một vòng lặp.

Multiple Choice

Thuật toán sắp xếp chèn (Insertion Sort) hoạt động như thế nào khi chèn một phần tử vào dãy đã sắp xếp?

• Nó thêm phần tử vào cuối dãy và sắp xếp lại toàn bộ dãy.

• Nó sử dụng một dãy tạm thời để lưu trữ các phần tử trong khi sắp xếp.

• Nó chỉ thay đổi vị trí của phần tử mà không cần so sánh với các phần tử khác.

• Nó so sánh phần tử với các phần tử trong dãy và di chuyển chúng sang trái cho đến khi tìm thấy vị trí thích hợp.

​Thực hành

​Bài 1. Cho dãy A. Viết các chương trình sắp xếp dãy A theo thứ tự tăng dần bằng thuật toán sắp xếp chèn và nổi bọt

Bài 2. Cho tệp Diem.txt lưu trữ giá trị điểm của 10 học sinh. Hãy sử dụng thuật toán xắp xếp chèn theo điểm số tăng dần, in kết quả ra màn hình.