Ndtyjky

I wrote a insertion sort program but it's not sorting the inputs correctly. Please help me find the error in the program.
If my input is 1 2 3 10 -1 -2 -3 then the output is

Value of a[0] is 1

Value of a[1] is 2

Value of a[2] is 3

Value of a[9] is -1

Value of a[10] is -2

Value of a[11] is -3

Value of a[19] is 10

I don't know if my logic is correct but I don't know where I did wrong please help me find the error in the program.

 #include<stdio.h>

void looper(int *);

void sort(int *,int *);

int main()

{

    int a[25];

    for(int i=0;i<=24;i++)

    {

        printf("Enter the value of a[%d] : ",i);

        scanf("%d",&a[i]);

    }

    looper(a);

    for(int i=0;i<=24;i++)

    {

        printf("Value of a[%d] is %dn",i,a[i]);

    }

}

void looper(int *p)

{

    for(int i=1;i<=24;i++)

    {

        for(int j=(i-1);j>=0;j--)

        {

            sort((p+i),(p+j));

        }

    }

}

void sort(int *a,int *b)

{

    int tmp;

    if((*a)<(*b))

    {

        tmp=*a;

        *a=*b;

        *b=tmp;

    }

}

Your current method is ... not quite right, for any kind of sort. Insertion sort would take an element and insert it at the correct index, then shift the already inserted items down appropriately. Something like

void looper(int *p)

{

    for (int i = 1;i < 25;i++)

    {

        int key = p[i];

        int j = i - 1;

        while (j >= 0 && p[j] > key)

        {

            p[j + 1] = p[j];

            j = j - 1;

        }

        p[j + 1] = key;

    }

}

Insertion sort is about building a sorted segment, and while doing so, using the fact it is sorted to optimally perform a binary search if the list representation supports random access (and your array does) for the location of the next element (which could go at the beginning, the end, or anywhere in between) . If it goes anywhere besides the position it is already in, shifting is going to happen. To place the incoming element, do the following:

1. Search the already sorted segment to find the location of the incoming value.


2. Once you find the spot it is supposed to be inserted, loop over the segment from there through the end of the sorted segment, continually swapping with the slot of the incoming element. When this is done, all of the elements up to then will be sorted.


3. This process repeats for each element

An example would be best

5 3 8 1



Active element: 5

Length of sorted segment: 0

Starting with a sorted segment of zero length, not much happens. the first element is already "sorted" and we can move on to the next.

5 3 8 1



Active element: 3

Length of sorted segment: 1

At this time we do a search of the sorted segment. We find that 3 belongs at the beginning of the segment. So we swap element pairs arr[0] and arr[1]. When finished, we now have a sorted segment of length 2.

3 5 8 1



Active element: 8

Length of sorted segment: 2

Again, search the sorted segment an we'll discover the element belongs on the end. but that's where it already is, so no swaps will take place and we can move on.

3 5 8 1



Active element: 1

Length of sorted segment: 3

This final element amplifies the general algorithm nicely. The 1 belongs where the 3 is, and everything should be shifted up accordingly. One way to do that is to loop up the sorted segment, starting at the insertion point (where 3 is) up through the end of the sorted segment, continually swapping the loop-indexed element with the active element slot (in this case, the last slot). The results after each swap will look like this:

3 5 8 1

^-----^



1 5 8 3

  ^---^



1 3 8 5

    ^-^



1 3 5 8

That's it. In code, it looks something like this:

#include <stdio.h>

#include <stdlib.h>



void swap_int(int *a, int *b)

{

    int tmp = *a;

    *a = *b;

    *b = tmp;

}



const int *binary_search(int value, const int arr, size_t len)

{

    if (len == 0)

        return arr;



    size_t mid = len / 2;



    if (value < arr[mid])

        return binary_search(value, arr, mid);



    return binary_search(value, arr + mid + 1, len - len / 2 - 1);



}



void insertion_sort(int arr, size_t len)

{

    for (size_t i = 0; i < len; ++i)

    {

        size_t pos = binary_search(arr[i], arr, i) - arr;

        for (size_t j = pos; j < i; ++j)

            swap_int(arr + i, arr + j);

    }

}



int main()

{

    int arr = { 5,3,8,6,9,2,4,1,7 };



    for (size_t i = 0; i < sizeof arr / sizeof *arr; ++i)

        printf("%d ", arr[i]);

    fputc('n', stdout);



    insertion_sort(arr, sizeof arr / sizeof *arr);



    for (size_t i = 0; i < sizeof arr / sizeof *arr; ++i)

        printf("%d ", arr[i]);

    fputc('n', stdout);

}

Output

5 3 8 6 9 2 4 1 7

1 2 3 4 5 6 7 8 9