Conditional Expressions and Statements : 08/25/2022

Operations on Variables : 08/24/2022

Variables and Types : 08/23/2022

Welcome to CS 124 : 08/22/2022

Sorting Algorithms

Java

Created By: Geoffrey Challen

/ Updated: 2022-11-01

In this lesson we introduce a new topic: sorting.
Sorting algorithms are both fun to implement, and fun to analyze.
We'll get to practice with iterative and recursive algorithms, and with algorithm analysis.
Let's get started!

Sorting

Sorting is the process of putting things in order.
While it may not feel at first like the most interesting problem to solve, sorting is a core building block for many other algorithms.
Competitions continue to be held for systems that can sort large numbers of items.
And, despite being a very old problem, new sorting algorithms continue to be released with new performance characteristics.
(The sorting algorithm used by default by Java, Python, and other languages dates only to 2002.)

Sorting Basics

For the sake of simplicity most of our examples will follow a few conventions:

We'll sort int arrays. We can sort anything that's Comparable in Java, but using integers makes the comparisons a bit simpler

We'll sort in ascending order

As we examine the performance of our sorting algorithms we'll look at a few things:

How much time does it take?

How much space is required? This in particular becomes a big concern when sorting massive data sets.

And, while there are many sorting algorithms, we'll focus on just a few due to their interesting performance characteristics or real world use cases.
Specifically, we'll implement or analyze:

As a warm up, let's implement and analyze a simple method to determine whether an integer array is already sorted.
We can use this as needed to check our work as we develop additional sorting algorithms!

Implement isSorted.

Interactive Walkthrough

Click on an icon below to start!

Bubble Sort

Now let's actually implement a sorting algorithm.
Our first algorithm, Bubble Sort, follows naturally from the isSorted method that we implement above.
But, rather than just returning when we find out-of-order elements, we'll fix them!
If we do this enough times, the array should end up sorted.

Implement bubble sort.

Interactive Walkthrough

Click on an icon below to start!

Next, let's analyze the performance of our bubble sort implementation.
We'll look at both best and worst case inputs, and try to say something general about the performance of the algorithm.

Insertion Sort

Next, let's look at a different approach called insertion sort.
You'll implement this on the next homework problem.
But let's walk through the approach visually to get you off to a good start!

Walk through insertion sort using a diagram.
This explanation should be language-agnostic!

Show how to complete the homework problem above. Feel free to cover multiple approaches!