Bubble Sort Algorithm in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Bubble Sort Algorithm?

Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order, "bubbling" the largest unsorted element to the end in each pass.

beginner

How many passes does Bubble Sort make in the worst case for an array of size n?

In the worst case, Bubble Sort makes n-1 passes through the array.

beginner

What is the time complexity of Bubble Sort in the average and worst cases?

The time complexity is O(n²) because it compares and swaps elements in nested loops.

intermediate

How can Bubble Sort be optimized to stop early if the array is already sorted?

By adding a flag to check if any swaps happened in a pass; if no swaps occur, the array is sorted and the algorithm stops early.

beginner

Show the state of the array after the first pass of Bubble Sort on [5, 3, 8, 4, 2].

After first pass: [3, 5, 4, 2, 8] because 5 swaps with 3, then 8 stays, 4 swaps with 8, 2 swaps with 8.

What does Bubble Sort do in each pass through the array?

A Swaps adjacent elements if they are in the wrong order

B Finds the minimum element and places it at the start

C Divides the array into halves and sorts each

D Builds a heap structure

Bubble Sort compares adjacent elements and swaps them if needed, moving the largest unsorted element to the end.

What is the best case time complexity of Bubble Sort when optimized with a swap flag?

A O(n)

B O(n log n)

C O(n²)

D O(log n)

If the array is already sorted, the optimized Bubble Sort stops after one pass, resulting in O(n) time.

Which of these is NOT true about Bubble Sort?

A It has a worst-case time complexity of O(n²)

B It is a stable sorting algorithm

C It swaps adjacent elements

D It always requires n-1 passes

With optimization, Bubble Sort can stop early if no swaps occur, so it does not always require n-1 passes.

After the first pass of Bubble Sort on [4, 2, 7, 1], what is the array?

A [4, 2, 7, 1]

B [2, 4, 1, 7]

C [1, 2, 4, 7]

D [2, 1, 4, 7]

Swaps happen between 4 and 2, then 7 and 1, resulting in [2, 4, 1, 7].

Which sorting algorithm is generally faster than Bubble Sort for large datasets?

A Selection Sort

B Insertion Sort

C Merge Sort

D Bubble Sort

Merge Sort has better time complexity O(n log n) and is faster on large datasets than Bubble Sort's O(n²).

Explain how Bubble Sort works step-by-step on a small array.

Think about how bubbles rise to the surface in water.

Describe one way to optimize Bubble Sort and why it helps.

Consider what happens if the array is already sorted.