Sorting Algorithms Overview

Simple sorting involves three algorithms:
- Bubble sort
- Selection sort
- Insertion sort
All three algorithms execute two main steps repeatedly until the data is sorted:
- Compare two items
- Swap two items or copy one item

Begin comparing items at array positions 0 and 1
- If the item at position 0 is larger, swap with item at position 1; otherwise, do nothing
Move to positions 1 and 2, repeating the comparison and swap process
Continue until reaching the right end of the array

The algorithm is termed 'bubble sort' because the largest items "bubble up" to the top end of the array as the sorting progresses.
After one complete pass through the data:
- N-1 comparisons made
- 0 to N-1 swaps depending on initial arrangement
- The last item in the array is guaranteed to be sorted and will not move again

After sorting the largest item, another pass is initiated from the left end
- This time, comparisons only need to be made up to position N-2, as N-1 is sorted
The process repeats until the list is completely sorted

For 10 items:
- Comparisons per pass are: 9, 8, 7, 6, 5, 4, 3, 2, 1
- Total comparisons: 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45
General pattern: N-1 comparisons on the first pass, N-2 on the second, down to 1
In the worst case, bubble sort requires up to N-1 passes

The formula for total comparisons as a series:
- (N-1) + (N-2) + (N-3) + … + 2 + 1 = \frac{N*(N-1)}{2}
Approximate total comparisons: \frac{N^{2}}{2} (ignoring constants)
Note: There are fewer swaps than comparisons, as swaps occur only if necessary

In a random dataset, swaps occur about half the time, leading to:
- Approximately \frac{N^{2}}{4} swaps on average
Worst case (inversely sorted) requires a swap with every comparison
Both swaps and comparisons run proportional to N², concluding:
- Bubble sort has a time complexity of O(N²)

When encountering nested loops (e.g., in bubble sort), suspect O(N²) time complexity:
- Outer loop runs N times
- Inner loop runs up to N times each outer cycle
- Total operations approximately N * N or N²

Selection sort definition:
- Algorithm that makes a full pass through all items, selecting the smallest item
- The smallest item is then swapped with the item at position 0 (the left end of the array)

Selection sort comparisons: Works on N*(N-1)/2 comparisons
- For N = 10: 45 comparisons
Time complexity: O(N²), similar to bubble sort
Selection sort can be faster than bubble sort due to fewer swaps

Definition of insertion sort:
- Considered the best among elementary sorts
- Executes in O(N²) time, but more efficient (twice as fast as bubble sort) under typical conditions
- Simplified implementation
- Frequently used as a final stage in advanced algorithms like quicksort

Partial sorting concept:
- Items to the left of a marker are partially sorted among themselves
Elements may not be in final position and need adjustment when inserting new items
Unlike bubble and selection sorts, maintains a partially sorted state

As new items are inserted, previously sorted items are shifted to make room
Marked item temporarily removed to manage the shift:
- A temporary variable holds removed data
Shift items to the right, clearing space for the marked item
This process iterates until all unsorted items are inserted into their proper places

Pseudocode for insertion sort:
java public static void insertionSort(int[] a, int n) { int i; for(i = 1; i < n; i++) { int value = a[i]; int hole = i; while(hole > 0 && a[hole - 1] > value) { a[hole] = a[hole - 1]; hole = hole - 1; } a[hole] = value; } }
Key points of pseudocode:
- Outer loop starts marking leftmost unsorted data
- Inner loop shifts sorted elements to the right to accommodate the marked item
- Each execution of the while loop shifts one sorted element to the right

Big O notation reflects worst-case scenario as O(N²)
Best case (data already sorted or nearly sorted) could be O(N)
- In this case, while loop never executes, leading to efficiency gains