Glossary
ArrayList
A resizable array implementation in Java that belongs to the Java Collections Framework, allowing dynamic addition and removal of elements.
Example:
Creating an ArrayList of Strings to store a list of student names that can grow or shrink as needed.
Insertion Sort
A sorting algorithm that builds the final sorted array one item at a time by repeatedly taking the next element from the unsorted part and inserting it into its correct position in the already sorted part.
Example:
When sorting [5, 2, 8, 1] with insertion sort, you'd start with [5] sorted, then take 2 and insert it before 5 to get [2, 5], then take 8 and place it after 5 to get [2, 5, 8], and finally take 1 and insert it at the beginning to get [1, 2, 5, 8].
Merge Sort
A divide-and-conquer sorting algorithm that recursively divides a list into halves until each sublist has only one element, then repeatedly merges the sublists to produce new sorted sublists until there is only one sorted list.
Example:
To sort [3, 1, 4, 2] using merge sort, you'd split it into [3, 1] and [4, 2], then further into [3], [1], [4], [2], sort these single-element lists, and then merge them back up.
Run-Time Comparisons
The process of evaluating and comparing the efficiency of different algorithms or code segments based on how their execution time scales with input size.
Example:
Analyzing whether run-time comparisons show that sorting 1000 items with selection sort is faster or slower than with insertion sort.
Selection Sort
A sorting algorithm that repeatedly finds the minimum element from the unsorted part of the list and swaps it with the element at the beginning of the unsorted part.
Example:
To sort [5, 2, 8, 1] using selection sort, you'd first find 1 (smallest) and swap it with 5, making it [1, 2, 8, 5], then continue with the remaining unsorted part.
Sorted Subarray
A contiguous portion of an array or list that contains elements already arranged in the desired sorted order.
Example:
In selection sort, after the first pass, the first element forms the sorted subarray. In insertion sort, the elements processed so far form the sorted subarray.
Sorting
The process of arranging elements in a list or array into a specific order, typically ascending or descending.
Example:
If you have a list of student scores [85, 92, 78, 95], sorting them in ascending order would result in [78, 85, 92, 95].
Statement Execution Counts
A method for informally comparing algorithm efficiency by counting the number of basic operations or lines of code executed during a program's run.
Example:
Using statement execution counts to see that a loop running 'n' times with one operation inside performs 'n' operations.
Unsorted Subarray
The remaining contiguous portion of an array or list whose elements have not yet been placed into their final sorted positions.
Example:
In selection sort, as elements are moved to the beginning, the rest of the list remains the unsorted subarray from which the next smallest element is chosen.
isSorted (algorithm)
An algorithm or method used to check if the elements within an ArrayList are already arranged in a specific order, typically ascending.
Example:
Calling isSorted on an ArrayList like [10, 20, 30] would return true, but on [10, 30, 20] it would return false.