C kind of sorting

Question

Ok so a function which arranges the elements in an array in such a way that all elements smaller than a given value are placed into positions to the left of the elements that are larger than the given value.

For instance if the array contents are {4,6,2,9,1,7,3,10} and x is given as 5, then {4,3,2,1,9,7,6,10} is a possible solution, since all elements smaller than 5 are to the left of the elements larger than 5.

Also, using brackets [ ] is ​ forbidden ​ except for defining the array in the main function.

Also, implement a function which prints the contents of an array. Both functions must be implemented recursively. you are allowed to access each element of the array only for once.

ok so this "challenge" and I dont know if it is possible with the given restrictions. I have tried to make it with a while loop and then convert it to recursive somehow but you are not allowed to change the parameters as well. Does anyone know a solution.

I have written something but its garbage.

#include <stdio.h>
#define length 8
void selection(int array[],int size, int x){

int i=0;
int temp;

        if(( array[i]>x ) && (array[i] > array[i+1])){

             temp=array[i+1];
             array[i+1]=array[i];
             array[i]=temp;

             i++;
                selection(array+1,size-1,x)
            }
        else if(( array[i] > x) && ( array[i+1] > array[i])){
                i++;
            }

    //This is not correct 
     }

void printArray(int arr[], int start, int len)
   {

    if(start >= len)
        return;

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


    printArray(arr, start + 1, len); 
   }

int main(){

    int array[length]={6,4,2,9,1,7,3,10};
    int x=5;

     selection(array,length,x);
     printArray(array,0,length);

return 0;
}

I havent implemented the a recursive solution because things I tried kept giving segmentation faults because I was reaching outside the array.

Can anyone do this recursivly without for or while. I guess you need to split the array and look at it half by half

Answer 1

Here you are.

#include <stdio.h>

void partition( int a[], size_t n, int pivot )
{
    if ( !( n < 2 ) )
    {
        if ( *a < pivot )
        {
            partition( a + 1, n - 1, pivot );
        }
        else
        {
            if ( *( a + n - 1 ) < pivot )
            {
                int tmp = *a;
                *a = *( a + n - 1 );
                *( a + n - 1 ) = tmp;
                partition( a + 1, n - 2, pivot );
            }
            else
            {
                partition( a, n - 1, pivot );
            }
        }
    }
}

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

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


     int pivot = 5;

     partition( a, N, pivot );

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

     return 0;
}

The program output is

4 6 2 9 1 7 3 10 
4 3 2 1 9 7 6 10 

Or also with a recursive definition of the function printArray.

#include <stdio.h>

void partition( int a[], size_t n, int pivot )
{
    if ( !( n < 2 ) )
    {
        if ( *a < pivot )
        {
            partition( a + 1, n - 1, pivot );
        }
        else
        {
            if ( *( a + n - 1 ) < pivot )
            {
                int tmp = *a;
                *a = *( a + n - 1 );
                *( a + n - 1 ) = tmp;
                partition( a + 1, n - 2, pivot );
            }
            else
            {
                partition( a, n - 1, pivot );
            }
        }
    }
}

void printArray( const int a[], size_t n )
{
    if ( n )
    {
        printf( "%d ", *a );
        printArray( a + 1, n - 1 );
    }
    else
    {
        putchar( '\n' );
    }
}

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

     printArray( a, N );     

     int pivot = 5;

     partition( a, N, pivot );

     printArray( a, N );     

     return 0;
}

The recursive function printArray also can be defined the following way

void printArray( const int a[], size_t n )
{
    n == 0 ? ( void )putchar( '\n' ) 
           : ( printf( "%d ", *a ), printArray( a + 1, n - 1 ) );
}