Insertion Sort: Explained and Applied

In summary: 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.
  • #1
evinda
Gold Member
MHB
3,836
0
Hi! (Smile)

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

View attachment 3445
 

Attachments

  • list.png
    list.png
    1 KB · Views: 119
Technology news on Phys.org
  • #2
Code:
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

Code:
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.
 
  • #3
ZaidAlyafey said:
Code:
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)
 
  • #4
evinda said:
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?
 
  • #5
evinda said:
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;
 
  • #7
  • #8
evinda said:
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)
 
  • #9
evinda said:
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:
Code:
procedure Nth(A, n)
  P = A
  for i = 2 to n
    P = P.next
  return P
(Thinking)
 
  • #10
evinda said:
I understand the Insertion Sort.. But, could you explain me how I can apply it to lists? (Thinking)

What is unclear in my explanation ?

ZaidAlyafey said:
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;
 
  • #11
I like Serena said:
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:
Code:
procedure Nth(A, n)
  P = A
  for i = 2 to n
    P = P.next
  return P
(Thinking)

At the following algorithm:

Code:
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:

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

Is it right? (Thinking)
 
  • #12
ZaidAlyafey said:
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)
 
  • #13
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)

evinda said:
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)
 
  • #14
I like Serena said:
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:

Code:
Q.next=P.next;
P.next=Q;

Right? (Thinking)
 
  • #15
evinda said:
It should be like that:

Code:
Q.next=P.next;
P.next=Q;

Right? (Thinking)

Almost.
What will the next element of $100$ be? (Wondering)
 
  • #16
I like Serena said:
Almost.
What will the next element of $100$ be? (Wondering)

So should it be like that?

Code:
P.next.next.next=Q.next;
Q.next=P.next;
P.next=Q;

(Thinking)
 
  • #17
evinda said:
So should it be like that?

Code:
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)
 
  • #18
I like Serena said:
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)
 
  • #19
evinda said:
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:
Code:
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)
 
  • #20
I like Serena said:
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
Code:
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)

I like Serena said:
$$
\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:
Code:
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)
 
  • #21
evinda said:
To find where R should point, couldn't we use the function
Code:
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:
Code:
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)
 
  • #22
I like Serena said:
Suppose we rewrite your algorithm a little, making a step to make it more abstract:
Code:
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)

Code:
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.}
 
  • #23
evinda said:
So, is it like that? (Thinking)

Code:
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)
 
  • #24
I like Serena said:
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)

Code:
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)
 
  • #25
Manipulating the list halfway destroys normal access to it. (Worried)
You can resolve this by tracking the relevant pointers separately.
For instance:
Code:
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)
 
  • #26
I like Serena said:
Manipulating the list halfway destroys normal access to it. (Worried)
You can resolve this by tracking the relevant pointers separately.
For instance:
Code:
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)

Code:
    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.}
 
  • #27
evinda said:
So, should it be like that? (Thinking)

Code:
    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)
 
  • #28
I like Serena said:
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)
 
  • #29
evinda said:
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:
Code:
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)
 
  • #30
I like Serena said:
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:
Code:
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)

Code:
    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;
    }
 
  • #31
evinda said:
So, do I have to do it like that? (Thinking)

Code:
    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)
 
  • #32
I like Serena said:
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)
 
  • #33
evinda said:
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)
 
  • #34
I like Serena said:
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)
Code:
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.}
 
  • #35
Or do I have to add at the code something else? (Thinking)
 

Similar threads

Replies
6
Views
4K
Replies
1
Views
1K
Replies
11
Views
3K
Replies
10
Views
4K
Replies
6
Views
2K
Back
Top