Sorting Algorithms for AP Computer Science A

Sorting algorithms to know to AP CSA, includes best/worst runtime

Bubble Sort

A sorting algorithm that iteratively compares adjacent elements and swaps them if the first is greater than the second, allowing the largest unsorted element to 'bubble up' to its correct position.

Best Case of Bubble Sort

O(n), occurs when the list is already sorted.

Average and Worst Case of Bubble Sort

O(n^2), occurs in cases where the list is in reverse order.

Selection Sort

A sorting algorithm that finds the smallest element from the unsorted portion of the list and swaps it with the first unsorted element.

Time Complexity of Selection Sort

O(n^2) comparisons in all cases, making it inefficient for large datasets.

Space Efficiency of Selection Sort

An in-place algorithm requiring no additional memory, making it suitable for memory-constrained environments.

Insertion Sort

A sorting method that processes elements one at a time, inserting each into its correct position in the sorted part of the list.

Shifting Elements in Insertion Sort

During insertion, larger elements in the sorted portion are shifted to the right to make space for the current element.

Best Case of Insertion Sort

O(n), occurs when the list is already sorted.

Average and Worst Case of Insertion Sort

O(n^2), occurs for random or reverse-ordered data due to nested iterations.

In-Place and Stable

Characteristics of insertion sort that indicate it operates on the input list without extra memory and preserves the relative order of equal elements.

Merge Sort

A divide-and-conquer sorting algorithm that recursively divides the list into two halves and merges them in sorted order.

Time Complexity of Merge Sort

O(nlogn) in all cases (best, average, and worst).

Space Complexity of Merge Sort

Requires O(n) additional space for temporary storage during merging.

Stable Sort

A sorting algorithm that maintains the relative order of equal elements, characteristic of merge sort.

Quick Sort

A sorting algorithm that uses partitioning to rearrange elements based on a pivot, such that elements less than the pivot are on one side and greater on the other.

Average and Best Case of Quick Sort

O(nlogn), occurs on average cases and best-case scenarios.

Worst Case of Quick Sort

O(n^2), occurs if the pivot is consistently the smallest or largest element.

In-Place Sorting

Refers to algorithms that require minimal extra memory, characteristic of quick sort.

Unstable Sort

A sorting algorithm that does not necessarily preserve the relative order of equal elements, like quick sort.

Iterative Insertion in Insertion Sort

The process of inserting each element into its appropriate position in a sorted list.

Pass Through the List in Bubble Sort

Refers to the process where the algorithm iteratively traverses the list to perform comparisons and swaps.

Finding Minimum in Selection Sort

The process of identifying the smallest element from the unsorted portion of the list during each pass.

Swapping in Selection Sort

The action of exchanging the smallest element with the first element of the unsorted portion of the list.

Sorted/Unsorted Division in Selection Sort

The method of expanding the sorted portion of the list one element at a time.

Divide and Conquer in Merge Sort

The strategy of recursively splitting the list into smaller parts until each contains a single element.

Merge Process in Merge Sort

Combining two sorted sublists into one sorted list by comparing and arranging elements.

Characteristics of Insertion Sort

In-place and stable algorithm effective for nearly sorted data.

Comparison in Algorithms

Refers to the process of evaluating pairs of elements to determine their order.

Best Use Cases of Bubble Sort

Best for small or nearly sorted datasets.

Best Use Cases of Selection Sort

Useful when memory space is limited and datasets are small.

Best Use Cases of Merge Sort

Ideal for large datasets requiring stability.

Best Use Cases of Quick Sort

Effective for large datasets where space is a concern.

Gradual Reduction in Bubble Sort

Fewer elements are compared in each pass as sorted elements accumulate at the end.