zuai-logo

Sorting

Ethan Taylor

Ethan Taylor

6 min read

Listen to this study note

Study Guide Overview

This study guide covers ArrayList sorting algorithms. It introduces selection sort and insertion sort, including pseudocode, implementation examples, and visualizations. It also briefly discusses determining if an ArrayList is sorted and touches on informal run-time comparisons between the algorithms.

The other major application of ArrayLists is sorting, which is placing elements in an ascending or descending order, but it is mainly used for ascending order. There are many sorting algorithms, but we'll only learn selection sort and insertion sort in this unit and merge sort in Unit 10. There are many others that you can view in this video:

🎥 Video on 50+ Sorts, Visualized - Bar Graph Seize Warning

Courtesy of Musicombo.

Determining Whether An ArrayList is Sorted

To determine whether an ArrayList is sorted, there is a quick algorithm that sees if the elements are always increasing. Here is its implementation:

/** Returns if the ArrayList is sorted in ascending order */ public static boolean isSorted(ArrayList array) { for (int i = 0; i < array.size() - 1) { if (array.get(i + 1) < array.get(i)) { //checks if two array elements are in the return false; // wrong order } } return true; }

Selection Sort

Selection sort is the simpler of the two sorting algorithms. The selection sort divides the ArrayList into two "subarrays:" the first being a sorted subarray and the second being the unsorted subarray.

Here is the implementation preceded by pseudocode whic...