Insertion Sort: Explained and Applied

[evinda]

Hi! (Smile)

$\text{ Could you explain me how I could sort the following list, applying the Insertion sort ? }$

View attachment 3445

 

[alyafey22]

Given A[1...N];
for i = 2 to N 
//put elements in its right position
  Insert(A[i])
//A[1..i] is sorted now
end for 

Insert (A[i])
{
//compare A[i] to A[k] ;  1<=k<=i-1 
//We A[k] to right if  A[i] > A[k] else A[k+1]=A[i]
for k=i-1 to 1 
  if (A[k] > A[i])
    A[j] =A[j+1];
  else
    A[i] = A[j+1] ; break;
  end if
end for
}

Applying the algorithm above

100-(10)-2-6-230-77-33
10-100-(2)-6-230-77-33
2-10-100-(6)-230-77-33
2-6-10-100-(230)-77-33
2-6-10-100-230-(77)-33
2-6-10-77-100-230-(33)
2-6-10-33-77-100-230
//The parenthesis represents the element to be inserted next.

 

[evinda]

Given A[1...N];
for i = 2 to N 
//put elements in its right position
  Insert(A[i])
//A[1..i] is sorted now
end for 

Insert (A[i])
{
//compare A[i] to A[k] ;  1<=k<=i-1 
//We A[k] to right if  A[i] > A[k] else A[k+1]=A[i]
for k=i-1 to 1 
  if (A[k] > A[i])
    A[j] =A[j+1];
  else
    A[i] = A[j+1] ; break;
  end if
end for
}

This algorithm uses an array, instead of a list. How could we apply the Insertion Sort to a list? (Thinking)

 

[Nono713]

This algorithm uses an array, instead of a list. How could we apply the Insertion Sort to a list? (Thinking)

A list is an abstract data structure which holds an ordered sequence of elements. An array is one concrete way to implement a list, by storing the elements contiguously in memory and simply interpreting A as "the ith element". Basically, an array is a kind of list. Does that answer your question?

 

[alyafey22]

This algorithm uses an array, instead of a list. How could we apply the Insertion Sort to a list? (Thinking)

If it is a singly linked list with unique elements we use that head.next to move from one element to another. Then to insert an element "ele" to its right position we create a temporary variable temp to traverse the list using temp.next from the beginning and compare it to the value of ele in hand if temp.next is greater than ele we place it their by putting temp.data = value. Then we have to shift all elements one position to right until we reach the original position of ele. The insertion stops if temp.next.data = ele;

 

[alyafey22]

A visualization might help

Insert-sort with Romanian folk dance - YouTube

 

[evinda]

A visualization might help

Insert-sort with Romanian folk dance - YouTube

I understand the Insertion Sort.. But, could you explain me how I can apply it to lists? (Thinking)

 

[Nono713]

I understand the Insertion Sort.. But, could you explain me how I can apply it to lists? (Thinking)

What is your definition of a list? What do you think a list is? How would you access the elements of a list in pseudocode? (that's actually the only operation needed in insertion sort since you don't need to add or remove elements, only compare and swap)

 

[I like Serena]

I understand the Insertion Sort.. But, could you explain me how I can apply it to lists? (Thinking)

Suppose A is a pointer to the first element of a list.

Then where the sort algorithm refers to A[k] you could use for instance the algorithm:

procedure Nth(A, n)
  P = A
  for i = 2 to n
    P = P.next
  return P

(Thinking)

 

[alyafey22]

I understand the Insertion Sort.. But, could you explain me how I can apply it to lists? (Thinking)

What is unclear in my explanation ?

If it is a singly linked list with unique elements we use that head.next to move from one element to another. Then to insert an element "ele" to its right position we create a temporary variable temp to traverse the list using temp.next from the beginning and compare it to the value of ele in hand if temp.next is greater than ele we place it their by putting temp.data = value. Then we have to shift all elements one position to right until we reach the original position of ele. The insertion stops if temp.next.data = ele;

 

[evinda]

Suppose A is a pointer to the first element of a list.

Then where the sort algorithm refers to A[k] you could use for instance the algorithm:

procedure Nth(A, n)
  P = A
  for i = 2 to n
    P = P.next
  return P

(Thinking)

At the following algorithm:

1.Insertion Sort(A[1...n]){
2.  int key,i,j;
3.  for (j=2; j<n+1; j++){
4.       key=A[j];
5.      i=j-1;
6.       while (i>0 && A[i]>key){
7.                A[i+1]=A[i];
8.                i=i-1;
9.       }
10.      A[i+1]=key;
11. }
12.  return A;
13.}

I changed the lines 7,8 like that:

 Nth(A,i-1).next=Nth(A,i+1) , Nth(A,i+1).next=Nth(A,i)

Is it right? (Thinking)

 

[evinda]

What is unclear in my explanation ?

How could we shift all elements one position to the right? (Worried)

Is that what I have written in post #11 right? (Thinking)

 

[I like Serena]

Is that what I have written in post #11 right? (Thinking)

It looks okay'ish, but I find it very difficult to interpret, so I'm not sure. (Sweating)

How could we shift all elements one position to the right? (Worried)

That's a better question. (Nod)
Let's see if we can come up with a sub algorithm for this.

Suppose P points to the element before the first one that we want to shift.
And suppose Q points to the key element that comes after the last element that we want to shift.

$$
\underset{{}^\uparrow_P}{\boxed{2}} \to \boxed{10} \to \boxed{100}
\to \underset{{}^\uparrow_Q}{\boxed{key=6} }
\to \boxed{230} \to \boxed{77} \to \boxed{33}
$$

What should be do with P and Q to achieve what you asked? (Wondering)

 

[evinda]

It looks okay'ish, but I find it very difficult to interpret, so I'm not sure. (Sweating)
That's a better question. (Nod)
Let's see if we can come up with a sub algorithm for this.

Suppose P points to the element before the first one that we want to shift.
And suppose Q points to the key element that comes after the last element that we want to shift.

$$
\underset{{}^\uparrow_P}{\boxed{2}} \to \boxed{10} \to \boxed{100}
\to \underset{{}^\uparrow_Q}{\boxed{key=6} }
\to \boxed{230} \to \boxed{77} \to \boxed{33}
$$

What should be do with P and Q to achieve what you asked? (Wondering)

It should be like that:

Q.next=P.next;
P.next=Q;

Right? (Thinking)

 

[I like Serena]

It should be like that:

Q.next=P.next;
P.next=Q;

Right? (Thinking)

Almost.
What will the next element of $100$ be? (Wondering)

 

[evinda]

Almost.
What will the next element of $100$ be? (Wondering)

So should it be like that?

P.next.next.next=Q.next;
Q.next=P.next;
P.next=Q;

(Thinking)

 

[I like Serena]

So should it be like that?

P.next.next.next=Q.next;
Q.next=P.next;
P.next=Q;

(Thinking)

Something like that (except you have one "next" too many). (Smile)

But it will only work for this specific sequence then.
I gave this sequence only as an example... (Wasntme)

 

[evinda]

Something like that (except you have one "next" too many). (Smile)

But it will only work for this specific sequence then.
I gave this sequence only as an example... (Wasntme)

I haven't understood how we could do it for a general case... (Worried)

Could you explain it to me? (Thinking)

 

[I like Serena]

I haven't understood how we could do it for a general case... (Worried)

Could you explain it to me? (Thinking)

Well, apparently we also need a pointer to the last element that we want to shift.
Let's call it R.
We might find it by scanning through the list with a while-loop, but let's not go there yet.

$$
\underset{{}^\uparrow_P}{\boxed{2}} \to \boxed{10} \to \underset{{}^\uparrow_R}{\boxed{100}}
\to \underset{{}^\uparrow_Q}{\boxed{key=6} }
\to \boxed{230} \to \boxed{77} \to \boxed{33}
$$

Then the sub algorithm is:

Procedure: Shift sub sequence after key(P,R,Q)

Input: P   pointer to list element before the sub sequence
       R   pointer to last element of the sub sequence
       Q   pointer to key element after the sub sequence

  R.next = Q.next
  Q.next = P.next
  P.next = Q

(Thinking)

 

[evinda]

Well, apparently we also need a pointer to the last element that we want to shift.
Let's call it R.
We might find it by scanning through the list with a while-loop, but let's not go there yet.

To find where R should point, couldn't we use the function

Procedure Nth(A,n)

that you have written in the post #9, since R points to the previous element of the key? Or am I wrong? (Thinking)

$$
\underset{{}^\uparrow_P}{\boxed{2}} \to \boxed{10} \to \underset{{}^\uparrow_R}{\boxed{100}}
\to \underset{{}^\uparrow_Q}{\boxed{key=6} }
\to \boxed{230} \to \boxed{77} \to \boxed{33}
$$

Then the sub algorithm is:

Procedure: Shift sub sequence after key(P,R,Q)

Input: P   pointer to list element before the sub sequence
       R   pointer to last element of the sub sequence
       Q   pointer to key element after the sub sequence

  R.next = Q.next
  Q.next = P.next
  P.next = Q

(Thinking)

I understand! (Nod)

 

[I like Serena]

To find where R should point, couldn't we use the function

Procedure Nth(A,n)

that you have written in the post #9, since R points to the previous element of the key? Or am I wrong? (Thinking)

Yep!
We could! (Smile)Suppose we rewrite your algorithm a little, making a step to make it more abstract:

1.Insertion Sort(A[1..n]){
2.  int key,i,j;
3.  for (j=2; j<n+1; j++){
4.       key=A[j];
5.       Find i < j such that A[i] <= key or else set i to 0
6.       Shift sub sequence from i+1 to j-1 to after key j
7.       A[i+1]=key;
8. }
9.  return A;
10.}

How could we adapt it further to the use of lists? (Wondering)

 

[evinda]

Suppose we rewrite your algorithm a little, making a step to make it more abstract:

1.Insertion Sort(A[1..n]){
2.  int key,i,j;
3.  for (j=2; j<n+1; j++){
4.       key=A[j];
5.       Find i < j such that A[i] <= key or else set i to 0
6.       Shift sub sequence from i+1 to j-1 to after key j
7.       A[i+1]=key;
8. }
9.  return A;
10.}

How could we adapt it further to the use of lists? (Wondering)

So, is it like that? (Thinking)

1.Insertion Sort (NODE *A){
2.   int key, i, j;
3.   for(j=2; j<n+1; j++){
4.        key=Nth(A,j).data;
5.        i=j-1;
6.        while(i>0 && Nth(A,i).data>key){
7.                Nth(A,j-1).next=Nth(A,j);
8.                Nth(A,j).next=Nth(A,i+1);
9.                Nth(A,i+1).next=Nth(A,j)
10.               i=i-1;
11.      }
12.      Nth(A, i+1).data=key;
13.  }
14.  return A;
15.}

 

[I like Serena]

So, is it like that? (Thinking)

1.Insertion Sort (NODE *A){
2.   int key, i, j;
3.   for(j=2; j<n+1; j++){
4.        key=Nth(A,j).data;
5.        i=j-1;
6.        while(i>0 && Nth(A,i).data>key){
7.                Nth(A,j-1).next=Nth(A,j);
8.                Nth(A,j).next=Nth(A,i+1);
9.                Nth(A,i+1).next=Nth(A,j)
10.               i=i-1;
11.      }
12.      Nth(A, i+1).data=key;
13.  }
14.  return A;
15.}

I'm afraid that after:
[m]7. Nth(A,j-1).next=Nth(A,j);[/m]
the list is broken and you cannot get to the original Nth(A,j).next any more in line 8. (Worried)

Additionally, where is $n$ coming from? (Wondering)

 

[evinda]

I'm afraid that after:
[m]7. Nth(A,j-1).next=Nth(A,j);[/m]
the list is broken and you cannot get to the original Nth(A,j).next any more in line 8. (Worried)

Additionally, where is $n$ coming from? (Wondering)

Could we maybe replace the for with the following while? (Thinking)

1.Insertion Sort (NODE *A){
2.   int key, i, j;
3.   while (A.next != NULL){
4.        key=Nth(A,j).data;
5.        i=j-1;
6.        while(i>0 && Nth(A,i).data>key){
7.                Nth(A,j-1).next=Nth(A,j);
8.                Nth(A,j).next=Nth(A,i+1);
9.                Nth(A,i+1).next=Nth(A,j)
10.               i=i-1;
11.      }
12.      Nth(A, i+1).data=key;
13.      A.next=A.next.next;
14.  }
15.  return A;
16.}

What could I change after the $7^{th}$ line? (Worried)

 

[I like Serena]

Manipulating the list halfway destroys normal access to it. (Worried)
You can resolve this by tracking the relevant pointers separately.
For instance:

7.                P = Nth(A, i+1)
8.                Q = Nth(A, j-1)
9.                R = Nth(A, j)
10.               P.next = ...

Btw, should you be referring to j and j-1 here? (Wondering)

 

[evinda]

Manipulating the list halfway destroys normal access to it. (Worried)
You can resolve this by tracking the relevant pointers separately.
For instance:

7.                P = Nth(A, i+1)
8.                Q = Nth(A, j-1)
9.                R = Nth(A, j)
10.               P.next = ...

Btw, should you be referring to j and j-1 here? (Wondering)

So, should it be like that? (Thinking)

    1.Insertion Sort (NODE *A){
    2.   int key, i, j=2;
    3.   while (A.next != NULL){
    4.        key=Nth(A,j).data;
    5.        i=j-1;
    6.        while(i>0 && Nth(A,i).data>key){
    7.                P=Nth(A, i+1);
    8.                Q=Nth(A, j-1);
    9.                R=Nth(A, j);
    10.               Q.next=R.next;
    11.               R.next=P.next;
    12.               P.next=R;
    13.               i=i-1;
    14.       }       
    15.       P.data=key;
    16.       A.next=A.next.next;
    17.       j++;
    18.  }
    19.  return A;
    20.}

 

[I like Serena]

So, should it be like that? (Thinking)

    7.                P=Nth(A, i+1);
    8.                Q=Nth(A, j-1);
    9.                R=Nth(A, j);
    10.               Q.next=R.next;
    11.               R.next=P.next;
    12.               P.next=R;

That would work better, but you're swapping the wrong values.
You're supposed to achieve [m]A[i+1]=A[/m]. (Worried)

Anyway, it would be better to leave the elements where they are, and just reassign the values.
You can do that with: [m]Nth(A,i+1).data = Nth(A,i).data[/m] instead of what you have now. (Wasntme)

 

[evinda]

That would work better, but you're swapping the wrong values.
You're supposed to achieve [m]A[i+1]=A[/m]. (Worried)

Anyway, it would be better to leave the elements where they are, and just reassign the values.
You can do that with: [m]Nth(A,i+1).data = Nth(A,i).data[/m] instead of what you have now. (Wasntme)

The prof told us that we should not just reassign the values. (Shake)

Could you explain me what I could change, in order to achieve $A[i+1]=A$? (Thinking)

 

[I like Serena]

The prof told us that we should not just reassign the values. (Shake)

Could you explain me what I could change, in order to achieve $A[i+1]=A$? (Thinking)

Since you won't to lose track of any of the nodes, you'll have to swap those 2 around (as in the movie ZaidAlyafey posted (Wink)).

You can do that with:

P = Nth(A, i-1)
Q = Nth(A, i)
R = Nth(A, i+1)
P.next = R
Q.next = R.next
R.next = Q

But what would be much better, is if you use the inner while-loop only to find the place where the key should be inserted.
And, after the while-loop, move the node with the key to that location. (Mmm)

 

[evinda]

Since you won't to lose track of any of the nodes, you'll have to swap those 2 around (as in the movie ZaidAlyafey posted (Wink)).

You can do that with:

P = Nth(A, i-1)
Q = Nth(A, i)
R = Nth(A, i+1)
P.next = R
Q.next = R.next
R.next = Q

But what would be much better, is if you use the inner while-loop only to find the place where the key should be inserted.
And, after the while-loop, move the node with the key to that location. (Mmm)

So, do I have to do it like that? (Thinking)

    Insertion Sort (NODE *A){
       int key, i, j=2;
       while (A.next != NULL){
            key=Nth(A,j).data;
            i=j-1;
            while(i>0 && Nth(A,i).data>key){
                 P = Nth(A, i-1);
                 Q = Nth(A, i);
                 R = Nth(A, i+1);
                 i=i-1;
             }
             P.next = R;
             Q.next = R.next;
             R.next = Q;      
             P.data=key;
             A.next=A.next.next;
             j++;
       }
       return A;
    }

 

[I like Serena]

So, do I have to do it like that? (Thinking)

    Insertion Sort (NODE *A){
       int key, i, j=2;
       while (A.next != NULL){
            key=Nth(A,j).data;
            i=j-1;
            while(i>0 && Nth(A,i).data>key){
                 P = Nth(A, i-1);
                 Q = Nth(A, i);
                 R = Nth(A, i+1);
                 i=i-1;
             }
             P.next = R;
             Q.next = R.next;
             R.next = Q;      
             P.data=key;
             A.next=A.next.next;
             j++;
       }
       return A;
    }

Something like that... (Sweating)

What happens if you apply this algorithm to the list in your OP? (Wondering)

 

[evinda]

Something like that... (Sweating)

What happens if you apply this algorithm to the list in your OP? (Wondering)

At the first iteration, in the inner while loop isn't it P=Nth(A, 0); ? (Thinking)
Which is its value? (Thinking)

 

[I like Serena]

At the first iteration, in the inner while loop isn't it P=Nth(A, 0); ? (Thinking)
Which is its value? (Thinking)

Currently that is not properly defined.
But we can define it ourselves such that it will return NULL if it does not exist. (Wasntme)

 

[evinda]

Anyway, it would be better to leave the elements where they are, and just reassign the values.
You can do that with: [m]Nth(A,i+1).data = Nth(A,i).data[/m] instead of what you have now. (Wasntme)

So, would I just have to replace the lines 7-12 with [m]Nth(A,i+1).data = Nth(A,i).data[/m] ? (Thinking)

1.Insertion Sort (NODE *A){
2.   int key, i, j;
3.   for(j=2; j<n+1; j++){
4.        key=Nth(A,j).data;
5.        i=j-1;
6.        while(i>0 && Nth(A,i).data>key){
7.                Nth(A,i+1).data = Nth(A,i).data
8.  }
9.  return A;
10.}

 

[evinda]

Or do I have to add at the code something else? (Thinking)