Tính thích ứng
Bài học 6 trên 11 trong khóa học Sắp xếp nổi bọt của Coddy.
Chúng ta đã thảo luận về độ phức tạp thời gian của thuật toán sắp xếp nổi bọt, là O(n2) . Nhưng nếu mảng của chúng ta đã được sắp xếp thì sao? Khi đó, thời gian chạy vẫn là O(n2).
Tính thích nghi là gì?
Thuật toán thích nghi là thuật toán thay đổi cách hoạt động dựa trên chuỗi đầu vào.
Vậy thuật toán sắp xếp nổi bọt có tính thích nghi không?
Có, chúng ta có thể làm cho thuật toán sắp xếp nổi bọt có tính thích nghi. Chúng ta cần viết thuật toán sắp xếp nổi bọt với thời gian chạy trong trường hợp xấu nhất là O(n2) và trong trường hợp tốt nhất là O(n) để thuật toán có tính thích nghi. Ở đây, trường hợp tốt nhất là khi mảng đã được sắp xếp.
Chúng ta sẽ dùng một biến cờ kiểu boolean để điều khiển vòng lặp while, nhờ đó thuật toán sẽ dừng sớm nếu mảng đã được sắp xếp từ trước.
while(flag)
{
//code
}
Chúng ta cần lặp lại lượt duyệt cho đến khi mảng được sắp xếp. Chúng ta đã học cách đếm số lần hoán đổi, vì vậy có thể dùng một biến cờ để kiểm tra xem lượt duyệt có cần hoán đổi nào không, rồi thoát khỏi vòng lặp nếu không cần.
Thử thách
Trung bìnhTạo một hàm có tên ad_bubblesort nhận một mảng và kích thước của mảng. Thực hiện thuật toán sắp xếp nổi bọt thích ứng. Nhớ dùng một biến có tên flag để kiểm tra xem có phép hoán đổi nào không.
Tự làm thử
#include <stdio.h>
#include <stdlib.h>
int* ad_bubblesort(int* arr, int arr_size, int n, int* returnSize) {
// Viết code ở đây
*returnSize = n;
return arr;
}
Tất cả bài học trong Sắp xếp nổi bọt
1Kiến thức cơ bản về sắp xếp nổi bọt
Giới thiệuCách hoạt động của sắp xếp nổi bọtHoán đổi các phần tử liền kềThuật toán sắp xếp nổi bọtTự luyện tập: Trình biên dịch C online