C5 CTDL

Sắp xếp chọn (Selection Sort) - Đặc điểm, Ưu điểm, Nhược điểm?

• Dễ hiểu và dễ cài đặt.

• Không cần bộ nhớ bổ sung ngoài bộ nhớ đã có (O(1) bộ nhớ phụ).

• Độ phức tạp thời gian O(n²), không hiệu quả đối với các danh sách lớn.

• Số lần hoán đổi phần tử là tối đa.

Sắp xếp nổi bọt (Bubble Sort) - Đặc điểm, Ưu điểm, Nhược điểm?

• Dễ hiểu và dễ cài đặt.

• Trong trường hợp danh sách đã gần sắp xếp, có thể giảm số lần duyệt qua danh sách.

• Độ phức tạp thời gian O(n²), rất chậm đối với danh sách lớn.

• Số lần hoán đổi cũng rất lớn.

Sắp xếp chèn (Insertion Sort) - Đặc điểm, Ưu điểm, Nhược điểm?

• Tốt cho các danh sách nhỏ hoặc danh sách đã gần sắp xếp.

• Có thể tiết kiệm thời gian nếu danh sách đã gần sắp xếp.

• Độ phức tạp thời gian O(n²), không hiệu quả với danh sách lớn.

Sắp xếp nhanh (Quick Sort) - Đặc điểm, Ưu điểm, Nhược điểm?

• Thời gian trung bình O(n log n), thường rất nhanh với danh sách lớn.

• Sử dụng bộ nhớ phụ O(log n), là thuật toán sắp xếp rất hiệu quả.

• Trong trường hợp xấu (khi pivot luôn là phần tử nhỏ nhất).

Tìm kiếm tuyến tính (Linear Search) - Đặc điểm:

• Duyệt qua tất cả các phần tử trong danh sách từ đầu đến cuối để tìm kiếm phần tử cần tìm.

• Dễ hiểu và dễ cài đặt.

• Không yêu cầu danh sách phải được sắp xếp.

• Độ phức tạp thời gian O(n), có thể rất chậm đối với danh sách lớn.

Tìm kiếm nhị phân (Binary Search) - Đặc điểm:

• Chỉ áp dụng cho các danh sách đã được sắp xếp.

• Duyệt qua danh sách bằng cách chia đôi danh sách tại mỗi bước.

• Độ phức tạp thời gian O(log n), rất nhanh đối với danh sách lớn.

Để đánh giá tính hiệu quả của một thuật toán sắp xếp, ngoài thời gian thực hiện, bạn cần xem xét yếu tố nào khác? Tại sao yếu tố đó quan trọng?

• Bộ nhớ sử dụng (Space Complexity)

• Ổn định (Stability)

Sắp xếp chọn (Selection Sort) - Độ phức tạp thời gian?

• O(n)

• O(n²)

• O(log n)

• O(n log n)

Sắp xếp nổi bọt (Bubble Sort) - Độ phức tạp thời gian?

• O(n)

• O(n²)

• O(log n)

• O(n log n)

Sắp xếp chèn (Insertion Sort) - Độ phức tạp thời gian?

• O(n)

• O(n²)

• O(log n)

• O(n log n)