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).
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: "3, 5, 9, 1, 8, 0, 2, 6, 4, 10". Một lượt của vòng for i = 0 đến n-2 chỉ so từng cặp kề nhau đúng một lần từ đầu tới cuối, nên tác dụng duy nhất là đẩy phần tử lớn nhất về cuối. Chạy tay trên 5, 3, 9, 10, 1, 8, 0, 2, 6, 4: cặp 5 và 3 đổi cho 3, 5; 5 với 9 rồi 9 với 10 đều đúng thứ tự nên giữ nguyên; từ đó 10 là phần tử đang được mang đi và lần lượt đổi với 1, 8, 0, 2, 6, 4 nên trôi hẳn về cuối, mỗi phần tử bị 10 vượt qua chỉ dịch trái đúng một ô. Vì vậy "3, 5, 9, 8, 1, 0, 2, 6, 4, 10" sai vì nó đổi 1 với 8 dù 1 nhỏ hơn 8; "3, 5, 9, 1, 8, 0, 2, 4, 6, 10" sai vì nó đổi thêm 6 với 4, nhưng khi 10 đã vượt qua 6 thì chỉ số i đã đi quá cặp đó và một lượt không quay lại; "3, 5, 9, 0, 1, 8, 2, 6, 4, 10" sai vì 0 nhảy trái hai ô, trong khi một lượt chỉ kéo được một phần tử nhỏ sang trái đúng một ô.
Cùng phần 6
Select the most correct statement about the complexity of bubble sortCó lời giảiCâu hỏiSelect the most correct statement about the complexity of mergesortCó lời giảiCâu hỏiPartitioning is a technique used in quicksort. The following is a partition pseudocode for sorting from smallest to largest:
partition the array a from index low to index up
x := a[low], i=low, j=up
do
increase i and stop at i, where a[i]>x
decrease j and stop at j, where a[j]<=x
if(i<j) swap a[i] with a[j]
while(i<j)
swap a[low] with a[j]
Consider the list of eight integers (n=8) below:
15, 13, 18, 19, 17, 12, 16, 14
What is the list after it is partitioned with low = 0 and up = n-1?Có 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