Chapter 3 – Simple Sorting (Bubble, Selection, Insertion)

Vocabulary flashcards summarizing key terms and concepts from the lecture on bubble, selection and insertion sorting algorithms.

Simple Sorting

Group of basic algorithms—bubble, selection and insertion—that are easy to implement but run in O(N²) time.

Bubble Sort

Algorithm that repeatedly compares adjacent elements and swaps them so the largest values ‘bubble’ to the end of the array.

Selection Sort

Algorithm that repeatedly selects the smallest (or largest) remaining item and swaps it into the next unsorted position, keeping swap count low.

Insertion Sort

Algorithm that builds a sorted section by removing the next item and inserting it into its correct place within the partially-sorted left side.

Pass (in sorting)

One complete traversal of the data by the inner loop during which comparisons and swaps/copies occur.

Swap

Operation that exchanges the values of two array elements, usually with the help of a temporary variable.

Comparison (Sorting)

Operation that evaluates two key values to decide ordering; core step of every sorting algorithm.

Inner Loop

The nested loop that performs element-level comparisons and operations during each pass of a sorting algorithm.

Outer Loop

The controlling loop that determines how many passes or positions must be processed in a sort.

Invariant

Condition that remains true throughout an algorithm (e.g., ‘items right of out are sorted’ in bubble sort).

Partially Sorted

State in insertion sort where items to the left of the divider are internally ordered but may shift as new items are inserted.

Key Field

Attribute used for ordering records during a sort, such as lastName in a Person object.

Stable Sort

Sort that preserves the original relative order of items with identical keys.

O(N²) Time Complexity

Performance where operations grow proportionally to the square of the data size; typical for simple sorts with nested loops.

In-Place Sort

Sorting method that rearranges elements within the original array, requiring only a constant amount of extra memory.

Shift (Insertion Sort)

Process of moving elements one position right to create space for the item being inserted.

Copy (Sorting)

Duplicating a value from one index to another; used during shifts in insertion sort and counted separately from swaps.

Binary Search

Fast O(log N) search requiring pre-sorted data; motivates the need for sorting arrays.

compareTo()

Java String method that returns a negative, zero or positive integer to indicate lexicographical ordering between two strings.

Lexicographical Comparison

Alphabetical ordering based on character sequence, used when comparing string keys.

Primitive Type

Built-in Java data type (e.g., long) used in simple sort examples for clarity.

Object Sorting

Applying sort algorithms to arrays of objects by comparing their key fields instead of primitive values.

Bubble Up

Informal term describing how the largest items move toward the end of the array during bubble sort passes.

Minimum Pointer (min)

Variable in selection sort that tracks the index of the smallest item found during the current pass.

Quicksort (Preview)

Faster O(N log N) algorithm covered later; often finishes with insertion sort on small or nearly-sorted subarrays.