Fiveable
Fiveable

or

Log in

Find what you need to study


Light

Find what you need to study

7.6 Sorting

5 min readdecember 30, 2022

Milo Chang

Milo Chang

Athena_Codes

Athena_Codes

Milo Chang

Milo Chang

Athena_Codes

Athena_Codes

The other major application of ArrayLists is , which is placing elements in an ascending or , but it is mainly used for . There are many algorithms, but we'll only learn and in this unit and 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 is sorted, there is a quick algorithm that sees if the elements are always increasing. Here is its implementation:

/** Returns if the is sorted in */ public static boolean isSorted(<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

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

Here is the implementation preceded by which explains why it's called the :

/** Uses on an * 1. Originally the is unsorted * 2. We select the smallest number and 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 * 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 <Integer> selectionSort(<Integer> array) { for (int i = 0; i < array.size() - 1; i++) { // 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; j < array.size(); j++) {

// 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) { // 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 :

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 algorithm is the . Like , there are sorted and unsorted subarrays.

Here is the implementation and explaining why it is called :

/** Uses on an * 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 <Integer> insertionSort(<Integer> array) { for (int i = 1; i < array.size(); 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 int itemToRight = array.get(j - 1); array.set(j - 1, currentElement); array.set(j, itemToRight); } } } return array; }

Here is a visual version of :

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.

Informal Run-Time Comparisons

To compare the performance of these algorithms, you can count the number of statements they execute during execution. For example, you might count the number of times the loop variables are updated or the number of times elements are compared or swapped. This will give you an idea of how many statements each algorithm executes to complete the process.

Informal run-time comparisons of program code segments can be made using statement execution counts. By comparing the number of statements executed by different algorithms, you can get a sense of their relative efficiency and make informed decisions about which algorithm to use in a given situation.

requires more data accesses and modifications than because it needs to search the entire array to find the minimum element on each iteration. , on the other hand, only needs to access and modify the data in the sorted portion of the array.

As a result, may be faster for small data sets or when the data is partially sorted.

Key Terms to Review (11)

ArrayList

: ArrayList is a dynamic data structure that allows you to store and manipulate collections of objects. Unlike arrays, ArrayLists can grow or shrink dynamically as needed.

Ascending Order

: Ascending order refers to arranging items in increasing numerical or alphabetical value. The smallest value comes first, followed by larger values.

Descending Order

: Descending order refers to arranging items or numbers from highest to lowest value.

Insertion Sort

: Insertion sort is a simple sorting algorithm where each iteration removes one element from an input data set and inserts it into its correct position within a partially sorted list until all elements are inserted.

Merge Sort

: Merge Sort is an efficient, comparison-based sorting algorithm that divides an unsorted list into smaller sublists, sorts those sublists recursively, and then merges them back together to obtain a sorted list.

Pseudocode

: Pseudocode is a simplified programming language that uses plain English to outline the logic of a program. It helps programmers plan and communicate their ideas before writing actual code.

Runtime Comparisons

: Runtime comparisons refer to the analysis and evaluation of the efficiency and speed of different algorithms or programs during execution.

Selection Sort

: Selection Sort is a simple sorting algorithm that repeatedly finds the minimum element from an unsorted portion of the list and swaps it with the first element of that portion until the entire list is sorted.

Sorting

: Sorting refers to arranging a collection of items in a specific order, such as ascending or descending order, based on certain criteria.

Swap

: Swap refers to exchanging the values of two variables or elements in an array. It allows you to rearrange data without losing any information.

Traverse

: Traversing refers to the process of accessing each element in a data structure (such as arrays or linked lists) one by one, usually for performing some operation on them.

7.6 Sorting

5 min readdecember 30, 2022

Milo Chang

Milo Chang

Athena_Codes

Athena_Codes

Milo Chang

Milo Chang

Athena_Codes

Athena_Codes

The other major application of ArrayLists is , which is placing elements in an ascending or , but it is mainly used for . There are many algorithms, but we'll only learn and in this unit and 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 is sorted, there is a quick algorithm that sees if the elements are always increasing. Here is its implementation:

/** Returns if the is sorted in */ public static boolean isSorted(<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

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

Here is the implementation preceded by which explains why it's called the :

/** Uses on an * 1. Originally the is unsorted * 2. We select the smallest number and 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 * 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 <Integer> selectionSort(<Integer> array) { for (int i = 0; i < array.size() - 1; i++) { // 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; j < array.size(); j++) {

// 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) { // 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 :

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 algorithm is the . Like , there are sorted and unsorted subarrays.

Here is the implementation and explaining why it is called :

/** Uses on an * 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 <Integer> insertionSort(<Integer> array) { for (int i = 1; i < array.size(); 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 int itemToRight = array.get(j - 1); array.set(j - 1, currentElement); array.set(j, itemToRight); } } } return array; }

Here is a visual version of :

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.

Informal Run-Time Comparisons

To compare the performance of these algorithms, you can count the number of statements they execute during execution. For example, you might count the number of times the loop variables are updated or the number of times elements are compared or swapped. This will give you an idea of how many statements each algorithm executes to complete the process.

Informal run-time comparisons of program code segments can be made using statement execution counts. By comparing the number of statements executed by different algorithms, you can get a sense of their relative efficiency and make informed decisions about which algorithm to use in a given situation.

requires more data accesses and modifications than because it needs to search the entire array to find the minimum element on each iteration. , on the other hand, only needs to access and modify the data in the sorted portion of the array.

As a result, may be faster for small data sets or when the data is partially sorted.

Key Terms to Review (11)

ArrayList

: ArrayList is a dynamic data structure that allows you to store and manipulate collections of objects. Unlike arrays, ArrayLists can grow or shrink dynamically as needed.

Ascending Order

: Ascending order refers to arranging items in increasing numerical or alphabetical value. The smallest value comes first, followed by larger values.

Descending Order

: Descending order refers to arranging items or numbers from highest to lowest value.

Insertion Sort

: Insertion sort is a simple sorting algorithm where each iteration removes one element from an input data set and inserts it into its correct position within a partially sorted list until all elements are inserted.

Merge Sort

: Merge Sort is an efficient, comparison-based sorting algorithm that divides an unsorted list into smaller sublists, sorts those sublists recursively, and then merges them back together to obtain a sorted list.

Pseudocode

: Pseudocode is a simplified programming language that uses plain English to outline the logic of a program. It helps programmers plan and communicate their ideas before writing actual code.

Runtime Comparisons

: Runtime comparisons refer to the analysis and evaluation of the efficiency and speed of different algorithms or programs during execution.

Selection Sort

: Selection Sort is a simple sorting algorithm that repeatedly finds the minimum element from an unsorted portion of the list and swaps it with the first element of that portion until the entire list is sorted.

Sorting

: Sorting refers to arranging a collection of items in a specific order, such as ascending or descending order, based on certain criteria.

Swap

: Swap refers to exchanging the values of two variables or elements in an array. It allows you to rearrange data without losing any information.

Traverse

: Traversing refers to the process of accessing each element in a data structure (such as arrays or linked lists) one by one, usually for performing some operation on them.


© 2024 Fiveable Inc. All rights reserved.

AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.


© 2024 Fiveable Inc. All rights reserved.

AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.