Sorting Algorithms to Know for AP Computer Science A

Bubble Sort

Bubble Sort

A sorting algorithm that iteratively compares adjacent elements and swaps them if the first is greater than the second.

Best Case Time Complexity of Bubble Sort

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

Average Case Time Complexity of Bubble Sort

O(n^2), occurs in most cases where elements are in random order.

Worst Case Time Complexity of Bubble Sort

O(n^2), happens when the list is sorted in reverse order.

Selection Sort

A sorting algorithm that finds the minimum (or maximum) element from the unsorted portion and swaps it with the first unsorted element.

Time Complexity of Selection Sort

O(n^2) for all cases, which makes it inefficient for large datasets.

Space Efficiency of Selection Sort

An in-place algorithm that requires no additional memory.

Insertion Sort

A sorting algorithm that builds the sorted list by inserting elements into their correct position one at a time.

Best Case Performance of Insertion Sort

O(n) when the input list is already sorted.

Average Case Complexity of Insertion Sort

O(n^2) when elements are in random order.

Merge Sort

A divide and conquer sorting algorithm that recursively divides the list into halves and merges sorted sublists.

Guaranteed Time Complexity of Merge Sort

O(n log n) in all cases (best, average, worst).

Stability of Merge Sort

Maintains the relative order of equal elements, making it a stable sorting algorithm.

Quick Sort

A sorting algorithm that selects a pivot and partitions the list around it, sorting elements recursively.

Average Case Time Complexity of Quick Sort

O(n log n), occurs with a good choice of pivots.

Worst Case Time Complexity of Quick Sort

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

In-Place Sorting in Quick Sort

Requires minimal extra memory, making it more space-efficient compared to merge sort.

Unstable Sorting Algorithm

Quick Sort is an unstable algorithm as it does not preserve the relative order of equal elements.

Gradual Reduction in Bubble Sort

With each pass, the number of elements to compare decreases as the last elements become sorted.

Shifting Elements in Insertion Sort

During insertion, larger elements are shifted one position to the right to accommodate the current element.

Space Complexity of Merge Sort

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

Sorted/Unsorted Division in Selection Sort

Expands the sorted portion of the list by moving the boundary after each minimum element is swapped.