Solve Insertion Sort For Array {23, 26, 20, 18, 22, 24, 25} A Step-by-Step Guide

by ADMIN 81 views
Iklan Headers

Introduction to Insertion Sort

In the realm of sorting algorithms, insertion sort stands out as a simple yet efficient method, particularly well-suited for sorting smaller datasets or nearly sorted arrays. It operates much like how you might sort a hand of playing cards. Imagine you have a set of cards in your hand, and you want to arrange them in ascending order. You would pick a card, compare it with the cards already in your sorted sequence, and insert it into its correct position. This intuitive process mirrors the essence of insertion sort.

The core principle behind insertion sort is to build a sorted subarray one element at a time. It iterates through the array, considering each element as the 'key' to be inserted. For each key, it compares it with the elements in the sorted subarray (which initially consists of just the first element) and shifts the elements greater than the key to the right, creating a space for the key to be inserted in its correct sorted position. This process continues until all elements have been considered, resulting in a fully sorted array. Insertion sort is an in-place sorting algorithm, meaning it doesn't require additional memory space beyond the original array. This makes it memory-efficient, especially when dealing with limited resources. Furthermore, it's a stable sorting algorithm, which means it preserves the relative order of equal elements. If two elements have the same value, their original order in the array will be maintained after sorting.

Insertion sort's simplicity makes it easy to understand and implement. However, its performance characteristics make it more suitable for certain scenarios than others. In the best-case scenario, when the input array is already sorted, insertion sort has a linear time complexity of O(n), making it exceptionally efficient. This is because it only needs to iterate through the array once, comparing each element with its predecessor. In the worst-case scenario, when the input array is sorted in reverse order, insertion sort has a quadratic time complexity of O(n^2). This is because, for each element, it may need to compare and shift all the preceding elements. The average-case time complexity is also O(n^2). Therefore, insertion sort is not the most efficient choice for large, unsorted arrays. Algorithms like merge sort or quicksort, which have an average time complexity of O(n log n), are generally preferred for larger datasets. However, insertion sort's efficiency on small datasets and its ability to handle nearly sorted arrays effectively make it a valuable tool in a programmer's arsenal. It's also often used as a subroutine in more advanced sorting algorithms, such as shellsort, to improve their performance on smaller subarrays. In summary, insertion sort is a simple, in-place, and stable sorting algorithm that is efficient for small datasets and nearly sorted arrays. While it may not be the best choice for large, unsorted datasets, its ease of implementation and adaptability make it a fundamental sorting algorithm to understand.

Step-by-Step Solution for int arr[] = {23, 26, 20, 18, 22, 24, 25}

To illustrate how insertion sort works, let's apply it to the given array: int arr[] = {23, 26, 20, 18, 22, 24, 25}. We will walk through each step of the sorting process, showing how the array is transformed at each iteration. This step-by-step solution will provide a clear understanding of the algorithm's mechanics and how it achieves a sorted output.

Initial Array: [23, 26, 20, 18, 22, 24, 25]

Step 1: The first element, 23, is considered already sorted as it's the only element in the sorted subarray. We move to the second element, 26.

  • Sorted Subarray: [23]
  • Unsorted Portion: [26, 20, 18, 22, 24, 25]

Step 2: Compare 26 with 23. Since 26 is greater than 23, it is already in the correct position. The sorted subarray now consists of [23, 26].

  • Sorted Subarray: [23, 26]
  • Unsorted Portion: [20, 18, 22, 24, 25]

Step 3: Now, consider 20. Compare 20 with 26 and then with 23. Since 20 is less than both, shift 26 and 23 one position to the right and insert 20 at the beginning of the sorted subarray.

  • Shifting: [_, 23, 26]
  • Insertion: [20, 23, 26]
  • Sorted Subarray: [20, 23, 26]
  • Unsorted Portion: [18, 22, 24, 25]

Step 4: Consider 18. Compare 18 with 26, 23, and 20. Since 18 is the smallest so far, shift all elements in the sorted subarray one position to the right and insert 18 at the beginning.

  • Shifting: [_, 20, 23, 26]
  • Insertion: [18, 20, 23, 26]
  • Sorted Subarray: [18, 20, 23, 26]
  • Unsorted Portion: [22, 24, 25]

Step 5: Consider 22. Compare 22 with 26, 23, and 20. Insert 22 between 20 and 23 after shifting 23 and 26 one position to the right.

  • Shifting: [18, 20, _, 23, 26]
  • Insertion: [18, 20, 22, 23, 26]
  • Sorted Subarray: [18, 20, 22, 23, 26]
  • Unsorted Portion: [24, 25]

Step 6: Consider 24. Compare 24 with 26 and 23. Insert 24 between 23 and 26 after shifting 26 one position to the right.

  • Shifting: [18, 20, 22, 23, _, 26]
  • Insertion: [18, 20, 22, 23, 24, 26]
  • Sorted Subarray: [18, 20, 22, 23, 24, 26]
  • Unsorted Portion: [25]

Step 7: Finally, consider 25. Compare 25 with 26 and 24. Insert 25 between 24 and 26.

  • Shifting: [18, 20, 22, 23, 24, _, 26]
  • Insertion: [18, 20, 22, 23, 24, 25, 26]
  • Sorted Subarray: [18, 20, 22, 23, 24, 25, 26]
  • Unsorted Portion: []

Final Sorted Array: [18, 20, 22, 23, 24, 25, 26]

This step-by-step walkthrough clearly demonstrates how insertion sort iteratively builds a sorted subarray by inserting each element into its correct position. By understanding this process, you can appreciate the algorithm's logic and its suitability for certain sorting tasks.

Code Implementation (Java)

To solidify your understanding of insertion sort, let's examine a Java implementation. This code snippet will provide a practical perspective on how the algorithm is translated into a working program. We'll break down the code step by step, explaining each part's role in the sorting process.

public class InsertionSort {

    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;

            /* Move elements of arr[0..i-1], that are
               greater than key, to one position ahead
               of their current position */
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    // Driver method
    public static void main(String args[]) {
        int arr[] = {23, 26, 20, 18, 22, 24, 25};

        insertionSort(arr);

        System.out.println("Sorted array");
        for (int i = 0; i < arr.length; ++i)
            System.out.print(arr[i] + " ");

        System.out.println();
    }
}

Explanation:

  1. insertionSort(int[] arr) Method: This method takes an integer array arr as input and sorts it using the insertion sort algorithm.
  2. int n = arr.length;: Gets the length of the array and stores it in the variable n.
  3. for (int i = 1; i < n; ++i): This loop iterates through the array starting from the second element (index 1). The first element is considered as the initial sorted subarray.
  4. int key = arr[i];: The current element arr[i] is selected and stored in the key variable. This is the element that will be inserted into the correct position in the sorted subarray.
  5. int j = i - 1;: j is initialized to the index of the element just before the key element. This j will be used to traverse the sorted subarray.
  6. while (j >= 0 && arr[j] > key): This while loop is the heart of the insertion sort. It iterates as long as j is within the bounds of the array (i.e., j is not negative) and the element at arr[j] is greater than the key. This loop finds the correct position for the key in the sorted subarray.
  7. arr[j + 1] = arr[j];: Inside the while loop, this statement shifts the element arr[j] one position to the right to make space for the key.
  8. j = j - 1;: Decrements j to compare the key with the next element in the sorted subarray.
  9. arr[j + 1] = key;: After the while loop completes, the correct position for the key has been found. This statement inserts the key into its sorted position.
  10. main(String args[]) Method: This is the driver method where the program execution begins.
  11. int arr[] = {23, 26, 20, 18, 22, 24, 25};: Initializes the array to be sorted.
  12. insertionSort(arr);: Calls the insertionSort method to sort the array.
  13. **`System.out.println(