bài 21 Các thuật toán sắp xếp đơn giản 3

Sắp xếp chèn có đặc điểm là:

• Là thuật toán ổn định

• Luôn có độ phức tạp O(n log n)

• Không thể sử dụng cho mảng đã sắp xếp

• Là thuật toán phân tách và trị

Trong thuật toán sắp xếp nổi bọt, sau mỗi lần hoán đổi các phần tử:

• Mảng được chia thành hai phần

• Phần chưa sắp xếp sẽ giảm dần

• Mảng sẽ được sắp xếp ngay lập tức

• Phần tử nhỏ nhất sẽ được đưa vào vị trí cuối cùng

Thuật toán sắp xếp nhanh có thể gặp trường hợp xấu nhất khi:

• Phần tử pivot luôn là phần tử nhỏ nhất hoặc lớn nhất

• Mảng đã được sắp xếp hoàn toàn

• Chọn pivot là phần tử giữa mảng

• Mảng có nhiều phần tử trùng lặp

Thuật toán sắp xếp chọn hoạt động bằng cách:

• Chọn phần tử lớn nhất trong mảng và hoán đổi với phần tử cuối cùng

• Tìm phần tử nhỏ nhất trong mảng và hoán đổi với phần tử đầu tiên

• Di chuyển phần tử vào đúng vị trí của nó bằng cách dịch chuyển

• Chia mảng thành hai phần và sắp xếp chúng độc lập

Sắp xếp nhanh có thể bị chậm trong trường hợp:

• Mảng có nhiều phần tử trùng lặp

• Mảng có ít phần tử

• Phần tử pivot được chọn tốt

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

Thuật toán sắp xếp nào dưới đây có thể sử dụng khi dữ liệu đầu vào đã được sắp xếp một phần?

• Sắp xếp nhanh

• Sắp xếp nổi bọt

• Sắp xếp chọn

• Sắp xếp chèn

Thuật toán sắp xếp nhanh có độ phức tạp thời gian trong trường hợp trung bình là:

• O(n)

• O(n log n)

• O(n²)

• O(log n)

Sắp xếp chèn thực hiện như thế nào khi mảng đã được sắp xếp một phần?

• Nó tiếp tục hoán đổi tất cả các phần tử

• Không cần

ung bình là:

• O(n)

• O(n log n)

• O(n²)

• O(log n)

Sắp xếp chèn thực hiện như thế nào khi mảng đã được sắp xếp một phần?

• Nó tiếp tục hoán đổi tất cả các phần tử

• Không cần thực hiện bất kỳ bước hoán đổi nào

• Chỉ hoán đổi phần tử cần thiết vào đúng vị trí

• Nó sẽ sắp xếp lại tất cả các phần tử