can you exaplin this? Given the following algorithm: To sort an array A [0.. N -

Question

can you exaplin this?

Given the following algorithm:

To sort an array A[0..N-1]:

for (int last = N -1; last >= 1; last --) {

// Move the largest entry in A[0…last] to A[last]

for (int index = 0; index <= last-1; index++)   {    

       //swap adjacent elements if necessary

        if (A[index] > A[index+1])   {

            int temp = A[index];

            A[index] = A[index+1];

            A[index + 1] = temp;

        }

}

}

1. Compute the TOTAL primitive operations

2. Compute the Big O for the algorithm

Explanation / Answer

Hi Friend,

Please find my answer.

The Given code is nothing but , it is Bubble Sort code.

Let's go through the cases for Big O for Bubble Sort

Case 1) O(n) (Best case) This time complexity can occur if the array is already sorted, and that means that no swap occurred and only 1 iteration of n elements

Case 2) O(n^2) (Worst case) The worst case is if the array is already sorted but in descending order. This means that in the first iteration it would have to look at n elements, then after that it would look n - 1 elements (since the biggest integer is at the end) and so on and so forth till 1 comparison occurs. Big-O = n + n - 1 + n - 2 ... + 1 = (n*(n + 1))/2 = O(n^2)

1. Compute the TOTAL primitive operations

Ans:  (n*(n + 1))/2

2. Compute the Big O for the algorithm

Ans: O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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