Bubble Sort Algorithm in DSA C++ - 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²) 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

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 Sorts the entire array in one pass

B Moves the smallest unsorted element to the beginning

C Moves the largest unsorted element to the end

D Removes duplicates from the array

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(log n)

D O(n)

Bubble Sort uses nested loops, resulting in O(n²) time complexity in the worst case.

Which of these is a simple optimization for Bubble Sort?

A Stop if no swaps happen in a pass

B Use binary search to find elements

C Sort only half the array

D Use recursion instead of loops

If no swaps occur in a pass, the array is already sorted, so Bubble Sort can stop early.

After the first pass of Bubble Sort on an unsorted array, what can we say about the last element?

A It is the smallest element

B It is in the middle

C It is unchanged

D It is the largest element

The largest element "bubbles" to the end after the first pass.

Which data structure does Bubble Sort work on?

A Linked list only

B Array or list

C Tree

D Graph

Bubble Sort works on arrays or lists where elements can be accessed by index.

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

Think about how the biggest number moves to the right in each pass.

Describe one way to improve Bubble Sort's efficiency.

Consider what happens if the array is already sorted.