Bubble Sort Algorithm in DSA Javascript - 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 to fully sort it.

intermediate

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

The time complexity is O(n²) in both average and worst cases because it compares pairs repeatedly for each element.

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 can stop early.

beginner

Write the basic step of Bubble Sort comparing two adjacent elements a[i] and a[i+1].

If a[i] > a[i+1], swap a[i] and a[i+1] to move the larger element towards the end.

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

A Moves the smallest element to the start

B Removes duplicates from the array

C Sorts the entire array at once

D Moves the largest unsorted element to the end

Bubble Sort compares adjacent elements and swaps them to move the largest unsorted element to the end in each pass.

What is the worst-case time complexity of Bubble Sort?

A O(n)

B O(n log n)

C O(n²)

D O(log n)

Bubble Sort has a worst-case time complexity of O(n²) because it compares pairs repeatedly for each element.

Which of these is a way to optimize Bubble Sort?

A Use recursion instead of loops

B Stop if no swaps happen in a pass

C Sort only half the array

D Skip comparing adjacent elements

If no swaps happen during a pass, the array is already sorted and Bubble Sort can stop early.

In Bubble Sort, what happens when two adjacent elements are in the wrong order?

A They are swapped

B They are removed

C They are ignored

D They are duplicated

Bubble Sort swaps adjacent elements if they are in the wrong order to sort the array.

How many passes does Bubble Sort need to sort an array of 5 elements in the worst case?

A 4

B 6

C 5

D 3

Bubble Sort needs n-1 passes, so for 5 elements, it needs 4 passes in the worst case.

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 make Bubble Sort faster when the array is already mostly sorted.

How do you know if the array is sorted before finishing all passes?