CODEWITHSUNDEEP
javaalgorithmsortinginsertion-sort
venkysmarty
venkysmarty

Reputation: 11431

about insertion sort improvement in Robert Sedgewick

I am reading about algorithms by Robert Sedgewick book.

public static void sort(Comparable[] a)
{   // Sort a[] into increasing order.
    int N = a.length;
    for (int i = 1; i < N; i++)
    { // Insert a[i] among a[i-1], a[i-2], a[i-3]... ..
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--)
            exch(a, j, j-1);
    }
}

Above is insertion sort implementation in java. Here author mentiones as improvment as below.

It is not difficult to speed up insertion sort substantially, by shortening its inner loop to move the larger entries to the right one position rather than doing full exchanges (thus cutting the number of array accesses in half)

I am having difficutly in understanding above improvement. What does author mean by

  1. Move large entries to the right one postion rather than full exchanges and how this will reduce array access to half.

Request to example with simple example for better understanding.

Upvotes: 4

Views: 1167

Answers (1)

Andy Turner
Andy Turner

Reputation: 140328

I think that he is referring to the fact that you don't need to keep on actually swapping elements, because you will end up repeatedly moving the same element.

For instance, you can cache the value of the i-th element initially, and refer just to this in the inner loop:

public static <C extends Comparable<C>> void insertionSort(C[] a) {
  for (int i = 1; i < a.length; i++) {
    C ithElement = a[i];
    int j = i;
    for (j = i; j > 0 && ithElement.compareTo(a[j - 1]) < 0; --j) {
      // This is "moving the larger entry to the right 1 position"
      a[j] = a[j - 1];
    }
    a[j] = ithElement;
  }
}

Demo

Upvotes: 5

Related Questions