# Sorting numbers using Insertion method

In this program I've tried the insertion Sort method to execute

#include<stdio.h>
int main()
{
int numbers[25]={21,89,98,76,56,4,345,34,53,56,68,68,68,575,7,4,45,45,35,35,35,2,22,52,235}, temp_str, comp_count=0 ;

while(comp_count<25) // To ensure sorting completion
{
for(int comp_loop=0; comp_loop<24; comp_loop++) // To go for every array element
{
if(numbers[comp_loop]>numbers[comp_loop+1]) // For comparing two successive elements
{

// Storing smaller number in separate variable

temp_str = numbers[comp_loop+1];

// Promoting value addresses by 1 index

for(int pro_loop=comp_loop; pro_loop>=0; pro_loop--)
{
numbers[pro_loop+1]= numbers[pro_loop];
}

// Placing smaller number at the top index of array

numbers[0]= temp_str;

comp_count=0; // reset to 0 if comparison results to true
}
else
{
comp_count++; // to count how many compares are false
}

}
}

//Printing the sorted list

for(int rslt_loop=0; rslt_loop<25; rslt_loop++)
{
printf(" %d",numbers[rslt_loop]);
}
return 0;
}


To improve this program I would like to know from you, the possibilities.

First thoughts: all the code is in main(), but we would like to have a reusable function. I'd create a function that accepts an array and its length:

void insertion_sort(int arr[], size_t len)


Here is a good demonstration of why one declaration per line is a good style to follow:

int numbers[25]={ … }, temp_str, comp_count=0 ;


In the full line, temp_str and comp_count disappear off the screen and are harder to find.

Actually, we don't need temp_str up at this level - it can be local to the if test.

We have a lot of 25 (and one 24) in the code that makes it hard to change for arrays of different length. Everything that depends on the length should get it from the same place (the parameter to the function, once we create that).

We can derive the array size from the array itself:

int numbers[] =
{ 21, 89, 98,  76,  56,   4, 345, 34, 53, 56,
68, 68, 68, 575,   7,   4,  45, 45, 35, 35,
35,  2, 22,  52, 235 };
const size_t length = sizeof numbers / sizeof numbers[0];


The outer loop (while(comp_count<25) wouldn't be necessary if we'd implemented insertion sort correctly. A single pass should sort the array.

The presence of the outer loop suggests we actually have a form of bubble sort, rather than insertion sort. The problem is that we always move values to the front of the array here, instead of in the correct insert position:

        temp_str = numbers[comp_loop+1];
for(int pro_loop=comp_loop; pro_loop>=0; pro_loop--)
{
numbers[pro_loop+1]= numbers[pro_loop];
}
numbers[0]= temp_str;


To fix this, it's worth writing a binary search function that can find the insertion position within the the sorted part of the array.

The copying loop (indexed using pro_loop) can be replaced with the Standard Library memmove() function (from <string.h>):

                        int temp = numbers[comp_loop+1];
memmove(numbers+1, numbers, (comp_loop + 1) * sizeof *numbers);
numbers[0]= temp;


We write an unfinished line of output. We should terminate it with a newline. The easiest way is to add

    puts("");


# Modified program

This is completely re-worked, as suggested above:

#include <stdio.h>
#include <string.h>

/* return index at which value should be inserted */
static size_t find(const int arr[], size_t len, int value)
{
size_t a = 0;
size_t z = len;

if (value < arr[a]) { return 0; }
while (a + 1 < z) {
size_t m = a + (z - a) / 2;
if (value <= arr[m]) {
z = m;
} else {
a = m;
}
}
return z;
}

static void insertion_sort(int arr[], size_t len)
{
for (size_t i = 1;  i < len;  ++i) {
int value = arr[i];
size_t new_pos = find(arr, i, value);
memmove(arr+new_pos+1, arr+new_pos, (i - new_pos) * (sizeof *arr));
arr[new_pos]= value;
}
}

int main(void)
{
int numbers[] =
{ 21, 89, 98,  76,  56,   4, 345, 34, 53, 56,
68, 68, 68, 575,   7,   4,  45, 45, 35, 35,
35,  2, 22,  52, 235 };
const size_t length = sizeof numbers / sizeof numbers[0];

insertion_sort(numbers, length);

for (size_t i = 0;  i < length;  ++i) {
printf(" %d", numbers[i]);
}
puts("");
}


I don't understand what this is doing.

I see it takes each successive element and if it's not already greater than the previous last element, I expect to insert it into the correct position: that is the definition of Insertion Sort.

Instead, it appears to move it all the way to the left, to element zero.

Then the whole sort is inside another while loop that terminates when it discovers that all the elements are already in order.

This is not an Insertion Sort. I don't know what it is, or if it has a serious name. It works on the principle of "if it's not sorted, change something and check again". I suppose you could use an induction proof to show that it always works, and add a counter in your code to find out just how inefficient it is.

To improve this program I would like to know from you, the possibilities.

The most important thing would be to implement an actual Insertion Sort algorithm.

A guess: you tried to write an insertion sort, and when it didn't work, you added the outer loop and then it got the right answer.

I think that when learning to write sorts and other algorithms, part of the assignment should be to include counters and the testing should not just verify that it got the right result, but chart the performance. Is the number of comparisons you made O(n log n), O(n²), or something unexpectedly higher like O(n³)?

Also, if you don't mind answering my little survey: why are you writing in C rather than C++?