Rucete ✏ AP Computer Science A In a Nutshell
8. Sorting and Searching
This chapter covers basic sorting and searching algorithms in Java, including selection sort, insertion sort, merge sort, quicksort, sequential search, and binary search. It also discusses analysis of efficiency, best/worst cases, and application contexts.
Selection Sort
• "Search-and-swap" sorting algorithm.
• Find the smallest element and swap it with the first unsorted element.
• Repeat until all elements are sorted.
• After the kth pass, the first k elements are in their final sorted positions.
• Inefficient for large n due to O(n²) comparisons.
Insertion Sort
• Builds a sorted list one element at a time by inserting into the correct position.
• Elements to the right may need shifting to create space.
• Best case: Already sorted array (O(n)).
• Worst case: Reversed array (O(n²)).
• Inefficient for large n but simple and efficient for small arrays.
Common Points: Selection vs. Insertion Sort
• Both require about n-1 passes for n elements.
• Insertion sort generally performs better than selection sort on nearly sorted arrays.
• Neither is efficient for large datasets.
Recursive Sorts: Merge Sort and Quicksort
• Merge Sort:
• Divide array into halves, recursively sort each half, merge sorted halves.
• Requires a temporary array.
• Best, worst, and average case times are O(n log n).
• Not sensitive to initial element ordering.
• Quicksort (Optional for AP subset):
• Choose a pivot, partition elements smaller to the left, larger to the right.
• Recursively quicksort left and right partitions.
• Best and average case: O(n log n).
• Worst case (already sorted or bad pivot choice): O(n²).
• Strategies like random pivot selection or median-of-three pivot reduce worst-case chances.
Sorting Algorithms in Java
• Arrays.sort() uses a tuned quicksort for primitive types and a modified mergesort for objects (stable sort).
• Collections.sort() is used for sorting ArrayLists and uses a mergesort algorithm internally.
• Custom sort orders are defined using the Comparable or Comparator interfaces.
Sequential (Linear) Search
• Searches for a target by checking each element one by one.
• Best case: Target found at the first index (O(1)).
• Worst case: Target found at the last index or not found (O(n)).
• Works on both sorted and unsorted arrays or lists.
• Inefficient for large datasets but simple to implement.
Binary Search
• Requires a sorted array or list.
• Repeatedly halves the search space by comparing the middle element to the target.
• Best case: Target is found at the middle element (O(1)).
• Worst and average case: O(log n) comparisons.
• Common mistakes:
• Not checking for sorted data before applying binary search.
• Incorrect middle calculation causing infinite loops or index errors.
Efficiency Comparisons
• Sequential Search: O(n).
• Binary Search: O(log n) but only on sorted data.
• Insertion Sort and Selection Sort: O(n²).
• Merge Sort and average Quicksort: O(n log n).
Choosing the Right Search or Sort
• Use binary search if the data is already sorted or can be sorted once upfront.
• Use sequential search if the dataset is small or unsorted and searching needs to happen quickly without sorting overhead.
• Use insertion sort for small or nearly sorted datasets; otherwise, prefer mergesort for larger datasets where stability matters.
In a Nutshell
Understanding sorting and searching algorithms is key to writing efficient programs. Simple sorts like selection and insertion are easy to implement but inefficient for large datasets, while merge sort and quicksort offer superior performance for bigger problems. Linear search works universally but slowly, whereas binary search requires sorted data but is highly efficient. Choosing the right technique based on the problem context leads to optimized and scalable Java applications.