Insertion Sort: Explained and Applied

  • Context: MHB 
  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Applied Sort
Click For Summary

Discussion Overview

The discussion revolves around the application of the Insertion Sort algorithm, specifically how it can be implemented for sorting lists as opposed to arrays. Participants explore the mechanics of the algorithm, propose variations, and discuss the challenges of adapting the algorithm for different data structures.

Discussion Character

  • Technical explanation
  • Conceptual clarification
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • Some participants provide pseudocode for the Insertion Sort algorithm as applied to arrays, detailing the insertion process.
  • Others question how to adapt the algorithm for a list data structure, noting that lists can be implemented in various ways, including singly linked lists.
  • A participant suggests using a temporary variable to traverse a singly linked list and insert elements in the correct position based on comparisons.
  • There are multiple proposals for how to shift elements in a list when inserting a new element, with varying degrees of clarity and correctness.
  • Some participants express uncertainty about the correctness of their proposed modifications to the algorithm and seek clarification on generalizing the approach for different cases.
  • A sub-algorithm is proposed for shifting elements in a list, which includes pointers to the relevant elements before and after the insertion point.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the best method to implement Insertion Sort for lists, and there are competing views on how to handle element shifting and pointer management. The discussion remains unresolved with ongoing questions and clarifications being sought.

Contextual Notes

Participants express uncertainty regarding the generalization of their proposed solutions and the need for additional pointers in certain cases. There are also mentions of specific sequences that may not apply universally.

Who May Find This Useful

This discussion may be useful for individuals interested in algorithm design, particularly those looking to understand data structure manipulation and sorting algorithms in different contexts.

  • #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)
 
Technology news on Phys.org
  • #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)
 
  • #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)
 
  • #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: 115

Similar threads

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