Why are all solutions for insertion sort using a nested while loop instead of a nested for?

user_13204939 0
Viewed 1343

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; 
        } 
    }
insertion-sort sorting algorithm java
1 Answers

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

  • If the number of iterations is known, use a for-loop.
  • If the number of iterations is not known, use a while-loop.

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:

  • ... for a known starting value to a known limit do ...
  • ... while a condition is true do ...

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.

  • The outer loop is a for-loop because i and n are known. Value n is known because it's given by the size of the array, which is a constant in this algorithm.
  • The inner loop is a while-loop because it's not known when the condition will fail, as it depends on an array-access. You don't know the values; if you would, then you could sort the array by hardcoding some swaps.
user_123232480
Related