AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Mediumsortinginversions

~90s

Swaps in a bubble sort

How many swaps does bubble sort perform while sorting [5, 4, 3, 2, 1] into ascending order?

Show the answer and the worked solution

Correct answer: C.

10

Worked solution

  1. Each swap in bubble sort exchanges two adjacent elements, removing exactly one inversion.
  2. The array is in exactly reverse order, so every pair of positions is an inversion.
  3. There are C(5, 2) = 10 such pairs, so bubble sort performs 10 swaps.

Answer: 10.

The idea

The swap count of any adjacent-exchange sort equals the number of inversions in the input. That is also why insertion sort runs in O(n + inversions) and is excellent on nearly sorted data.

Shortcut. On a reversed array every comparison finds the larger element in front, so the passes swap 4, 3, 2 and 1 times: 4 + 3 + 2 + 1 = 10.

Common trap. 4 counts only the swaps in the first pass, which carries 5 to the end; three more passes are still needed.

Swaps in a bubble sort — Aptitude Question

Swaps in a bubble sort: How many swaps does bubble sort perform while sorting [5, 4, 3, 2, 1] into ascending order? Answer and worked solution on CodeKairo.

Question

How many swaps does bubble sort perform while sorting [5, 4, 3, 2, 1] into ascending order?

Options

  1. 4
  2. 5
  3. 10
  4. 20
Show the answer and the worked solution

Correct answer: C. 10

Worked solution

  1. Each swap in bubble sort exchanges two adjacent elements, removing exactly one inversion.
  2. The array is in exactly reverse order, so every pair of positions is an inversion.
  3. There are C(5, 2) = 10 such pairs, so bubble sort performs 10 swaps.

Answer: 10.

The idea

The swap count of any adjacent-exchange sort equals the number of inversions in the input. That is also why insertion sort runs in O(n + inversions) and is excellent on nearly sorted data.

Shortcut. On a reversed array every comparison finds the larger element in front, so the passes swap 4, 3, 2 and 1 times: 4 + 3 + 2 + 1 = 10.

Common trap. 4 counts only the swaps in the first pass, which carries 5 to the end; three more passes are still needed.

All Data Structures & Algorithms questions · placement mock tests