CODEWITHSUNDEEP
algorithmsorting
sb15
sb15

Reputation: 313

Insertion sort comparison?

How to count number of comparisons in insertion sort in less than O(n^2) ?

Upvotes: 3

Views: 1482

Answers (3)

kajacx
kajacx

Reputation: 12939

If I remember correctly, this is how insertion sort works:

A = unsorted input array
B := []; //sorted output array
while(A is not empty) {
    remove first element from A and add it to B, preserving B's sorting
}

If the insertion to B is implemented by linear search from the left until you find a greater element, then the number of comparisons is the number of pairs (i,j) such that i < j and A[i] >= A[j] (I'm considering the stable variant).

In other words, for each element x, count the number of elements before x that have less or equal value. That can be done by scanning A from the left, adding it's element to some balanced binary search tree, that also remembers the number of elements under each node. In such tree, you can find number of elements lesser or equal to a certain value in O(log n). Total time: O(n log n).

Upvotes: 0

David Eisenstat
David Eisenstat

Reputation: 65458

When we're inserting an element, we alternate comparisons and swaps until either (1) the element compares not less than the element to its right (2) we hit the beginning of the array. In case (1), there is one comparison not paired with a swap. In case (2), every comparison is paired with a swap. The upward adjustment for number of comparisons can be computed by counting the number of successive minima from left to right (or however your insertion sort works), in time O(n).

num_comparisons = num_swaps
min_so_far = array[0]
for i in range(1, len(array)):
    if array[i] < min_so_far:
         min_so_far = array[i]
    else:
         num_comparisons += 1

Upvotes: 2

lrleon
lrleon

Reputation: 2648

As commented, to do it in less than O(n^2) is hard, maybe impossible if you must pay the price for sorting. If you already know the number of comparisons done at each external iteration then it would be possible in O(n), but the price for sorting was payed sometime before.

Here is a way for counting the comparisons inside the method (in pseudo C++):

void insertion_sort(int p[], const size_t n, size_t & count)
{
  for (long i = 1, j; i < n; ++i)
    {
      auto tmp = p[i];
      for (j = i - 1; j >= 0 and p[j] > tmp; --j) // insert a gap where put tmp
        p[j + 1] = p[j];

      count += i - j; // i - j is the number of comparisons done in this iteration
      p[j + 1] = tmp;
    }
}

n is the number of elements and count the comparisons counter which must receive a variable set to zero.

Upvotes: 0

Related Questions