CODEWITHSUNDEEP
javaalgorithminsertion-sort
trailblazer
trailblazer

Reputation: 1451

Difference between following implementations of insertion sort

Implementation1: (uses one for loop, but does thee shifting in a while loop)

public class Insertionsort{
public static void main(String[] args) {
    int a[] = {10,9,8,7,6,5,4,3,2,1};
    for (int i = 1; i < a.length; i++){
        int j = i;
        int B = a[i];
        while ((j > 0) && (a[j-1] > B)){
            a[j] = a[j-1];
            j--;
        }
        a[j] = B;
    }
    for(int i = 0; i <a.length; i++)
          System.out.print(a[i]+"  ");
    }
}

Implementation 2: uses 3 for loops

public class InsertionSort {
    public static void main(String[] args) {
       int a[] = {10,9,8,7,6,5,4,3,2,1};

       for(int i = 0; i<a.length; i++){
           for(int j=i+1; j<a.length; j++){
               if(a[i]>a[j]){
                   int temp = a[j];
                   for (int k=j; k>i; k--){
                       a[k] = a[k-1];
                   }
                   a[i] = temp;
               } 
            }
            System.out.print(a[i]+" ");
        }
    }
}

inner most loop has definitely less number of iterations, but I am not sure if both algorithms are exactly same or the first one is better. Please help in deciding.

Upvotes: 0

Views: 108

Answers (1)

kullalok
kullalok

Reputation: 823

In the end, both of these implementations sort the array and are both insertion sort (although the second implementation shares some similarities with bubble sort).

The first implementation is better than the second one. The first one runs O(N^2) time whereas the second one is O(N^3). The smarter choice would be to use the first implementation

Upvotes: 1

Related Questions