📚 Quick Study Guide: Modifying Insertion Sort
- 💡 Understanding Insertion Sort (Ascending): The standard Insertion Sort algorithm builds the final sorted array (or list) one item at a time. It iterates through the input elements and at each iteration, removes one element from the input data and inserts it into the correct position in the already sorted part. For ascending order, it typically compares `arr[j] > key` to shift elements.
- ⚙️ Core Logic for Descending Order: To sort in descending order, the fundamental change is in the comparison logic. Instead of finding a position where `arr[j]` is greater than the `key` (to shift it right and place `key` before it), we need to find a position where `arr[j]` is *less than* the `key`. This means the comparison `arr[j] > key` should be changed to `arr[j] < key`.
- 🔄 Shifting Elements: When `arr[j] < key` (for descending sort), elements `arr[j]` that are smaller than `key` need to be shifted one position to the right (`arr[j+1] = arr[j]`). This creates space for the `key` to be inserted at the correct position, ensuring larger elements come before smaller ones.
- 🔍 The `key` Element: In each iteration, `key` holds the current element being considered from the unsorted part of the array. This `key` is then inserted into its correct place within the already sorted subarray.
- ✅ Outer and Inner Loops: The outer loop iterates from the second element to the end of the array. The inner loop (`while` loop) is responsible for finding the correct position for the `key` and shifting elements to make space.
📝 Practice Quiz
1. Which comparison operator in the inner loop of a standard Insertion Sort (for ascending order) needs to be changed to sort in descending order?
- `>` (greater than) to `<` (less than)
- `<` (less than) to `>` (greater than)
- `==` (equals) to `!=` (not equals)
- `>=` (greater than or equals) to `<=` (less than or equals)
2. Consider the following Java code snippet for an Insertion Sort inner loop:
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
To modify this for descending order, which line needs the primary change?
- `int j = i - 1;`
- `while (j >= 0 && arr[j] > key)`
- `arr[j + 1] = arr[j];`
- `arr[j + 1] = key;`
3. If an array `[5, 2, 8, 1]` is being sorted using modified Insertion Sort for descending order, what would be the state of the array after the first pass (after processing `2`)?
- `[5, 2, 8, 1]`
- `[2, 5, 8, 1]`
- `[5, 8, 2, 1]`
- `[8, 5, 2, 1]`
4. What is the purpose of shifting elements to the right (`arr[j+1] = arr[j]`) in a descending Insertion Sort?
- To move smaller elements to the end of the array.
- To create space for the `key` element at its correct position.
- To swap elements in place without an extra variable.
- To ensure elements are always moved to the left.
5. In a descending Insertion Sort, if `key` is `7` and the sorted subarray is `[10, 8, 5]`, where will `key` be inserted?
- Before `10`
- Between `10` and `8`
- Between `8` and `5`
- After `5`
6. What happens if you forget to include `j >= 0` in the `while` loop condition when modifying Insertion Sort for descending order?
- The algorithm will still work correctly but be less efficient.
- It will result in an `ArrayIndexOutOfBoundsException` if `j` becomes negative.
- The array will be sorted in ascending order instead.
- The inner loop will never execute.
7. Which of the following best describes the `key` variable in an Insertion Sort algorithm?
- It stores the largest element found so far.
- It is a temporary variable holding the element to be inserted into the sorted subarray.
- It represents the index of the current element being processed.
- It is used to count the number of comparisons made.
Click to see Answers
1. A: To sort in descending order, we need to shift elements that are *smaller* than the key. So, `arr[j] > key` becomes `arr[j] < key`.
2. B: The comparison `arr[j] > key` directly dictates the sorting order. Changing it to `arr[j] < key` will switch to descending.
3. A: The first pass of Insertion Sort considers the element at index 1 (`2`). `key = 2`. The sorted part is `[5]`. The inner loop condition for descending is `arr[j] < key`. Is `arr[0]` (`5`) < `key` (`2`)? No. So, no shifting occurs, and `2` is placed at `arr[1]`. The array remains `[5, 2, 8, 1]`.
4. B: Shifting elements to the right creates an empty slot where the `key` element can be inserted, maintaining the sorted order of the subarray.
5. C: For descending order, `7` is smaller than `10` and `8`, but larger than `5`. So, it will be inserted between `8` and `5` to maintain the `[larger, ..., smaller]` sequence.
6. B: If `j` becomes negative (i.e., less than 0) because the loop condition only checks `arr[j] < key` and not `j >= 0`, accessing `arr[j]` will lead to an `ArrayIndexOutOfBoundsException`.
7. B: The `key` variable temporarily holds the element that is currently being sorted and inserted into its correct place within the already sorted portion of the array.