Độ phức tạp về thời gian của sắp xếp chèn là gì?
Độ phức tạp về thời gian là lượng thời gian mà một bộ mã hoặc thuật toán thực hiện để xử lý hoặc chạy như một hàm của lượng đầu vào.
Đối với sắp xếp chèn, độ phức tạp về thời gian là theo thứ tự O (n) tức là O lớn của n trong trường hợp tốt nhất. Và trong trường hợp trung bình hoặc trường hợp xấu nhất, độ phức tạp là bậc O (n 2 ).
Độ phức tạp về thời gian của việc sắp xếp khi thuật toán sắp xếp chèn được áp dụng cho n mảng có kích thước như sau:6, 5, 8, 7, 10, 9 …… I, i-1
Độ phức tạp về thời gian của hình thức sắp xếp mảng trên là O (n). Hãy xem thuật toán này một cách cẩn thận, ở đây tất cả các cặp được hoán đổi từ vị trí ban đầu của chúng, tức là vị trí của phần tử 1 và phần tử 2 được hoán đổi cho nhau, 3 và 4 được hoán đổi cho nhau, v.v. Vì vậy, trong khi sắp xếp, thuật toán sẽ chỉ cần một thao tác n lần để sắp xếp thuật toán này.
Xác định sắp xếp chèn và Viết mã cho sắp xếp chèn?
Sắp xếp chèn là một thuật toán sắp xếp sắp xếp cấu trúc dữ liệu bằng cách đặt phần tử vào vị trí của nó trong một mảng đã sắp xếp.
Đoạn mã dưới đây hiển thị chức năng sắp xếp chèn -
Ví dụ
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++){
int element = arr[i];
int j = i-1;
while (j >= 0 && arr[j] > element){
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = element;
}
}