javaalgorithmsortinginsertion-sort

Why does insertion sort work only if we use while as an inner loop and doesn’t work for ” for loop”?

I was trying to attempt a insertion algorithm question. However, I had the following question.

I wanted to nderstand why most solutions online use a nested while loop instead of a nested for loop? I thought it might have to do something with time complexity, however, both have a O(n^2) complexity.

Below I have attached the two different solutions


public class InsertionSort { 
// MY method
    /*Function to sort array using insertion sort*/
    // void sort(int arr[]) 
    // { 
    //     int n = arr.length; 
    //     for (int i = 1; i < n; ++i) { 
    //         if(arr[i] < arr[i-1]){
    //             for(int j = 0; j < i; j++){
    //                 if(arr[i] < arr[j]){
    //                     int temp = arr[j];
    //                     arr[j] = arr[i];
    //                     arr[i] = temp;
    //                 }
    //             }
    //         }
    //     } 
    // } 

// Online Solution
  
    void sort(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; 
        } 
    }
Solution

  • Usually, when developing algorithms, you choose a loop based on this:

    In Java, and other languages, you can implement the same thing using both loops. It doesn't matter if the number of iterations is known. However, it makes sense, it's more readable/logical:

    In pseudocode, which is a way to describe an algorithm independently of implementation-details, it's often done just like that (or similar):

    for i = 0 to n do
    ...

    while condition do
    ...

    When you look at sort, you can see two loops: the outer for-loop and the inner while-loop.