CODEWITHSUNDEEP
algorithminsertion-sort
Shikhar
Shikhar

Reputation: 77

Insertion sort in best case

With reference to Algorithm - Fourth Edition by Robert and Kevin, I am having difficulty in understanding the best case complexity for Insertion sort as per below code:

    public class Insertion
{
    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);
        }
    }
// See page 245 for less(), exch(), isSorted(), and main().
}

It says in the book that in best case (sorted array), the number of exchanges is 0 and number of compares is N-1. While I understood exchanges to be 0, I am having a hard time how can number of compares be N-1 in best case?

Upvotes: 0

Views: 2204

Answers (3)

user3437460
user3437460

Reputation: 17454

how can number of compares be N-1 in best case?

The best case happens when you have an already sorted array. The number of comparison is n-1 because the comparison is made from the 2nd element onwards till the last element.

This can also be observed from your given code:

for (int i = 1; i < N; i++)    //int i=1 (start comparing from 2nd element)

Upvotes: 0

Claudio Borges
Claudio Borges

Reputation: 132

The source code for the specific implementation is:

    public class Insertion
{
    public static void sort(Comparable[] a)
    { // Sort a[] into increasing order.
        int N = a.length;
        bool exc = false;
        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);
                    exc = true;
                }
             if (!exc)
                 break;
        }
    }
// See page 245 for less(), exch(), isSorted(), and main().
}

Upvotes: -1

ruakh
ruakh

Reputation: 183321

If the array is already sorted, then in the specific implementation of insertion-sort that you provide, each element will only be compared to its immediate predecessor. Since it's not less than that predecessor, the inner for-loop then aborts immediately, without requiring any further comparisons or exchanges.

Note that other implementations of insertion-sort do not necessarily have that property.

Upvotes: 2

Related Questions