Java Arrays and Sorting Algorithms Explained

Exam Tip: When traversing a 2D array, you will almost always need a "nested loop"—an outer loop to iterate through the rows and an inner loop to iterate through the columns of each row.

---

Fundamental Sorting Algorithms

Sorting is the process of arranging elements in a specific order (usually ascending). Different algorithms have different strengths depending on the size of the data and the initial order of the elements.

1. Bubble Sort

Bubble Sort is one of the simplest sorting methods. It works by repeatedly stepping through the list, comparing adjacent elements ($j$ and $j + 1$), and swapping them if they are in the wrong order.

• Mechanism: In each pass, the largest unsorted element "bubbles up" to its correct position at the end of the array.
• Swapping Logic: To swap two elements without losing data, a temp variable is used: $$\begin{aligned} \text{int temp} = \text{arr}[j]; \\ \text{arr}[j] = \text{arr}[j+1]; \\ \text{arr}[j+1] = \text{temp}; \end{aligned}$$
• Optimization: A standard Bubble Sort can be optimized by using a boolean flag. If a complete pass occurs without any swaps, the array is already sorted, and the algorithm can stop early.
• Complexity: The best-case time complexity (with optimization) is $O(n)$, but the average and worst cases are $O(n^2)$.

2. Insertion Sort

Insertion Sort is analogous to the way many people sort playing cards in their hands. It divides the array into a "sorted" portion and an "unsorted" portion.

• Mechanism: The algorithm picks a key element from the unsorted portion and compares it against the elements in the sorted portion.
• Shifting: Instead of swapping adjacent elements repeatedly, Insertion Sort uses shifting (arr[j + 1] = arr[j]) to move elements one by one to make room for the key.
• Efficiency: It is extremely efficient for small datasets or arrays that are already "nearly sorted," achieving a best-case time complexity of $O(n)$.

3. Selection Sort

Selection Sort takes a different approach by focusing on finding the smallest element rather than comparing neighbors.

• Mechanism: The algorithm scans the unsorted portion of the array to find the minimum element (minIndex). Once found, it performs exactly one swap per pass to place that minimum element at the start of the unsorted section.
• Complexity: Unlike Insertion Sort, Selection Sort always performs the same number of comparisons, regardless of the initial order. The number of comparisons is always: $$\frac{n(n-1)}{2}$$ This results in a consistent $O(n^2)$ time complexity.
• Advantage: Because it performs only one swap per pass, it minimizes memory write operations, which can be beneficial in certain hardware environments.

4. Merge Sort

For large datasets, the $O(n^2)$ algorithms mentioned above become too slow. Merge Sort is a much more powerful alternative that utilizes a Divide-and-Conquer strategy.

• The Strategy:
  1. Divide: The algorithm recursively splits the array into two halves until each sub-array contains only a single element.
  2. Conquer/Merge: The algorithm then compares and combines these smaller sorted sub-arrays back together to form larger sorted arrays until the entire structure is reconstructed.
• Complexity: Merge Sort is highly consistent. It provides a time complexity of $O(n \log n)$ across best, average, and worst-case scenarios. This makes it the preferred choice for high-performance sorting of large datasets.

Summary Table of Time Complexities