GATE2025_CS1_Q33

The pseudocode of a function fun() is given below:

fun(int A[0,...,n-1]){ for i=0 to n-2 for j=0 to n-i-2 if (A[j] > A[j+1]) then swap A[j] and A[j+1] }

Let A[0, ...,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, ...,29] as argument, is ______. (Answer in integer)

✅ Final Answer:

The correct answer is 435.

🔹 Short Answer:

The provided pseudocode implements the Bubble Sort algorithm. When the input array is sorted in descending order, the condition `A[j] > A[j+1]` will be true for every comparison made. The total number of swaps will equal the total number of comparisons, which is the sum from i=1 to n-1 of i, or n(n-1)/2. For n=30, this is (30 * 29) / 2 = 435.

🔸 Long Answer:

This question requires analyzing the number of swap operations performed by a given sorting algorithm on a specific worst-case input.

Step 1: Identify the Algorithm

The pseudocode shows a nested loop structure characteristic of Bubble Sort. The outer loop `for i=0 to n-2` controls the number of passes, and the inner loop `for j=0 to n-i-2` performs the pairwise comparisons and swaps. In each pass `i`, the largest unsorted element "bubbles up" to its correct final position at index `n-1-i`.

Step 2: Analyze the Input Condition

The input is an array of 30 distinct integers sorted in descending order. For example, if n=4, the array would be like {50, 40, 30, 20}. The algorithm sorts in ascending order, as indicated by the swap condition `if (A[j] > A[j+1])`.

Because the array is perfectly reverse-sorted, the condition `A[j] > A[j+1]` will be true for every single comparison made by the inner loop. This means a swap operation will occur every time the `if` statement is executed.

Step 3: Count the Number of Comparisons (and Swaps)

Since every comparison leads to a swap, we just need to count the total number of comparisons. Let's trace the number of inner loop iterations for each value of the outer loop `i`:

• When i = 0, `j` goes from 0 to n-2. Number of comparisons = n-1.
• When i = 1, `j` goes from 0 to n-3. Number of comparisons = n-2.
• When i = 2, `j` goes from 0 to n-4. Number of comparisons = n-3.
• ...
• When i = n-2, `j` goes from 0 to 0. Number of comparisons = 1.

The total number of comparisons (and thus swaps) is the sum of an arithmetic series:

Total Swaps = (n-1) + (n-2) + ... + 2 + 1

This is the well-known formula for the sum of the first k integers, where k = n-1.

Sum = k(k+1)/2 = (n-1)(n-1+1)/2 = n(n-1)/2

Step 4: Calculate for n = 30

The problem gives an array A[0, ..., 29], which means the size of the array n = 30.

Substitute n = 30 into the formula:

Total Swaps = (30 * (30 - 1)) / 2
= (30 * 29) / 2
= 15 * 29
= 435

Therefore, the total number of swap operations performed is 435.

Bibliography:
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press. (Chapter 2: Getting Started).

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.