<Codesignal> Sort by Height

Easy

Some people are standing in a row in a park. There are trees between them which cannot be moved. Your task is to rearrange the people by their heights in a non-descending order without moving the trees. People can be very tall!

Example

For a = [-1, 150, 190, 170, -1, -1, 160, 180], the output should be
sortByHeight(a) = [-1, 150, 160, 170, -1, -1, 180, 190].

Input/Output

• [execution time limit] 0.5 seconds (c)

• [input] array.integer a

  If a[i] = -1, then the ith position is occupied by a tree. Otherwise a[i] is the height of a person standing in the ith position.

  Guaranteed constraints:
  1 ≤ a.length ≤ 1000,
  -1 ≤ a[i] ≤ 1000.

• [output] array.integer

  • Sorted array a with all the trees untouched.

[C] Syntax Tips

// Prints help message to the console
// Returns a string
char * helloWorld(char * name) {
    char * answer = malloc(strlen(name) + 8);
    printf("This prints to the console when you Run Tests");
    strcpy(answer, "Hello, ");
    strcat(answer, name);
    return answer;
}

---

Solution

// Arrays are already defined with this interface:
// typedef struct arr_##name {
//   int size;
//   type *arr;
// } arr_##name;
//
// arr_##name alloc_arr_##name(int len) {
//   arr_##name a = {len, len > 0 ? malloc(sizeof(type) * len) : NULL};
//   return a;
// }
//
//
arr_integer sortByHeight(arr_integer a)
{
	int count=0;
	arr_integer b;

	for(int i=0;i<a.size;i++)
		count+=a.arr[i]!=-1;
	b=alloc_arr_integer(count);

	for(int i=0;i<a.size;i++)
		if(a.arr[i]!=-1)
			b.arr[--count]=a.arr[i];

	for(int i=0;i<b.size-1;i++)
		for(int j=i+1;j<b.size;j++)
			if(b.arr[i]>b.arr[j])
			{
				int temp=b.arr[i];
				b.arr[i]=b.arr[j];
				b.arr[j]=temp;
			}

	for(int i=0;i<a.size;i++)
		if(a.arr[i]!=-1)
			a.arr[i]=b.arr[count++];

	return a;
}