Bubble Sort Flashcards
What is sorting?
Is a fundamental concept in computer science that involves arranging a collection of items in a specific order
Data collections become very large: millions of data entities or items
We often need to repeatedly search for items in datasets
Searching random data is time-consuming
By arranging data in a specific order:
= sorting improves organization, accessibility, and the performance of various algorithms (ex. Binary
Search)
• Choosing the right sorting algorithm requires:
= considering factors such as input size, stability, memory requirements, and performance considerations
What are the two common sorting algorithms we will learn in this class?
There are various ones, which each have their strength and weaknesses
Some common ones include:
- Bubble sort
- Selection sort
What is bubble sort?
It is a simple sorting algorithm that repeatedly compares adjacent elements and swaps them if they are in the wrong order
The basic idea is to repeatedly scan the list and compare adjacent pairs of elements:
= If a pair is found in the wrong order (the element on the left is greater than the one on the right), they are swapped.
This process is repeated until the list is fully sorted, with larger elements gradually moving towards the end
What is the visualization of bubble sort?
Imagine a row of bubbles rising to the surface of water:
= the larger bubbles (representing greater elements) will gradually move upwards
= while the smaller bubbles (representing lesser elements) will settle towards the bottom
Similarly, in Bubble Sort, the larger elements “bubble” towards the end of the list, while the smaller elements gradually “settle” towards the beginning
What is the algorithm involved in bubble sort?
- Start at the beginning of the list
- Compare the current element with the next element
- If the current element is greater than the next element:
= swap them - Move to the next element and repeat steps 2 and 3 until the end of the list is reached
- Repeat steps 1-4 until the list is sorted
Bubble sort starts at the “_____” element and advances one element at a time
First
In the standard bubble sort algorithm, the “_____” loop always iterates for the maximum number of passes, even if the list is already sorted
This results in what?
Outer
= results in UNNECESSARY iterations and comparisons
What is a short bubble sort?
Also called Optimized Bubble Sort:
= Is a variation of the Bubble Sort algorithm that includes an optimization to reduce the number of unnecessary comparisons
It introduces a boolean flag called “swapped.” This
flag tracks whether any swaps were made in a pass
= If no swaps are made, it means the list is already sorted, and the algorithm can terminate early
The algorithm starts with an initial pass counter set to the length of the list minus one:
= In each pass, it compares adjacent elements and
swaps them if they are out of order
= the pass counter is decremented after each pass
The algorithm continues until a pass completes without any swaps, indicating that the list is sorted
What are bubble sort benefits and limitations?
It is easy to understand and implement:
= making it useful for educational purposes and small datasets
NOT efficient for large lists:
= due to its time complexity of O(n^2)
These are still generally less efficient compared to more advanced sorting algorithms like Merge Sort or Quick Sort
