MHB Insertion Sort: Explained and Applied

[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)

 

[I like Serena]

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

Weird.
I thought I had already answered in this thread.

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.}

Yes, but you still need lines 8-10:

8.                i=i-1;
9.       }
10.      A[i+1]=key;

(Wasntme)

 

[evinda]

Weird.
I thought I had already answered in this thread.

Yes, but you still need lines 8-10:

8.                i=i-1;
9.       }
10.      A[i+1]=key;

(Wasntme)

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,i+1).data = Nth(A,i).data
8.                i=i-1;
9.       }
10.      A[i+1]=key;
11. return A;

 

[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,i+1).data = Nth(A,i).data
8.                i=i-1;
9.       }
10.      A[i+1]=key;
11. return A;

Well... we can't do [m]A[i+1]=key[/m] with a linked list... (Worried)

Btw, can you tell what the order of this algorithm is now? (Wondering)

 

[evinda]

Well... we can't do [m]A[i+1]=key[/m] with a linked list... (Worried)

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,i+1).data = Nth(A,i).data
8.                i=i-1;
9.       }
10.      Nth(A,i+1).data=key;
11. return A;

Btw, can you tell what the order of this algorithm is now? (Wondering)

Is it $O(n^3)$ ? (Thinking)

 

[I like Serena]

So, is it like that? (Thinking)

Is it $O(n^3)$ ? (Thinking)

Yes! (Nod)

 

[evinda]

Yes! (Nod)

And could we also write an algorithm with complexity $O(n^2)$ ? (Thinking)

 

[I like Serena]

And could we also write an algorithm with complexity $O(n^2)$ ? (Thinking)

Yes. (Smile)

 

[evinda]

Yes. (Smile)

Could you give me a hint, how we could do this? (Thinking)

 

[I like Serena]

Could you give me a hint, how we could do this? (Thinking)

We would need to make the algorithm a little bit more abstract. (Nerd)

Something like:

1.Insertion Sort(A[1..n])
2.  j = 2
3.  for each key starting with A[2]
4.       Find element at i < j such that A[i] <= key or else set i to 0
5.       Shift sub sequence from i+1 to j-1 to after key at j
6.       j = j + 1
7.  return A;

The inner loop that was $O(n^2)$ can be replaced by an $O(1)$ operation (line 5). (Mmm)

 

[evinda]

We would need to make the algorithm a little bit more abstract. (Nerd)

Something like:

1.Insertion Sort(A[1..n])
2.  j = 2
3.  for each key starting with A[2]
4.       Find element at i < j such that A[i] <= key or else set i to 0
5.       Shift sub sequence from i+1 to j-1 to after key at j
6.       A[i+1]=key;
7.       j = j + 1
8.  return A;

The inner loop that was $O(n^2)$ can be replaced by an $O(1)$ operation (line 5). (Mmm)

Could you explain me further how we could shift a sub sequence with time complexity $O(1)$ ? (Thinking)

 

[I like Serena]

Could you explain me further how we could shift a sub sequence with time complexity $O(1)$ ? (Thinking)

Suppose we have n=1000 elements, and we have i=5, and j=800.
Furthermore, suppose we have a pointer P to element i, a pointer Q to j-1, and a pointer R to j. (Sweating)

Then we can rehook the elements in the list by:
[m]Q->next = R->next;
R->next = P->next;
P->next = R;[/m]

Regardless of n, this is always 3 operations, so O(1). (Whew)

 

[evinda]

Suppose we have n=1000 elements, and we have i=5, and j=800.
Furthermore, suppose we have a pointer P to element i, a pointer Q to j-1, and a pointer R to j. (Sweating)

Then we can rehook the elements in the list by:
[m]Q->next = R->next;
R->next = P->next;
P->next = R;[/m]

Regardless of n, this is always 3 operations, so O(1). (Whew)

So, you mean that it is like that?

InsertionSort(A[1...n])
j=2;
for (j=2; j<n; j++){
     key=A[j];
     for (i=0; i<j; i++){
          if (A[i]<key){
             Q->next=R->next;
             R->next=P->next;
             P->next=R;
          }
          else i=0;
          P->next->data=key;
          j=j+1;
     }
     return A;
}

Or have I understood it wrong? (Worried)
If it's right, don't we have to find the positions to which Q,P and R point? (Thinking)
Also, at the else-statement, why do we set i=0? (Thinking)

 

[I like Serena]

So, you mean that it is like that?

InsertionSort(A[1...n])
j=2;
for (j=2; j<n; j++){
     key=A[j];
     for (i=0; i<j; i++){
          if (A[i]<key){
             Q->next=R->next;
             R->next=P->next;
             P->next=R;
          }
          else i=0;
          P->next->data=key;
          j=j+1;
     }
     return A;
}

Or have I understood it wrong? (Worried)
If it's right, don't we have to find the positions to which Q,P and R point? (Thinking)
Also, at the else-statement, why do we set i=0? (Thinking)

Actually, we won't need i, j, or n any more.
It's more like this:

InsertionSort(NODE* A)
  NODE *P, *Q, *R, *S;
  int key;

  if (A == NULL)
    return A;
  Q = A;
  R = Q->next;

  // For each key starting at j = 2
  for (Q = A, R = Q->next; R != NULL; Q = R, R = S) {
    key = R->data;
    S = R->next;

    // Find element at i < j such that A[i] <= key or else set i to 0
    for (P = A; (P != R) && (P->data <= key); P = P->next) {
    }

    // Shift sub sequence from i+1 to j-1 to after key at j
    if (P->data > key) {
      Q->next = R->next;
      R->next = P->next;
      P->next = R;
    } else {
      Q->next = R->next;
      R->next = A;
      A = R;
    }
  }
  return A;
}

(Thinking)

 

[evinda]

Actually, we won't need i, j, or n any more.
It's more like this:

InsertionSort(NODE* A)
  NODE *P, *Q, *R, *S;
  int key;

  if (A == NULL)
    return A;
  Q = A;
  R = Q->next;

  // For each key starting at j = 2
  for (Q = A, R = Q->next; R != NULL; Q = R, R = S) {
    key = R->data;
    S = R->next;

    // Find element at i < j such that A[i] <= key or else set i to 0
    for (P = A; (P != R) && (P->data <= key); P = P->next) {
    }

    // Shift sub sequence from i+1 to j-1 to after key at j
    if (P->data > key) {
      Q->next = R->next;
      R->next = P->next;
      P->next = R;
    } else {
      Q->next = R->next;
      R->next = A;
      A = R;
    }
  }
  return A;
}

(Thinking)

Can we use S, at the for loop, without initializing it? (Thinking)

What shoud be its value?

 

[I like Serena]

Can we use S, at the for loop, without initializing it? (Thinking)

What shoud be its value?

I have introduced S to keep track of the element that comes after R, which we need to be able to move on to the next element. (Thinking)

It is initialized at the beginning of the for-loop.
The first time it is used is as part of the increment-part of the for-loop, which comes later. (Wasntme)

 

[evinda]

I have introduced S to keep track of the element that comes after R, which we need to be able to move on to the next element. (Thinking)

It is initialized at the beginning of the for-loop.
The first time it is used is at the end of the for-loop.
And only then is it changed as part of the increment-part of the for-loop. (Wasntme)

Suppose that we have this list:

$$\boxed{3} \to \boxed{1} \to \boxed{5} \to \boxed{2} \to \text{NULL}$$

At the first for-loop, P and R will point to 3, and R will point to 1, right? (Thinking)
Then, the commands:

Q->next=R->next;

and

R->next=P->next

will be executed, right?

P->next points to R, so what will the command

R->next=P->next

do? (Worried)

 

[I like Serena]

Suppose that we have this list:

$$\boxed{3} \to \boxed{1} \to \boxed{5} \to \boxed{2} \to \text{NULL}$$

At the first for-loop, P and R will point to 3, and R will point to 1, right? (Thinking)
Then, the commands:

Q->next=R->next;

and

R->next=P->next

will be executed, right?

P->next points to R, so what will the command

R->next=P->next

do? (Worried)

Oh my, that means there are still mistakes in the code. (Tmi)

What should happen is:

      Q->next = R->next;
      R->next = A;
      A = R;

That is,
$$A \to \overset{Q}{\boxed{3}} \to \overset{R}{\boxed{1}} \to \overset{S}{\boxed{5}} \to \boxed{2} \to \text{NULL}$$
should be transformed to:
$$A \to \overset{R}{\boxed{1}} \to \overset{Q}{\boxed{3}} \to \overset{S}{\boxed{5}} \to \boxed{2} \to \text{NULL}$$
making it sorted up to, but before, S.

The code should search for the last occurrence of P that still has P->data <= key.
If it cannot find it, as in this case, the key has to be moved to the beginning of the list.
This implies that A has to be changed.

Perhaps you can fix it? (Blush)

 

[evinda]

Oh my, that means there are still mistakes in the code. (Tmi)

What should happen is:

      Q->next = R->next;
      R->next = A;
      A = R;

That is,
$$A \to \overset{Q}{\boxed{3}} \to \overset{R}{\boxed{1}} \to \overset{S}{\boxed{5}} \to \boxed{2} \to \text{NULL}$$
should be transformed to:
$$A \to \overset{R}{\boxed{1}} \to \overset{Q}{\boxed{3}} \to \overset{S}{\boxed{5}} \to \boxed{2} \to \text{NULL}$$
making it sorted up to, but before, S.

The code should search for the last occurrence of P that still has P->data <= key.
If it cannot find it, as in this case, the key has to be moved to the beginning of the list.
This implies that A has to be changed.

Perhaps you can fix it? (Blush)

Is it maybe like that? (Worried)

InsertionSort(NODE* A){
  NODE *P, *Q, *R, *S;
  int key;

  if (A == NULL)
    return A;

  // For each key starting at j = 2
  for (Q = A, R = Q->next; R != NULL; Q = R, R = S) {
    key = R->data;
    S = R->next;

    // Find element at i < j such that A[i] <= key or else set i to 0
    for (P = A; (P != R) && (P->data <= key); P = P->next) {
    }
    // Shift sub sequence from i+1 to j-1 to after key at j
    if (P->data > key) {
      Q->next = R->next;
      R->next = A;
      A=R;
    } else {
      Q->next = R->next;
      P->next=Q->next->next;
    }
  }
  return A;
}

Or am I wrong?

 

[evinda]

Is it maybe like that? (Thinking)

InsertionSort(NODE* A){
  NODE *P, *Q, *R, *S;
  int key;

  if (A == NULL)
    return A;
  Q = A;
  R = Q->next;

  // For each key starting at j = 2
  for (Q = A, R = Q->next; R != NULL; Q = R, R = S) {
    key = R->data;
    S = R->next;

    // Find element at i < j such that A[i] <= key or else set i to 0
    for (P = A; (P != R) && (P->data <= key); P = P->next) {
    }

    // Shift sub sequence from i+1 to j-1 to after key at j
    if (P->data > key) {
      Q->next = R->next;
      R->next = A;
      A = R;
    } else {
	      R->next=S->next;
	      S->next=Q->next;
          Q->next =S;   
    }
  }
  return A;
}

 

[I like Serena]

Is it maybe like that? (Thinking)

InsertionSort(NODE* A){
  NODE *P, *Q, *R, *S;
  int key;

  if (A == NULL)
    return A;
  Q = A;
  R = Q->next;

  // For each key starting at j = 2
  for (Q = A, R = Q->next; R != NULL; Q = R, R = S) {
    key = R->data;
    S = R->next;

    // Find element at i < j such that A[i] <= key or else set i to 0
    for (P = A; (P != R) && (P->data <= key); P = P->next) {
    }

    // Shift sub sequence from i+1 to j-1 to after key at j
    if (P->data > key) {
      Q->next = R->next;
      R->next = A;
      A = R;
    } else {
	      R->next=S->next;
	      S->next=Q->next;
          Q->next =S;   
    }
  }
  return A;
}

Neh. S shouldn't be involved.
But the for-P loop has to stop one iteration earlier. (Doh)

 

[evinda]

Neh. S shouldn't be involved.
But the for-P loop has to stop one iteration earlier. (Doh)

Could you give me a hint what else I could do, in order not to involve S? (Thinking)

InsertionSort(NODE* A){
  NODE *P, *Q, *R, *S;
  int key;

  if (A == NULL)
    return A;
  Q = A;
  R = Q->next;

  // For each key starting at j = 2
  for (Q = A, R = Q->next; R != NULL; Q = R, R = S) {
    key = R->data;
    S = R->next;

    // Find element at i < j such that A[i] <= key or else set i to 0
    for (P = A; (P != R) && (P->data < key); P = P->next) {
    }

    // Shift sub sequence from i+1 to j-1 to after key at j
    if (P->data > key) {
      Q->next = R->next;
      R->next = A;
      A = R;
    } else {
	      R->next=S->next;
	      S->next=Q->next;
          Q->next =S;   
    }
  }
  return A;
}

Now, the for-P loop stops one iteration earlier, right? (Thinking)

 

[I like Serena]

Could you give me a hint what else I could do, in order not to involve S? (Thinking)

I'm not sure why you introduced S there.
Wasn't it okay as it was? (Wondering)

    // Find element at i < j such that A[i] <= key or else set i to 0
    for (P = A; (P != R) && (P->data < key); P = P->next) {
    }

Now, the for-P loop stops one iteration earlier, right? (Thinking)

Not quite.
It depends on the data, but we could still get one too far. (Doh)

I was thinking more of:

    // Find element at i < j such that A[i] <= key or else set i to 0
    for (P = A; (P->next != R) && (P->next->data <= key); P = P->next) {
    }

(Thinking)

 

[evinda]

I'm not sure why you introduced S there.
Wasn't it okay as it was? (Wondering)

 if (P->data > key) {
      Q->next = R->next;
      R->next = P->next;
      P->next = R;
    } else {
      Q->next = R->next;
      R->next = A;
      A = R;
    }

I think that the commands [m]R->next = A;[/m] and [m]A = R;[/m] weren't right... Am I wrong? (Thinking)

 

[I like Serena]

That is,
$$A \to \overset{Q}{\boxed{3}} \to \overset{R}{\boxed{1}} \to \overset{S}{\boxed{5}} \to \boxed{2} \to \text{NULL}$$
should be transformed to:
$$A \to \overset{R}{\boxed{1}} \to \overset{Q}{\boxed{3}} \to \overset{S}{\boxed{5}} \to \boxed{2} \to \text{NULL}$$
making it sorted up to, but before, S.

 if (P->data > key) {
      Q->next = R->next;
      R->next = P->next;
      P->next = R;
    } else {
      Q->next = R->next;
      R->next = A;
      A = R;
    }

I think that the commands [m]R->next = A;[/m] and [m]A = R;[/m] weren't right... Am I wrong? (Thinking)

Well, let's see... if we look at how the list is transformed, I think it should be:

      Q->next = R->next;
      R->next = Q;
      A = R;

or we might also use:

      Q->next = S;
      R->next = Q;
      A = R;

(Wasntme)

 

[evinda]

I tried to apply the algorithm on this list:View attachment 3804
After some steps we have that [m] P->next=R [/m] and [m] P->data>key[/m] where [m] P->data=100[/m] and [m] key=1[/m].
So we execute the if condition and then we have the command [m] R->next=P->next[/m] but [m]P->next=R[/m].
So does [m] R->next [/m] point to [m] R [/m] ? (Thinking)