0
$\begingroup$

Here is insertion sort:

for i = 1 to length(A)
    x = A[i]
    j = i - 1
    while j >= 0 and A[j] > x
        A[j+1] = A[j]
        j = j-1
    end while
    A[j+1] = x
end for

My lecture notes say that the total number of basic computation steps is about

$$T = 1 + ( 5 + t_1 \times 3 ) + \dots + ( 5 + t_{n-1} \times 3 )\,,$$

where $t_i$ represents how many times the inner loop needs to run (anything between $0$ and $i$). $5$ for the basic operations in the outer loop, and $1$ for testing whether to enter the outer loop.

I understand the "1" and the "5" but not the "3". Because I think $t_i$ is not always anything between $0$ and $i$? Like say a number needs to move from position $5$ to position $1$, it repeats the inner loop meaning there will be more steps? The steps in the inner loop can possibly repeat for $n-1$ times?

So what is the basic computation steps?

$\endgroup$
  • 1
    $\begingroup$ Welcome to CS.SE! Please edit the question to provide a self-contained definition for all notation. What does "x 3" represent? Could that potentially have been "x_3"? If so, what does that variable represent? Have you tried reading any other book's analysis of insertion sort? The running time of insertion sort is explained in many places; you might want to start by reading another reference and understanding it, then come back to your particular lecture notes. $\endgroup$ – D.W. Oct 12 '16 at 19:45
  • $\begingroup$ x 3 means *3. and I have tried other analysis and I just don't understand. Basically the question is: when trying to move a number across 4 positions (Shifting), the while loop must be implement 4 times? Because it needs to compare the value with the key for 4 times until the previous key is smaller than the value? $\endgroup$ – lalala Oct 12 '16 at 19:59
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Oct 12 '16 at 22:08
  • 1
    $\begingroup$ "So what is the basic computation steps?" -- you need to be more precise. Are you meaning to ask "what is the number of ... executed in the worst case"? If not, what is it? $\endgroup$ – Raphael Oct 12 '16 at 22:12
1
$\begingroup$

You asked why the "3" is there in that equation. Here's the explanation.

$t_i$ counts the number of iterations of the inner loop, for a particular value of $i$. Each iteration executes 3 instructions (3 steps). Therefore, the total number steps of computations consumed by the inner loop, for a particular value of $i$, is $3 \times t_i$.

$\endgroup$
0
$\begingroup$

I believe to make it easy to understand it is necessary to set it as a task. So here it is:

TASK: Insertion Sort INPUT: $a_{1}, a_{2},...,a_{n} \in {\rm I\!R}\ or\ {\rm I\!N} $

OUTPUT: $b_{1}, b_{2},...,b_{n}$ the $a_{i}s $ in increasing order.

Insertion sort algorithm solves above task as follows. On the first iteration we have the sequence $a_{1},...,a_{n}.$ On the $j^{th}$ iteration we have the sequence $c_{1},...,c_{j},a_{j+1},...,a_{n}$. Note that $c_{1},...,c_{j}$ are the numbers $a_{1},...,a_{j}$ in increasing order. Trivially, on the first iteration $c_{1}=a_{1}$ and on the last we have sorted list of numbers.

So to construct $c_{1},...,c_{j},c_{j+1},a_{j+2},...,a_{n}$ from the previous iteration $c_{1},...,c_{j},a_{j+1},...,a_{n}$ we do the following;

compare $a_{j+1}$ with $c_{j},c_{j-1},...$ in this order and stop when its place is found. That is when $c_{i} < a_{j+1} <= c_{i+1}$. We then insert that $a_{j+1}$ between. When $a_{j+1} < c_{j}$ then $a_{j+1}$ becomes the first element on the next iteration, and when $a_{j+1} > c_{j}$ then $c_{j+1} = a_{j+1}$ and there are no more comparisons required.

So to find the new place for $a_{j+1}$ and to complete the $j^{th}$ iteration it takes at most j comparisons. So the total number of iterations is at most $ \sum^{n-1}_{j=1}j = n(n-1)/2 = O(n^2).$ Thus we end up with a conclusion that the complexity of the Insertion sort algorithm is $T(n) = n(n-1)/2$.

Hopefully this will help you understand the pseudo code above a bit better. I know from my experience as a Computer Scientist that these can be unclear at the start.

$\endgroup$
  • $\begingroup$ And yes as @D.W. mentioned I would also recommend learning at least basics of LaTex or Tex, it is helpful in many scenarios. $\endgroup$ – marcincuber Oct 12 '16 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.