Insertion sorting of a 2D array using pointers

Question

I have a task in my programming lesson - Sort the odd lines of the 2D array in ascending order using the insertion sort method, using a pointer. So far i tried without pointer because i don't know how to do it. Here is the code that i made and is not working like it should.

#include<stdio.h>
main(){
    
    int i,j,n,m;
    
    printf("Introduce n=");
    scanf("%d",&n);
    
    printf("Introduce m=");
    scanf("%d",&m);
    
    int a[n][m];
    
    for(i=0; i<n; i++){
        for(j=0; j<m; j++){
            printf("a[%d][%d]=",i,j);
            scanf("%d",&a[i][j]);
            }
    }
    
    for(i=1; i<n ; i++)
    {
        for(j=1; j<n; j++)
        {
            if(i%2==1)
            {
                for( j = 1 ; j < m ; j ++)
                {
                    int p = j;
                    while(p > 0 && a[i][p] < a[i][p-1])
                    {
                        int aux = a[i][p];
                        a[i][p] = a[i][p-1];
                        a[i][p-1] = aux;
                        p --;
                    }
                }
            }
        }
    }
    
    for(i=0; i<n; i++){
        for(j=0; j<m; j++){
            printf("a[%d][%d]=%d",i,j,a[i][j]);
        }
    }
    
    return 0;
}

You could just increment i by 2 instead of checking if i is odd at each iteration — NoShady420
– NoShady420, Commented Nov 9, 2020 at 19:03

Vlad from Moscow · Accepted Answer · 2020-11-09 20:57:05Z

It is not an easy task for beginners like you and me. Moreover it is unclear what these words "using a pointer" mean.

I can suggest the following solution shown in the demonstrative program below. That is there is a separate function that performs sorting using parameters having types of pointers to variable length arrays.

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

void sort_by_odd_rows( size_t n, 
                       int ( *first )[n], 
                       int ( *last )[n], 
                       int cmp( const int *, const int *, size_t ) )
{
    if ( first != last && ++first != last )
    {
        for ( int ( *next )[n] = first; ++next != last && ++next != last; )
        {
            int tmp[n];
            memcpy( tmp, *next, n * sizeof( int ) );
            
            int ( *current )[n] = next;
            while ( current != first && cmp( tmp, *( current - 2 ), n ) < 0 )
            {
                memcpy( *current, *( current - 2 ), n * sizeof( int ) );
                current -= 2;
            }
            
            if ( current != next )
            {
                memcpy( *current, tmp, n * sizeof( int ) );
            }
        }
    }
}

int cmp( const int *a, const int *b, size_t n )
{
    size_t i = 0;
    
    while ( i < n && a[i] == b[i] ) ++i;
    
    return i == n ? 0 : ( b[i] < a[i] ) - ( a[i] < b[i] );
}


int main(void) 
{
    size_t m = 10, n = 5;
    int a[m][n];
    
    srand( ( unsigned int )time( NULL ) );
    
    for ( size_t i = 0; i < m; i++ )
    {
        for ( size_t j = 0; j < n; j++ )
        {
            a[i][j] = rand() % ( m * n );
        }
    }

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

    sort_by_odd_rows( n, a, a + m, cmp );
    
    for ( size_t i = 0; i < m; i++ )
    {
        for ( size_t j = 0; j < n; j++ )
        {
            printf( "%2d ", a[i][j] );
        }
        putchar( '\n' );
    }
    
    putchar( '\n' );

    return 0;
}

The program output might look like

22  8  2 10  5 
33 21 20 17 45 
 7 20  3  7  5 
47 31 21 29 39 
46 44  0 31  7 
37 43  8 43 23 
 6 15 32  8 25 
39 41 49  9  8 
44 18 30 49 27 
35 46  9  7 28 

22  8  2 10  5 
33 21 20 17 45 
 7 20  3  7  5 
35 46  9  7 28 
46 44  0 31  7 
37 43  8 43 23 
 6 15 32  8 25 
39 41 49  9  8 
44 18 30 49 27 
47 31 21 29 39

As it is seen from the output odd rows of the array are sorted in the ascending order. The first elements of odd rows after sorting are 33, 35,37, 39, 47.

As for your code then it does not make a great sense. For example in these two for loops

    for(j=1; j<n; j++)
    {
        if(i%2==1)
        {
            for( j = 1 ; j < m ; j ++)
            //...

you are using the same variable j.

EDIT: It seems I have understood your assignment incorrectly and you need to sort elements within each odd row in the ascending order.

In this case the sorting function will look much simpler.

Here is a demonstrative program.

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

void insertion_sort( int *a, size_t n ) 
{
    for ( int *first = a, *last = a + n; first != last; ++first )
    {
        int tmp = *first;
        int *current = first;
        
        for ( ; current != a && tmp < *( current - 1 ); --current )
        {
                *current = *( current - 1 );
        }
        
        if ( current != first ) *current = tmp;
    }
}

int main(void) 
{
    size_t m = 10, n = 5;
    int a[m][n];
    
    srand( ( unsigned int )time( NULL ) );
    
    for ( size_t i = 0; i < m; i++ )
    {
        for ( size_t j = 0; j < n; j++ )
        {
            a[i][j] = rand() % ( m * n );
        }
    }

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

    for ( size_t i = 1; i < m; i += 2 )
    {
        insertion_sort( *( a + i ), n );
    }
    
    for ( size_t i = 0; i < m; i++ )
    {
        for ( size_t j = 0; j < n; j++ )
        {
            printf( "%2d ", a[i][j] );
        }
        putchar( '\n' );
    }
    
    putchar( '\n' );

    return 0;
}

The program output might look like

25 32 47 24 10 
33 39 32 31 33 
46  8 49 35 16 
32 34  9 35 22 
13 35 45 27 45 
17 37  2 13  6 
33 40 38 30 14 
48 15  6 32 49 
39 28  7 39 15 
26 23  2 35  8 

25 32 47 24 10 
31 32 33 33 39 
46  8 49 35 16 
 9 22 32 34 35 
13 35 45 27 45 
 2  6 13 17 37 
33 40 38 30 14 
 6 15 32 48 49 
39 28  7 39 15 
 2  8 23 26 35

Now each odd row has sorted elements in the ascending order.

That's what you call an answer with an added bonus of explaining how to sort both row-wise and column-wise for rows beginning with odd values. Too bad I can't vote twice...

Collectives™ on Stack Overflow

Insertion sorting of a 2D array using pointers

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related