Bài 21 các thuật toán sắp xếp đơn giản 2

Thuật toán sắp xếp nổi bọt có ưu điểm là:

• Dễ dàng cài đặt

• Hoàn hảo cho mảng có nhiều phần tử trùng lặp

• Không cần so sánh giữa các phần tử

• Không thay đổi mảng nhiều

Sắp xếp nhanh có thể sắp xếp mảng bằng cách:

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

• So sánh các phần tử theo thứ tự giảm dần

• Đưa các phần tử vào đúng vị trí bằng cách so sánh liên tiếp

• Chọn phần tử pivot và phân chia mảng

Thuật toán nào có thể cải thiện hiệu suất khi dữ liệu được phân chia đều?

• Sắp xếp nhanh

• Sắp xếp chọn

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

• Sắp xếp chèn

Đối với thuật toán sắp xếp nhanh, việc chọn pivot có ảnh hưởng trực tiếp đến:

• Độ phức tạp thời gian của thuật toán

• Sự ổn định của thuật toán

• Kết quả của thuật toán

• Mảng sắp xếp hoàn toàn

Trong thuật toán sắp xếp nhanh, sau khi chọn pivot, mảng được:

• Chia thành hai phần và tiếp tục sắp xếp từng phần

• Sắp xếp theo thứ tự giảm dần

• Đưa phần tử pivot vào đúng vị trí và dừng lại

• Hoán đổi phần tử pivot với phần tử cuối mảng

Sắp xếp nổi bọt có đặc điểm là:

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

• Chạy rất nhanh đối với các mảng có số lượng phần tử lớn

• Được cài đặt phức tạp

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

Khi số lượng phần tử trong mảng tăng lên, thuật toán sắp xếp nổi bọt:

• Chạy nhanh hơn nhiều

• Không thay đổi về hiệu suất

• Chạy chậm hơn rất nhiều

• Vẫn chạy với tốc độ O(n log n)

Thuật toán sắp xếp nào dưới đây có thể sắp xếp các phần tử mà không thay đổi thứ tự của các phần tử

Thuật toán sắp xếp nào dưới đây có thể sắp xếp các phần tử mà không thay đổi thứ tự của các phần tử trùng lặp?

• Sắp xếp nhanh

• Sắp xếp chèn

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

• Sắp xếp chọn

Để tối ưu thuật toán sắp xếp nổi bọt, ta có thể:

• Kiểm tra xem mảng đã được sắp xếp chưa sau mỗi vòng lặp

• Dùng thuật toán sắp xếp nhanh thay thế

• Giảm số lượng vòng lặp

• Cải thiện cách hoán đổi phần tử