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.
  • #36
evinda said:
Or do I have to add at the code something else? (Thinking)

Weird.
I thought I had already answered in this thread. :confused:
evinda said:
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.}

Yes, but you still need lines 8-10:
Code: 
8.                i=i-1;
9.       }
10.      A[i+1]=key;
(Wasntme)
 
Technology news on Phys.org
  • #37
I like Serena said:
Weird.
I thought I had already answered in this thread. :confused:

Yes, but you still need lines 8-10:
Code: 
8.                i=i-1;
9.       }
10.      A[i+1]=key;
(Wasntme)

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,i+1).data = Nth(A,i).data
8.                i=i-1;
9.       }
10.      A[i+1]=key;
11. return A;
 
  • #38
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,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)
 
  • #39
I like Serena said:
Well... we can't do [m]A[i+1]=key[/m] with a linked list... (Worried)

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,i+1).data = Nth(A,i).data
8.                i=i-1;
9.       }
10.      Nth(A,i+1).data=key;
11. return A;
I like Serena said:
Btw, can you tell what the order of this algorithm is now? (Wondering)

Is it $O(n^3)$ ? (Thinking)
 
  • #40
evinda said:
So, is it like that? (Thinking)

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

Yes! (Nod)
 
  • #41
I like Serena said:
Yes! (Nod)

And could we also write an algorithm with complexity $O(n^2)$ ? (Thinking)
 
  • #42
evinda said:
And could we also write an algorithm with complexity $O(n^2)$ ? (Thinking)

Yes. (Smile)
 
  • #43
I like Serena said:
Yes. (Smile)

Could you give me a hint, how we could do this? (Thinking)
 
  • #44
evinda said:
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:
Code: 
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)
 
Last edited:
  • #45
I like Serena said:
We would need to make the algorithm a little bit more abstract. (Nerd)

Something like:
Code: 
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)
 
  • #46
evinda said:
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)
 
  • #47
I like Serena said:
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? :confused:

Code: 
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)
 
  • #48
evinda said:
So, you mean that it is like that? :confused:

Code: 
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:
Code: 
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)
 
  • #49
I like Serena said:
Actually, we won't need i, j, or n any more.
It's more like this:
Code: 
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? :confused:
 
  • #50
evinda said:
Can we use S, at the for loop, without initializing it? (Thinking)

What shoud be its value? :confused:

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)
 
  • #51
I like Serena said:
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:
Code: 
Q->next=R->next;
and
Code: 
R->next=P->next

will be executed, right?

P->next points to R, so what will the command
Code: 
R->next=P->next
do? (Worried)
 
  • #52
evinda said:
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:
Code: 
Q->next=R->next;
and
Code: 
R->next=P->next

will be executed, right?

P->next points to R, so what will the command
Code: 
R->next=P->next
do? (Worried)

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

What should happen is:
Code: 
      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)
 
  • #53
I like Serena said:
Oh my, that means there are still mistakes in the code. (Tmi)

What should happen is:
Code: 
      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)

Code: 
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? :confused:
 
  • #54
Is it maybe like that? (Thinking)

Code: 
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;
}
 
  • #55
evinda said:
Is it maybe like that? (Thinking)

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

Code: 
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)
 
  • #57
evinda said:
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)
Code: 
    // 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:
Code: 
    // 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)
 
  • #58
I like Serena said:
I'm not sure why you introduced S there.
Wasn't it okay as it was? (Wondering)

Code: 
 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)
 
  • #59
I like Serena said:
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.
evinda said:
Code: 
 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:
Code: 
      Q->next = R->next;
      R->next = Q;
      A = R;
or we might also use:
Code: 
      Q->next = S;
      R->next = Q;
      A = R;
(Wasntme)
 
  • #60
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)
 

Attachments

  • apply.png
    apply.png
    1.1 KB · Views: 68

Similar threads

MHB Selection Sort & Insertion Sort: Step-by-Step Guide to Sorting Data
Replies
4
Views
2K
MHB Intermediate Steps in Insertion Sort Algorithm
Replies
6
Views
4K
MHB How can we implement this sort?
Replies
1
Views
1K
Java Why use spread operator when sorting an array in JavaScript?
Replies
2
Views
1K
MHB Stable Algorithm: Insertion, Merge, Heap, Quicksort?
Replies
11
Views
3K
Why insertion sort works better than quick-sort for small data?
Replies
6
Views
8K
How are there so many sorting algorithms?
Replies
10
Views
4K
Sorting by moving groups of numbers
Replies
6
Views
2K
C/C++ Why is my insertion sort code not working for certain array sizes?
Replies
5
Views
1K
MHB How to Efficiently Merge a Sorted List and a Pre-Order Sorted Tree?
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top