The pseudocode of a function $ fun() $ is given below: $$ \text{fun(int A[0, \ldots, n-1])} \{ $$ $$ \text{for } i = 0 \text{ to } n-2 $$ $$ \text{for } j = 0 \text{ to } n - i - 2 $$ $$ \text{if } (A[j] A[j+1]) \text{ then swap } A[j] \text{ and } A[j+1] $$ $$ \} $$ Let $ A[0, \ldots, 29] $ be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if the function $ fun() $ is called with $ A[0, \ldots, 29] $ as argument, is ______ (Answer in integer).

Question

The pseudocode of a function $ fun() $ is given below: $$ \text{fun(int A[0, \ldots, n-1])} \{ $$ $$ \text{for } i = 0 \text{ to } n-2 $$ $$ \text{for } j = 0 \text{ to } n - i - 2 $$ $$ \text{if } (A[j] > A[j+1]) \text{ then swap } A[j] \text{ and } A[j+1] $$ $$ \} $$ Let $ A[0, \ldots, 29] $ be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if the function $ fun() $ is called with $ A[0, \ldots, 29] $ as argument, is ______ (Answer in integer).

cdquestions Admin · Accepted Answer

The pseudocode provided is an implementation of Bubble Sort. Let’s analyze the number of swap operations in the case where the array is initially sorted in descending order: Step 1: Understanding the Loop Execution The outer loop runs from $ i = 0 $ to $ n-2 $, where $ n = 30 $. Therefore, the outer loop executes $ 29 $ times. The inner loop runs from $ j = 0 $ to $ n-i-2 $, meaning the number of iterations decreases as $ i $ increases. Step 2: Calculating Total Comparisons The number of comparisons for each value of $ i $ is: - For $ i = 0 $, the inner loop runs $ n-1 $ times. - For $ i = 1 $, the inner loop runs $ n-2 $ times. - For $ i = 2 $, the inner loop runs $ n-3 $ times. - … - For $ i = n-2 $, the inner loop runs 1 time. Thus, the total number of comparisons is the sum of the first $ n-1 $ integers: $$ \text{Total comparisons} = (n-1) + (n-2) + \ldots + 1 = \frac{n(n-1)}{2} $$ For $ n = 30 $: $$ \text{Total comparisons} = \frac{30 \times 29}{2} = 435 $$ Step 3: Number of Swaps In Bubble Sort, a swap occurs every time a comparison finds that $ A[j] &gt; A[j+1] $. Since the array is initially sorted in descending order, every comparison will result in a swap. Thus, the number of swaps is equal to the total number of comparisons, which is 435 . Final Answer: The number of swap operations performed is 435 .

Show Hint

Solution and Explanation

Top GATE CS Programming and Data Structures Questions

Top GATE CS Questions