The AP Computer Science A 5-hour live stream review is here!Β πŸ’»

Join us on May 5, 2021 for the 🌢️ AP Computer Science A Cram Finale for a last minute review to get all your questions answered!

πŸ“š

All Subjects

Β >Β 

πŸ’»Β 

AP Comp Sci A

Β >Β 

πŸ’Ύ

Unit 7

7.6 Sorting

4 min readβ€’november 16, 2020

Peter Cao

Caroline Koffke


7.6: Sorting

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:

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<Integer> 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 which explains why it's called the selection sort:
/** Uses selection sort on an ArrayList * 1. Originally the ArrayList is unsorted * 2. We select the smallest number and swap it with the first element * 3. Now the sorted subarray is the first item and the rest of the array is unsorted * 4. Select the smallest of the unsorted numbers (the second smallest overall) and * swap it with the second element * 5. Now the first two elements are sorted and the rest are unsorted * 6. Repeat until the rest of the elements are sorted */ public static ArrayList<Integer> selectionSort(ArrayList<Integer> array) { for (int i = 0; i < array.size() - 1; i++) { // traverse to the second to last item, the last item is automatically the largest int smallestIndex = i; int smallestElement = array.get(i); for (int j = i + 1; i < array.size(); j++) { //traverse through the rest of the array, looking for the smallest remaining item (less than smallestElement) if (array.get(j) < smallestElement) { smallestIndex = j; smallestElement = array.get(j); } } if (smallestIndex > i) { // swap the elements of i and j if the element of i isn't already the smallest int originalItem = array.get(i); array.set(i, smallestElement); array.set(smallestIndex, originalItem); } } return array; }
Here is a visual graphic showing selection sort:
https://firebasestorage.googleapis.com/v0/b/fiveable-92889.appspot.com/o/images%2F-IdIi2s3bETb8.png?alt=media&token=669e8c8d-1404-43d5-83ad-2ba3528f1fc0

Courtesy of w3resource.

Insertion Sort

The other sorting algorithm is the insertion sort. Like selection sort, there are sorted and unsorted subarrays. Here is the implementation and pseudocode explaining why it is called insertion sort:
/** Uses insertion sort on an ArrayList * 1. Assume the first element is already sorted * 2. Select the second element * 3. Insert it before the first element or keep it in place to make the first 2 elements sorted * 4. Select the third element and insert it so that the first 3 elements are sorted * 5. Repeat until all elements are sorted. */ public static ArrayList<Integer> insertionSort(ArrayList<Integer> array) { for (int i = 1; i < array.length(); i++) { int currentElement = array.get(i); int currentIndex = i; for (int j = i; j > 0 ; j--) { if (currentElement < array.get(j - 1)) { // shifting the item left until properly placed by swapping consecutive items itemToRight = array.get(j - 1); array.set(j - 1, currentElement); array.set(j, itemToRight); } } } return array; }
Here is a visual version of insertion sort:
https://firebasestorage.googleapis.com/v0/b/fiveable-92889.appspot.com/o/images%2F-G6cxMlupo9eo.png?alt=media&token=e12ac8cc-de40-4caa-bcb7-259a584913e2

Courtesy of Wikipedia.

Was this guide helpful?

πŸ’ͺ🏽 Are you ready for the Comp Sci exam?
Take this quiz for a progress check on what you’ve learned this year and get a personalized study plan to grab that 5!
START QUIZ
FREE AP comp sci a Survival Pack + Cram Chart PDF
Sign up now for instant access to 2 amazing downloads to help you get a 5
Browse Study Guides By Unit
πŸ™
Exam Reviews
πŸ–±
Unit 10: Recursion
βž•
Unit 1: Primitive Types
πŸ“±
Unit 2: Using Objects
πŸ–₯
Unit 3: Boolean Expressions and if Statements
πŸ•Ή
Unit 4: Iteration
βš™οΈ
Unit 5: Writing Classes
⌚️
Unit 6: Array
πŸ’»
Unit 8: 2D Array
πŸ–²
Unit 9: Inheritance
Join us on Discord
Thousands of students are studying with us for the AP Computer Science A exam.
join now
Play this on HyperTyper
Practice your typing skills while reading Sorting
Start Game