Elementary Sorts: Bubble Sort and Selection Sort, Explained

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 16.1 Free with a free account

Elementary Sorts: Bubble Sort and Selection Sort

Data Structures and Algorithms · Chapter 16: Sorting, Selection, and Text ProcessingSection 16.1 · lesson 67 of 8710 min · free with a free account

← Balanced Trees Compared: Red-Black Trees and TreeMapNext lesson: Merge Sort: Split in Half, Sort Each Piece, Combine →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

How bubble sort and selection sort work and what they cost.

  • Trace bubble sort and selection sort pass by pass on a small array
  • Count the comparisons and swaps each sort makes and explain why both are order n squared
  • Explain when bubble sort's early exit saves work and when it does not
  • Distinguish a stable sort from an unstable one using bubble sort and selection sort

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,385 words). Read along, or search it.

Opening Question

Counting Comparisons, Swaps, and Passes

Sorting puts the elements of an array in order, and it's one of the most common jobs a program does. The two simplest ways to do it fit in a dozen lines each: bubble sort and selection sort. Both sort in place, with no extra array. But how much work do they really do? And when is that work acceptable? To answer, every sort here counts its comparisons, its swaps, and its passes. Those counts measure the work itself, whatever the speed of the computer.

Core Idea

One Pass Parks the Largest Value

Bubble sort scans the array from left to right, looking at each pair of neighbors. Whenever the left value is larger, it swaps them. On 5, 1, 4, 2, 8: 5 is larger than 1, so swap. Then 5 and 4, swap. 5 and 2, swap. And 5 and 8 are already in order. A large value keeps being carried right until it meets a larger one. So after one pass, the largest value, 8, sits in its final place at the end, like a bubble rising to the surface.

Java Code

Bubble Sort With a Swapped Flag

Here's bubble sort in Java, with the counters. The outer loop counts passes. The inner loop compares a of j with its right neighbor, and swaps when they're out of order. Since each pass parks one more large value at the end, the next pass can stop one position sooner. That's why the inner loop runs to n minus one minus pass. And the flag swapped records whether this pass changed anything. If a whole pass makes no swap, every neighbor pair is in order, so the array is sorted, and it can stop early. That early exit costs just one boolean, and one test per pass.

Sample Run

Three Passes and Four Swaps

Main sorts 5, 1, 4, 2, 8 twice: once with the early exit, and once without. With it: three passes, nine comparisons, and four swaps. Pass three found nothing to swap, so the sort stopped. Without it, there's one more pass of a single comparison, just to look at an array that was already sorted. The swaps are the same four.

Experiment

Small Values Crawl Left Slowly

How much does the early exit save? It depends on the input, in a surprising way. In one pass, a large value can travel a long way right. But a small value moves left only one position per pass. This program builds two arrays of 1,000 elements, each one move away from sorted. In the first, the smallest value is last. In the second, the largest value is first. Smallest last needed 999 passes: the 1 crawls left, one step at a time. Largest first needed just two passes: one to carry 1000 to the end, and one to confirm.

Measurement

Early Exit Saves Little on Random Data

On 1,000 elements, the early exit shines on sorted input: one pass, 999 comparisons. And on a large value out of place at the front. But on random data, averaged over 100 arrays, it saved about 900 comparisons out of nearly 500,000: about 0.2 percent. On reversed data, and with the smallest value last, it saved nothing.

Java Code

Selection Sort Finds the Smallest Value

Selection sort works the other way around. In step i, it scans from position i to the end, to find where the smallest remaining value lives. The inner loop only reads the array, and remembers the index of the smallest in min. Only after the scan does it swap, once, moving that value to position i. If the smallest value is already at position i, the test min not equal to i skips the swap. Everything left of position i is final, and never looked at again.

Sample Run

Ten Comparisons but Only Two Swaps

Run it on the same five values. Ten comparisons, one more than bubble sort's early exit needed. But only two swaps, against four. And selection sort can never stop early. Finding the smallest remaining value means looking at all of them, however the array is arranged. Its comparisons don't depend on the input.

Quick Check

Swaps on a Reversed Four-Value Array

Quick check. Selection sort runs on four values in reverse order: 4, 3, 2, 1. How many swaps does it make? Pause and predict. Just two swaps. The first step finds the 1 at the end, and swaps it with the 4: 1, 3, 2, 4. The next step swaps the 3 and the 2: 1, 2, 3, 4. The last step finds the 3 already in place, so min equals i, and there's no swap. Three would be one swap per step. Six is what bubble sort makes here.

Comparison

One Bubble Swap per Inversion

Here's what each sort did on 1,000 elements. Selection sort always makes 499,500 comparisons, whatever the arrangement. Bubble sort's swaps depend heavily on the input. Each swap fixes exactly one pair of values in the wrong order, called an inversion. So it makes one swap per inversion: about 250,000 on random data. Selection sort makes at most n minus one swaps: 993 on random data, and only 500 on reversed data. When moving an element is costly, like copying a large record, that matters most.

Stability

Bubble Sort Keeps Equal Records in Order

One more difference. A sort is stable if equal values keep their original order. That matters when each element is a record, sorted by one field. Here, three records are sorted by their number: 2a, 2b, and 1c. The letters show the original order of the two 2s. Bubble sort gives 1c, 2a, 2b. It swaps only neighbors that are strictly out of order, so equal values never pass each other. Selection sort gives 1c, 2b, 2a. Its first swap jumped 2a over its equal 2b. So bubble sort is stable, and selection sort, as written, is not.

Analysis

Why Both Sorts Grow Quadratically

Why are both sorts order n squared? Selection sort's inner loop runs n minus one times in the first step, then n minus two, and so on, down to one. That sum is n times n minus one, over two. For 1,000 elements, it's 499,500, exactly as measured. Bubble sort without the early exit does the same scans. So when n doubles, the comparisons grow about fourfold, from row to row. Bubble swaps quadruple too, while selection swaps only double.

Quick Check

Selection Sort on Nearly Sorted Data

Quick check. An array of 2,000 values is sorted, except that the largest value sits first. Selection sort runs on it. How many comparisons does it make? Pause and predict. 1,999,000, the full n times n minus one over two. Selection sort scans the whole unsorted part in every step, however close to sorted the array is. 3,997 is what bubble sort with the early exit needs here: two passes, since a large value at the front moves fast. And 1,999 would be one pass.

Common Mistake

Sorting a Thousand Equal Values

Now a classic mistake. This program bubble sorts 1,000 equal values. With the correct test, strictly greater, one pass finds no swap, and the sort stops.

Common Mistake

Greater Than or Equal Breaks the Exit

Change the test to greater than or equal, and rebuild. Now equal neighbors get swapped, so every pass swaps something. The early exit never fires: 999 passes, and 499,500 pointless swaps. The result is still sorted, which is why this bug hides so well. Equal values also get reordered, so the sort is no longer stable. Swap only when the left value is strictly greater.

More Pitfalls

Flag Placement and Loop Bounds

Three more slips are worth knowing. Declaring the swapped flag outside the pass loop: once any swap happens, it stays true, and the early exit is lost. Running the inner loop to the end on every pass: still sorted, but the work roughly doubles. And a bound of j less than n minus pass reads one past the end. Java stops it with an ArrayIndexOutOfBoundsException.

When to Use

Small Arrays and Costly Moves

So when is an elementary sort acceptable? On one test machine, 1,000 random values took under a millisecond with either sort. But each doubling made them about four times slower. At 100,000 values, selection sort took about two seconds, and bubble sort about fifteen. Java's built-in Arrays dot sort took about six milliseconds. So use them for small arrays, teaching, or quick prototypes. Prefer selection sort when moving elements is costly. Beyond a few thousand elements, use a faster sort.

Key Takeaways

Bubble Versus Selection in Brief

To sum up. Bubble sort swaps out-of-order neighbors, and each pass parks the largest remaining value at the end. Selection sort finds the smallest remaining value, and makes at most one swap per step. Run in full, both make n times n minus one over two comparisons: order n squared. Bubble sort's early exit helps only when few passes are needed. Bubble sort is stable, and selection sort, as written, isn't.

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Elementary Sorts: Bubble Sort and Selection Sort

How does bubble sort work?
Bubble sort repeatedly scans an array from left to right, comparing each pair of neighbors and swapping them when the left value is larger. After the first pass, the largest value sits in its final place at the end, so each later pass can stop one position sooner. A swapped flag lets the sort stop early once a full pass makes no swap, because every neighbor pair is then in order.
What is the difference between bubble sort and selection sort?
Both are in-place, order n squared sorts, but they spend their work differently. Bubble sort swaps neighbors, making one swap per inversion, about 250,000 swaps on 1,000 random values. Selection sort scans for the smallest remaining value and makes at most one swap per step, so at most n minus 1 swaps. Bubble sort is stable and can stop early; selection sort, as usually written, is neither.
How many comparisons does selection sort make?
Selection sort makes n(n-1)/2 comparisons on every input of n elements, because each step scans the whole unsorted part to find the smallest value. The scans cover n minus 1 positions, then n minus 2, down to 1. For 1,000 elements that is 499,500 comparisons, and for 2,000 elements it is 1,999,000, even when the array is already nearly sorted.
Why should bubble sort swap only when the left value is strictly greater?
Swapping only when the left value is strictly greater keeps bubble sort stable and lets the early exit work. If the test is a[j] >= a[j + 1], equal neighbors get swapped too, so passes over equal values keep swapping and the early exit can fail to fire. On 1,000 equal values that means 999 passes and 499,500 pointless swaps. The output still looks sorted, which hides the bug, but equal records lose their original order.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Data Structures and Algorithms.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →