divide.c

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

void print_array( int* array, int size ) {
  printf("[");
  for ( int i = 0; i < size; i++ ) {
    printf("\"%d\"", array[i]);
    if ( i < size-1 ) { printf(", "); }
  }
  printf("]\n");
}

int intcmp(const void* a, const void* b) {
  int x = *(int *)a;
  int y = *(int *)b;
  return ( x < y ) ? -1 : ( ( x == y) ? 0 : 1 );
}

int* get_separator( int* array, int size, int part ) {
  int* separator = malloc((part-1)*sizeof(int));
  for ( int i = 0; i < part-1; i++ ) {
    separator[i] = array[i];
  }
  qsort( separator, part-1, sizeof(int), intcmp );
  return separator;
}

int* get_segment_size( int* array, int size, int part, int* separator ) {
  int* segment_size = malloc( part*sizeof(int) );
  for ( int j = 0; j < size; j++ ) {
    if ( array[j] <= separator[0] ) { segment_size[0]++; }
    if ( array[j] > separator[part-2] ) { segment_size[part-1]++; }
  }
  for ( int i = 1; i < part-1; i++ ) 
    for ( int j = 0; j < size; j++ ) 
      if ( array[j] <= separator[i] && array[j] > separator[i-1] ) 
        segment_size[i]++;
  
  return segment_size;
}

int** divide_array( int* array, int size, int part, int* separator, int* segment_size ) {
  int** segments = malloc(part*sizeof(int*));
  for ( int i = 0; i < part; i++ ) {
    segments[i] = malloc(segment_size[i]*sizeof(int));
  }

  int* iter = segments[0];
  int* iter2 = segments[part-1];
  for ( int j = 0; j < size; j++ ) {
    if ( array[j] <= separator[0] ) { *iter++ = array[j]; }
    if ( array[j] > separator[part-2] ) { *iter2++ = array[j]; }
  }
  for ( int i = 1; i < part-1; i++ ) {
    iter = segments[i];
    for ( int j = 0; j < size; j++ ) 
      if ( array[j] <= separator[i] && array[j] > separator[i-1] ) 
        *iter++ = array[j];
  }
  return segments;
}

int main( int argc, char** argv ) {
  int array[10] = { 5,7,3,6,2,9,0,4,8,1 };
  print_array(array, 10);
  int* separator = get_separator(array, 10, 4);
  int* segment_size = get_segment_size(array, 10, 4, separator);
  int** segments = divide_array( array, 10, 4, separator, segment_size);

  for ( int i = 0; i < 4; i++ ) {
    print_array( segments[i], segment_size[i] );
  }
}