C вид сортировки

Question

Хорошо, так что функция, которая размещает элементы в массиве таким образом, что все элементы, меньшие, чем заданное значение, помещаются в позиции слева от элементов, которые больше, чем заданное значение.

Например, если содержимое массива {4,6,2,9,1,7,3,10} и x задано как 5, то {4,3,2,1, 9,7,6,10} является возможным решением, так как все элементы меньше 5 находятся слева от элементов больше 5.

Также использование скобок [] запрещено, кроме для определения массива в основной функции.

Также реализуйте функцию, которая печатает содержимое массива. Обе функции должны быть реализованы рекурсивно. вам разрешен доступ к каждому элементу массива только один раз.

хорошо, так что это «вызов», и я не знаю, возможно ли это с данными ограничениями. Я попытался сделать это с помощью l oop, а затем каким-то образом преобразовать его в рекурсивный, но вы также не можете изменять параметры. Кто-нибудь знает решение.

Я написал что-то, кроме его мусора.

#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;
}

Я не реализовал рекурсивное решение, потому что вещи, которые я пытался, продолжали давать ошибки сегментации потому что я тянулся за пределы массива.

Может ли кто-нибудь сделать это рекурсивно без или в течение времени. Я думаю, вам нужно разделить массив и посмотреть на него пополам

Answer 1

Вот, пожалуйста.

#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;
}

Вывод программы:

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

Или также с рекурсивным определением функции 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;
}

Рекурсивная функция printArray также может быть определена следующим образом

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