Elementary Sorting: Bubble, Selection and Insertion
Bubble, selection, and insertion sort are comparison-based algorithms with average-case time $\Theta(n^2)$.
Summary
Bubble, selection, and insertion sort are comparison-based algorithms with average-case time . Their standard array implementations use auxiliary space, but differ in element movement, adaptivity, and stability.
| Algorithm | Element movement | Best-case time |
|---|---|---|
| Bubble sort | Swaps adjacent out-of-order elements | with no-swap early exit |
🧠 Key Concepts
- Bubble sort
- Selection sort
- Insertion sort
- Sorted prefix
- Sort stability
- In-place sorting
- Early termination
- Inversions
- Write costs
🧠 Quick Check
See what you remember from the summary.
Which best describes how insertion sort processes the next element?
🧠 Flashcards Preview
Tap a card to reveal the definition.
Ready to quiz yourself?
Test what you remember with a full practice quiz on this note. Create a free account and start in seconds.
Full Notes
Read the original note content before deciding whether to save or study from it.
Elementary Sorting: Bubble, Selection and Insertion
📘 Overview Bubble, selection, and insertion sort are comparison-based algorithms with quadratic average-case running time. Their standard array implementations use constant auxiliary space, but differ in how they move elements and exploit existing order.
🧠 Key Idea Bubble sort exchanges adjacent out-of-order elements, selection sort places the smallest remaining element, and insertion sort inserts each new element into a sorted prefix. Algorithm choice depends on existing order, write costs, and whether equal-key records must retain their order.
⚔️ Core Details: - Bubble sort repeatedly scans the unsorted region with adjacent swaps whenever the left key is larger than the right key. - Selection sort swaps the minimum element of the unsorted suffix into its first position. - Insertion sort extends a sorted prefix by shifting strictly larger elements right to make room for the next key. - Bubble sort with a no-swap early exit has best-case time and average- and worst-case time
More ways to study when you copy this note
Copy this note into your library to unlock focused practice sessions and long-term review.
Answer all questions first, then see feedback at the end — the way real exams work.
Focuses each session on what you got wrong, not what you already know.
Full timed exam with all questions, no pausing, and results at the end. Built for board exam prep.
Part of 🗄️ BS Information Systems — 1st Year
Browse this Review Set →More Computer Engineering notes
See all →More in Data Structures and Algorithms
See all →More from NoteLib
Browse NoteLib's public notes →Copy this note to your library and get the full Study Pack instantly — summary, key concepts, and practice quiz included.