Hi all,

 

Here’s the answers of the bonus questions from your friend:

 

Java implementation for Insertion Sort:

 

import java.util.*;

public class insertion {
  public static void main( String[] args ) {
    Scanner scanner = new Scanner(System.in);
   
    System.out.println("Enter the num of integers you want to sort: ");
    int n = scanner.nextInt();
   
    int[] list = new int[n];
   
    System.out.println("Enter the integers 1 by 1: ");
    for(int i=0;i<n;i++)
      list[i] = scanner.nextInt();
   
    for(int j=1;j<n;j++) {
      int temp =list[j];        // store the jth number into temp;
      for(int k=j-1;k>=0;k--){
        if(temp<list[k]) {      // if the jth number is less than (j-1,j-2,......so on) 
          list[k+1]=list[k];    // shift the (j-1,j-2,......so on) number to the next place;
          if(k==0)              // if there's no one to compare to;
            list[0] = temp;     // that means the jth number is the smallest, just put it to the first place;
        }
        else {
          list[k+1]=temp;       // if the jth number is greater than list[k], just put it inot (k+1)th place
          break;                // and end the comparison
        }
      }
    }
   
    for(int i=0;i<n;i++)
    System.out.print(list[i]+" ");
   
  }
}

 

Why Bubble Sort and Insertion Sort are stable?

 

Bubble Sort
Assuming that we have 5 numbers:   1, 10, 3_a, 5, 3_b

Now by sorting the numbers in first pass, we get: 1, 3_a, 5, 3_b ,10
Second Pass: 1, 3_a, 3_b, 5 ,10
What I am trying to explain is, 3_a, 3_b are equal, so bubble sort will not swap their position. It will look at the value; thus it will not affect the position.

Insertion Sort
For insertion sort, the values will only shift to the left by one space until a value is smaller or equal to itself. So we can say that,

One pass: 1, 3_a, 5, 3_b, 10
Two pass: 1, 3_a, 3_b, 5 ,10 (Because 3_a, 3_b are equal, 3_b  stop shifting to the left and the sort ends here...)