Kotlinlearncs.online LogoJava

    ← Prev

    Index

    Next →

    Kotlin
    Java

    • Merge Sort : 52

    • Sorting Algorithms : 51

    • Practice with Recursion : 50

    • Trees and Recursion : 49

    • Trees : 48

    • Recursion : 47

    • Lists Review and Performance : 46

    • Linked Lists : 45

    • Algorithms and Lists : 44

    • Lambda Expressions : 43

    • Anonymous Classes : 42

    • Practice with Interfaces : 41

    • Implementing Interfaces : 40

    • Using Interfaces : 39

    • Working with Exceptions : 38

    • Throwing Exceptions : 37

    • Catching Exceptions : 36

    • References and Polymorphism : 35

    • References : 34

    • Data Modeling 2 : 33

    • Equality and Object Copying : 32

    • Polymorphism : 31

    • Inheritance : 30

    • Data Modeling 1 : 29

    • Static : 28

    • Encapsulation : 27

    • Constructors : 26

    • Objects, Continued : 25

    • Introduction to Objects : 24

    • Compilation and Type Inference : 23

    • Practice with Collections : 22

    • Maps and Sets : 21

    • Lists and Type Parameters : 20

    • Imports and Libraries : 19

    • Multidimensional Arrays : 18

    • Practice with Strings : 17

    • null : 16

    • Algorithms and Strings : 15

    • Strings : 14

    • Functions and Algorithms : 13

    • Practice with Functions : 12

    • More About Functions : 11

    • Errors and Debugging : 10

    • Functions : 9

    • Practice with Loops and Algorithms : 8

    • Algorithms I : 7

    • Loops : 6

    • Arrays : 5

    • Compound Conditionals : 4

    • Conditional Expressions and Statements : 3

    • Operations on Variables : 2

    • Variables and Types : 1

    • Hello, world! : 0

    Sorting Algorithms

    boolean isSorted(int[] array) {
    return false;
    }
    assert isSorted(new int[] {1, 2, 5});

    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

    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
    Sorting Basics

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

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

    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:

    And maybe a few more along the way!

    isSorted
    isSorted

    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!

    // isSorted

    Bubble Sort
    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.

    // Bubble Sort

    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
    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!

    Solve: Insertion Sort

    Created By: Geoffrey Challen
    / Version: 2020.11.0

    Create a public class named InsertionSorter. It should provide one class method sort. sort accepts an array of Comparables and sorts them in ascending order. You should sort the array in place, meaning that you modify the original array, and return the number of swaps required to sort the array as an int. That's how we'll know that you've correctly implemented insertion sort. If the array is null you should throw an IllegalArgumentException. You can assume that the array does not contain any null values.

    To receive credit implement insertion sort as follows. Have the sorted part start at the left and grow to the right. Each step takes the left-most value from the unsorted part of the array and move it leftward, swapping elements until it is in the correct place. Do not swap equal values. This will make your sort unstable and cause you to fail the test suites.

    More Practice

    Need more practice? Head over to the practice page.