MHB Insertion Sort: Explained and Applied

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