What is the number of ordered elements in the array when sorted by insertion?

Insertion sort is the sorting algorithm in which the elements of the input sequence are viewed one by one, and each new incoming element is placed in a suitable place among the previously ordered elements [1]. Computational complexity - O (n ^ 2).

How many early ordered elements ?

  • reformulate the question. At what step or when? After the end of the sorting is all. How much at the previous step - well, depends on the step number - pavel
  • How many have already been viewed - so many previously ordered. At the i-th step of the algorithm there will be i previously ordered elements. - AnT

1 answer 1

Insertion sort is the sorting algorithm in which the elements of the input sequence are viewed one by one, and each new k incoming element is placed in a suitable place among the previously ordered k-1 elements [1].

So clearer? :)

See - when you insert the k element, the previous ones are already in order. How many of these previous ones? Right, k-1 ...