1) suppose a list is {2, 9 , 5, 4, 8, 1} after the first pass of bubble sort, th

Question

1) suppose a list is {2, 9 , 5, 4, 8, 1} after the first pass of bubble sort, the list becomes ______________

Question options:

A) 2, 5, 4, 8, 1, 9

B) 2, 9, 5, 4, 8, 1

C) 2, 1, 5, 4, 8, 9

D) 2, 9, 5, 4, 1, 8

E) 2, 5, 9, 4, 8, 1

2) The worst-time complexity for bubble sort is ________.

Question options:

3) The average-time complexity for merge sort is ________.

Question options:

4) The worst-time complexity for quick sort is ________.

Question options:

5) The average-time complexity for quick sort is ________.

Question options:

6) To add a new node, you need to start a process by first placing it as ________ and move it up to maintain the heap property.

Question options:

7) The average-time complexity for heap sort is ________.

Question options:

8) A list is sorted by selecting the largest element in the list and swapping it with the last one. This technique is called ________.

Question options:

A) O(1) B) O(logn) C) O(n) D) O(nlogn) E) O(n*n)

Explanation / Answer

Ans1) 2, 5, 4, 8, 1, 9

Explaination:

The buuble sort will sort like this.

2, 9 , 5, 4, 8, 1
2, 5, 9, 4, 8, 1
2, 5, 4, 9, 8, 1
2, 5, 4, 8, 9,1
2, 5, 4, 8, 1, 9

So at the end of first pass 2, 5, 4, 8, 1, 9 will be result.

Ans2) The worst time complexity for bubble sort is O(n^2). This occurs when the array is reverese sorted.

Each element is placed at wrong position. The total number of comparsion will be n times n so complexity O(n^2)

Ans 3) Average time complexity for merge sort is O(n log(n)).

There are 3 part of divide and rule in merge sort. Suppose there are n elements

1.   Constant time is taken by divide step. The size doesn't matter.
2. The next step that is conquer step we have to recurively sort 2 subarrays of approx n/2 element
3. The last step that is combine step which merges total of n elements.

Ans 4) O(n^2)

There are 3 cases in which the worst case occur:

> The elements are same

> The elements are arranged in reverse order

> The elements are already sorted

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.