instead of using exch to switch values store the item being

instead of using exch() to switch values, store the item being moved into position in a variable, move the items up the array as needed, and put the item being moved back into the array at the correct position.

public class InsertionSort {

   // Compare two values.

   private static boolean less(Comparable a, Comparable b) {

       return a.compareTo(b) < 0;

   }

   // Exchange two array entries.

   private static void exch(Comparable[] a, int idx1, int idx2) {

       Comparable t = a[idx1];

       a[idx1] = a[idx2];

       a[idx2] = t;

   }

   // Check that we\'re really sorted.

   private static boolean isSorted(Comparable[] a) {

       for (int i = 1; i < a.length; i++)

           if (less(a[i], a[i - 1]))

               return false;

       return true;

   }

   public static void Sort(Comparable[] a) {

       int n = a.length;

       // Starting with the element at index 1...

       for (int i = 1; i < n; i++) {

           // ...move to the left until we find one less

           // than the current element.

           for (int j = i; j > 0; j--) {

               if (less(a[j], a[j - 1]))

                   exch(a, j, j - 1);

               else

                   break;

           }

       }

   }

   public static void main(String[] args) {

      

       // Read an array of ints from stdin.

       int[] aInt = StdIn.readAllInts();

       // Convert to an array of Integer so we can use Comparable.

       int n = aInt.length;

       Integer[] a = new Integer[n];

       for (int i = 0; i < n; i++)

           a[i] = aInt[i];

       // Time the sort operation.

       Stopwatch sw = new Stopwatch();

       Sort(a);

       double elapsed = sw.elapsedTime();

       // Display the results.

       if (!isSorted(a))

           StdOut.println(\"Sort failure!\");

       StdOut.printf(\"Elapsed time: %6.3f\", elapsed);

   }

}

Solution

Please let me know in case of any issue.

public class InsertionSort {

// Compare two values.
private static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}


// Check that we\'re really sorted.
private static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++)
if (less(a[i], a[i - 1]))
return false;
return true;
}

public static void Sort(Comparable[] a) {
int n = a.length;
// Starting with the element at index 1...
for (int i = 1; i < n; i++) {
// ...move to the left until we find one less
// than the current element.
for (int j = i; j > 0; j--) {
if (less(a[j], a[j - 1])){
Comparable t = a[j];
a[j] = a[j-1];
a[j-1] = t;
}
else
break;
}
}
}

public static void main(String[] args) {
  
// Read an array of ints from stdin.
int[] aInt = StdIn.readAllInts();

// Convert to an array of Integer so we can use Comparable.
int n = aInt.length;
Integer[] a = new Integer[n];
for (int i = 0; i < n; i++)
a[i] = aInt[i];

// Time the sort operation.
Stopwatch sw = new Stopwatch();
Sort(a);
double elapsed = sw.elapsedTime();

// Display the results.
if (!isSorted(a))
StdOut.println(\"Sort failure!\");
StdOut.printf(\"Elapsed time: %6.3f\", elapsed);
}
}