two different results with insertion sort

Question

when I code this way i got correct results.1,2,3,4,6,

#include<stdio.h>
main()
{
    int i,x,temp,arr[5]={4,3,2,1,6};
    for(i=1;i<5;i++){
        temp=arr[i];
        for(x=i;x>0;x--){
            if(arr[x-1]>temp)
                arr[x]=arr[x-1];
            else 
                break;
        }arr[x]=temp;
    }
    for(i=0;i<5;i++)
    printf("%i,",arr[i]);
}

but in this way I got 4,4,4,4,6,an incorrect answer.

#include<stdio.h>
main(){
    int i,x,temp,arr[5]={4,3,2,1,6};
    for(i=1;i<5;i++){
        temp=arr[i];
        for(x=i;x>0;x--){
            if(arr[x-1]>temp)
                arr[x]=arr[x-1];
            else 
            {
                arr[x]=temp;
                break;
            }
        }
    }
    for(i=0;i<5;i++)
    printf("%i,",arr[i]);
}

but it looks like both are same.can you explain it?

Answer 1

There is a difference between both.

Note: temp will be the considered as the min element of that pass in both code. Because we search for values greater than temp for index i to 0.

Former one:

The inner loop ends either with x = 0 (or) x = i. Here you replace a[x] with temp. So obviously the temp(min value of that pass) will be inserted correctly in its appropriate place.

                    +----------------+
 Initial Array      |    4 3 2 1 6   |
                    +----------------+

+-------------------+                |  +-------------------+  
|       i = 1       |  temp = 3      |  |       i = 2       |   temp = 2
+-------+-----------+                |  +-------+-----------+
| x = 1 | 4 4 2 1 6 | arr[1] = 4     |  | x = 2 | 3 4 4 1 6 |   arr[2] = 4
+-------+-----------+                |  +-------+-----------+  
|     3 4 2 1 6     | arr[0] = temp  |  | x = 1 | 3 3 4 1 6 |   arr[1] = 3
+-------------------+                |  +-------+-----------+
                                     |  |     2 3 4 1 6     |   arr[0] = temp
                                     |  +-------------------+

+-------------------+                |  +-------------------+  
|       i = 3       |  temp = 1      |  |       i = 4       |  temp = 6
+-------+-----------+                |  +-------------------+
| x = 3 | 2 3 4 4 6 |  arr[3] = 4    |  |     1 2 3 4 6     | arr[4] = temp  
+-------+-----------+                |  +-------------------+
| x = 2 | 2 3 3 4 6 |  arr[2] = 3    |  
+-------+-----------+                |  
| x = 1 | 2 2 3 4 6 |  arr[1] = 2    |  
+-------+-----------+                |
|     1 2 3 4 6     |  arr[0] = temp |
+-------------------+                |

Latter one:

Here,

  if arr[x-1] > temp do arr[x] = arr[x-1]
  else do arr[x] = temp

So no proper insertion is done and values are lost.

                       +----------------+
    Initial Array      |    4 3 2 1 6   |
                       +----------------+

+-------------------+                |  +-------------------+  
|       i = 1       |  temp = 3      |  |       i = 2       |   temp = 2
+-------+-----------+                |  +-------+-----------+
| x = 1 | 4 4 2 1 6 | arr[1] = 4     |  | x = 2 | 4 4 4 1 6 |   arr[2] = 4
+-------+-----------+                |  +-------+-----------+  
|     4 4 2 1 6     |                |  | x = 1 | 4 4 4 1 6 |   arr[1] = 4
+-------------------+                |  +-------+-----------+
                                     |  |     4 4 4 1 6     |   
                                     |  +-------------------+

+-------------------+                |  +-------------------+  
|       i = 3       |  temp = 1      |  |       i = 4       |  temp = 6
+-------+-----------+                |  +-------------------+
| x = 3 | 4 4 4 4 6 |  arr[3] = 4    |  |     4 4 4 4 6     | arr[4] = temp  
+-------+-----------+                |  +-------------------+
| x = 2 | 4 4 4 4 6 |  arr[2] = 4    |  
+-------+-----------+                |  
| x = 1 | 4 4 4 4 6 |  arr[1] = 4    |  
+-------+-----------+                |
|     4 4 4 4 6     |                |
+-------------------+                |

Instead of using break, you can control the code with for-loop itself.

#include <stdio.h>
int main()
{
    int i,x,temp,arr[5]={5,6,5,1,2};
    for(i=1;i<5;i++)
    {
         temp=arr[i];
         for(x=i;arr[x-1]>temp;x--)
             arr[x]=arr[x-1];
         arr[x]=temp;
    }
    for(i=0;i<5;i++)
        printf("\t%d",arr[i]);
return 0;
}

Answer 2

1:

#include<stdio.h>
main(){
  int i,x,temp,arr[5]={4,3,2,1,6};
  for(i=1;i<5;i++){
    temp=arr[i];
    for(x=i;x>0;x--){
      if(arr[x-1]>temp)
        arr[x]=arr[x-1];
      else 
        break;
    }
    arr[x]=temp;
  }
  for(i=0;i<5;i++);
  printf("%i,",arr[i]);
}

2:

#include<stdio.h>
main(){
  int i,x,temp,arr[5]={4,3,2,1,6};
  for(i=1;i<5;i++){
    temp=arr[i];
    for(x=i;x>0;x--){
      if(arr[x-1]>temp)
        arr[x]=arr[x-1];
      else {
        arr[x]=temp;
        break;
      }
    }
  }
  for(i=0;i<5;i++)
  printf("%i,",arr[i]);
}

I think that is the correct formatting, the difference in the second set as seen above is the arr[x]=temp executing inside the else.

Answer 3

Your second case should be like this....

#include<stdio.h>
main(){
    int i,x,temp,arr[5]={4,3,2,1,6};
    for(i=1;i<5;i++){
        temp=arr[i];
        for(x=i;x>0;x--){
            if(arr[x-1]>temp){
                arr[x]=arr[x-1];
                arr[x-1]=temp;// earlier you were missing this part to swap the values
            }
            else 
            {
                //arr[x]=temp; this doesn't need here.
                break;
            }
        }//arr[x]=temp; Here it will always executed after your for loop is executed.
    }
    for(i=0;i<5;i++)
    printf("%i,",arr[i]);

}

Answer 4

In your second case, arr[x]=temp is not executed whenever temp is less than all the values in the array between 0 and i, while temp ought to go on arr[0] when this is the case (as is done by the first version). Since the cells are properly shifted to the right, arr[0] is in fact copied instead of simply moved each time this occurs (in your example, for all the cells except the last one, leading to your final output).