Recursive Bubble Sort

Easy

One pass floats the max, then recurse

Problem

Bubble sort written recursively: one pass floats the largest element to the end, then recurse on the rest.

In simple words

Bubble the largest to the end, then recurse on the smaller front part.

The idea

One full pass of adjacent swaps guarantees the largest element ends up last, so the rest of the problem is the same sort on the first n-1 elements. Writing it recursively makes that invariant explicit — the loop version hides it inside a shrinking bound.

The trick

After pass k, the last k elements are final.
If a pass makes no swaps the array is sorted; return early for the O(n) best case.

←→stepspaceplay

1/24

Brute force

timeO(n²)spaceO(1)

Largest bubbles to the end.

1// bubble the largest to the end each pass2for (let i = 0; i < n - 1; i++) {3  for (let j = 0; j < n - 1 - i; j++) {4    if (a[j] > a[j + 1])5      [a[j], a[j + 1]] = [a[j + 1], a[j]];6  }7}8return a;

Input

array: [5, 2, 8, 1, 9, 3]

Memory

j: —
j+1: —

Output

result: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: nums = [5, 1, 4, 2, 8]
Output:: [1, 2, 4, 5, 8]
Explanation:: Bigger values bubble to the end each pass.

Example 2

Input:: nums = [1, 2, 3]
Output:: [1, 2, 3]
Explanation:: Already sorted — one clean pass.

Example 3

Input:: nums = [3, 2, 1]
Output:: [1, 2, 3]
Explanation:: Reversed input flips to order.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.