4 min read•Last Updated on June 18, 2024
Avanish Gupta
Milo Chang
Avanish Gupta
Milo Chang
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.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
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
4. Select the smallest of the unsorted numbers (the second smallest overall) and
swap it with the second element
//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:
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
Here is a visual version of insertion sort:
To compare the performance of these sorting 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 sorting 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 sorting algorithms, you can get a sense of their relative efficiency and make informed decisions about which algorithm to use in a given situation.
Selection sort requires more data accesses and modifications than insertion sort because it needs to search the entire array to find the minimum element on each iteration. Insertion sort, on the other hand, only needs to access and modify the data in the sorted portion of the array.
As a result, insertion sort may be faster for small data sets or when the data is partially sorted.
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.
Term 1 of 11
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.
Term 1 of 11
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.
Term 1 of 11
Sorting refers to arranging a collection of items in a specific order, such as ascending or descending order, based on certain criteria.
Algorithm: An algorithm is a step-by-step procedure used to solve problems or perform operations, such as sorting.
Comparison Operator: A comparison operator is used to compare two values and determine their relationship (e.g., greater than, less than).
Stable Sort: A stable sort algorithm maintains the relative order of equal elements during sorting.
Descending order refers to arranging items or numbers from highest to lowest value.
Ascending Order: Arranging items or numbers from lowest to highest value.
Sorting Algorithm: A step-by-step procedure used to arrange elements in a specific order.
Bubble Sort: A sorting algorithm that repeatedly compares adjacent elements and swaps them if they are in the wrong 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 is the opposite of ascending order; it arranges items from largest to smallest value.
Comparator Interface: The Comparator interface allows custom sorting of objects based on specific criteria.
Bubble Sort: Bubble sort is a simple sorting algorithm that repeatedly compares adjacent elements and swaps them if they are in the wrong order.
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.
Insertion Sort: A sorting algorithm where elements are gradually inserted into their correct positions within a partially sorted array.
Bubble Sort: A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
Quick Sort: A divide-and-conquer sorting algorithm that selects a pivot element and partitions the array around it. It recursively sorts subarrays before and after the pivot.
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.
Selection Sort: A sorting algorithm that repeatedly selects the smallest element from the unsorted part and moves it to the sorted part.
Merge Sort: A divide-and-conquer algorithm that divides an array into two halves, sorts them separately, and then merges them back together.
Quick Sort: A divide-and-conquer algorithm that picks an element as a pivot, partitions the array around this pivot, and recursively sorts subarrays before and after the pivot.
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.
Quick Sort: A divide-and-conquer sorting algorithm that selects a pivot element and partitions the array around it. It recursively sorts subarrays before and after the pivot.
Heap Sort: A comparison-based sorting algorithm that uses binary heaps to build a partially ordered tree structure which is then used for sorting.
Radix Sort: A non-comparative integer sorting algorithm that distributes data elements into buckets based on digits or significant places.
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.
List Interface: A Java interface that defines common methods for working with lists.
add(): A method used to insert elements into an ArrayList.
remove(): A method used to delete elements from an ArrayList.
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.
Algorithm: A step-by-step procedure or formula for solving a problem. It is like following a set of instructions to complete a task.
Flowchart: A visual representation of an algorithm using different shapes and arrows to show the flow of control. It is like drawing out the steps of your plan on paper.
Syntax: The rules and structure that define how statements are written in a programming language. It is like grammar rules that determine how sentences should be constructed in English.
Swap refers to exchanging the values of two variables or elements in an array. It allows you to rearrange data without losing any information.
Sort: The process of arranging elements in ascending or descending order based on certain criteria, such as numerical value or alphabetical order.
Array: A data structure that stores multiple values under one variable name, allowing easy access and manipulation of those values.
Variable: A named storage location in computer memory that holds data which can change during program execution.
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.
Iteration/Looping: Repeating a set of instructions multiple times until certain conditions are met.
Searching: The process of finding a specific element within a data structure.
Sorting: Rearranging the elements in a specific order within a data structure.