Select the most correct statement about the complexity of bubble sort
4 phương ánCó giải thích
Các phương án trả lời
Chọn một phương ánLời giảiChọn phương án để mở
Đáp án đúng: "The best case is O(n), and the worst case is O(n^2)". Bubble sort chuẩn có cờ đánh dấu đã xảy ra đổi chỗ hay chưa: với mảng đã sắp sẵn, lượt quét đầu làm n-1 phép so sánh mà không đổi chỗ lần nào nên thuật toán dừng ngay, cho O(n); với mảng sắp ngược, mỗi lượt chỉ đưa được một phần tử về chỗ nên phải chạy n-1 lượt với tổng khoảng n(n-1)/2 phép so sánh và đổi chỗ, cho O(n^2). Phương án "Both best and worst cases are O(n^2)" chỉ đúng với bản viết không kiểm cờ đổi chỗ, tức luôn chạy đủ n-1 lượt bất kể dữ liệu, điều kiện mà câu hỏi không nêu. Phương án "The best case is O(n), and the worst case is O(nlogn)" sai ở trường hợp xấu: thuật toán chỉ so sánh các cặp kề nhau nên không có cách nào hạ xuống nlogn. Phương án "The best case is O(nlogn), and the worst case is O(n^2)" sai ở trường hợp tốt: một lượt quét sạch đã đủ kết luận, tốn đúng n-1 phép so sánh.
Cùng phần 6
The following is the main part of bubble sort pseudocode:
do
swapped := false
for i := 0 to n-2
if a[i] > a[i+1] then
swap(a[i],a[i+1])
swapped := true
end if
end for
while swapped
Consider the list of ten integers below:
5, 3, 9, 10, 1, 8, 0, 2, 6, 4
What is the list after the FIRST iteration (for i = 0 to n-2) in a bubble sort? (sorting from smallest to largest).Có lời giảiCâu hỏiThe following is the main part of selection sort pseudocode:
for i := 0 to n-2 // large loop
find a[k], where a[k] = min {a[i], a[i+1],...,a[n-1]}
if k # i then swap a[i] with a[k]
end for
Consider the list of ten integers below:
7, 5, 11, 12, 3, 10, 2, 4, 8, 6
What is the list after the FIRST TWO iterations of the large loop in a selection sort? (sorting from smallest to largest).Có lời giảiCâu hỏiSelect the most correct statement about the complexity of mergesortCó lời giảiCâu hỏiCả 20 câu của chủ đề20 câu
Xuất hiện trong 1 bộ đề
Đi tiếp từ đây