insertion sort algorithm in c not working-CodePudding

I am trying to sort an array of integers for finding the median of the same array. The code am using sorts only the first two elements of the 10 element array. I have cross checked the swapping of variables in the loops but everything seems okay.

void sort(int *arr) {
    //get the size of this array
    int size = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < size; i  ) {
        for (int j = i   1; j < size; j  ) {
            if (arr[i] > arr[j]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

Application

#include <stdlib.h>
#include <stdio.h>

int main() {
    int numbers[10];
    numbers[0] = 10;
    numbers[1] = 9;
    numbers[2] = 8;
    numbers[3] = 7;
    numbers[4] = 6;
    numbers[5] = 5;
    numbers[6] = 4;
    numbers[7] = 3;
    numbers[8] = 2;
    numbers[9] = 1;
    
    sort(numbers);
    //code sorts the element in the first and second index, the rest are unsorted please help
    
    return 0;
}

What am I doing wrong?

CodePudding user response：

The function parameter has a pointer type

void sort(int* arr){

Even if you will rewrite the function declaration like

void sort( int arr[10] ){

nevertheless the compiler will adjust the function parameter having the array type to pointer to the element type as it is written in your original function declaration

void sort(int* arr){

And in this call of the function

sort(numbers);

the array designator is implicitly converted to a pointer to its first element. That is the call above in fact is the same as

sort( &numbers[0] );

So using the operator sizeof with a pointer expression yields the size of a pointer. That is this line

//get the size of this array
int size=sizeof(arr)/sizeof(arr[0]);

is equivalent to

//get the size of this array
int size=sizeof( int * )/sizeof( int );

and yields either 2 or 1 depending on the used system.

You need to declare the function like

void sort( int *arr, size_t n );

and pass to the function the number of elements in the array explicitly.

Bear in mind that in general the user can use the function for a dynamically allocated array.

Pay attention to that the used by you algorithm is not the insertion sort algorithm. It is the selection sort algorithm with redundant swaps.

A function that implements the insertion sort algorithm can look for example the following way as it is shown in the demonstration program below.

#include <stdio.h>

void insertion_sort( int a[], size_t n )
{
    for ( size_t i = 1; i < n; i   )
    {
        int current = a[i];
        size_t j = i;
        for ( ; j != 0 && current < a[j - 1]; j-- )
        {
            a[j] = a[j - 1];
        }

        if ( j != i ) a[j] = current;
    }
}

int main()
{
    int a[] = { 9,8, 7, 6, 5, 4, 3, 2, 1, 0 };
    const size_t N = sizeof( a ) / sizeof( *a );

    for (size_t i = 0; i < N; i  )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );

    insertion_sort( a, N );

    for (size_t i = 0; i < N; i  )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );
}

The program output is

9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9

As for the function that implements the selection sort algorithm then without redundant swaps it can look the following way as it is shown in the next demonstration program.

#include <stdio.h>

void selection_sort( int a[], size_t n )
{
    for ( size_t i = 0; i < n; i   )
    {
        size_t min = i;

        for ( size_t j = i   1; j < n; j   )
        {
            if (a[j] < a[min]) min = j;
        }

        if ( min != i )
        {
            int tmp = a[i];
            a[i] = a[min];
            a[min] = tmp;
        }
    }
}

int main()
{
    int a[] = { 9,8, 7, 6, 5, 4, 3, 2, 1, 0 };
    const size_t N = sizeof( a ) / sizeof( *a );

    for (size_t i = 0; i < N; i  )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );

    selection_sort( a, N );

    for (size_t i = 0; i < N; i  )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );
}

The program output is the same as shown above

9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9

CodePudding user response：

This is because int size = sizeof(arr) / sizeof(arr[0]); will return 2, because sizeof(arr) will give the sizeof a pointer to int, which in your case is 8 bytes and then sizeof(arr[0]) will give a sizeof int which in your case is 4 bytes.

So,

8 / 4 = 2

Fix:

Add another parameter for the length of the array.
type-cast numbers to (int *) for sort() function
Your sort() function does not implement insertion sort algorithm, instead it is selection sort algorithm. READ MORE
There's no need of stdlib.h header file in your code

Like this: TRY IT ONLINE

#include <stdio.h>

void sort(int *arr, size_t len)
{
    for (int i = 0; i < len; i  )
    {
        for (int j = i   1; j < len; j  )
        {
            if (arr[i] > arr[j])
            {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

// using `const` keyword, because `arr` isn't modifying inside `print()` function
void print(const int *arr, size_t len){
    for (size_t i = 0; i < len; i  )
    {
        printf("%d\n", arr[i]);
    }
}

int main(void)
{
    int numbers[10];
    numbers[0] = 10;
    numbers[1] = 9;
    numbers[2] = 8;
    numbers[3] = 7;
    numbers[4] = 6;
    numbers[5] = 5;
    numbers[6] = 4;
    numbers[7] = 3;
    numbers[8] = 2;
    numbers[9] = 1;

    size_t len = sizeof(numbers) / sizeof(numbers[0]);
    sort((int *)numbers, len);

    print(numbers, len);
    return 0;
}