Problem summary

Given list of heights of boxes, show the final configuration after the gravity change.

Approach method

Let position $b_x$ be the normal horizontal axis position of the box and $b_y$ be the height of the box. Now realize that each box $b$ at height $b_y$ is going to stay at $b_y$ after the gravity change. It may change $b_x$ or it may not, but the $b_y$ is never going to change.

If one is not convinced, try simulating it in real life, placing boxes inside of one huge box then tilting it such that all the boxes move that the same time.

The tallest set of boxes will be at the final position, because the box at the tallest height will stay at the tallest height. The height will not change.

The second tallest height will be exactly one on the left of the tallest position.

This continues for all set of boxes. The set of boxes with the smallest height will be at the edge of the queue, just like the tallest one (at the other edge).

It is almost like we’ve just sorted the height of the set of boxes themselves, and it is.

This is a sorting problem.

Constraints

$1 \leq n \leq 100$, where $n$ is the number of the set of boxes.
For each set of boxes, there is the height of the set of box, noted by $a_i$. $1 \leq a_i \leq 100$.

Solution

Solution 1 - Insertion sort

Insertion sort on Wikipedia

Implementation in C:

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

void insert_sort(int *s, int a_sz) {
for (int i = 0; i < a_sz; ++i) {
int j = i;
while (j > 0 && s[j] < s[j-1]) {
int t = s[j];
s[j] = s[j-1];
s[j-1] = t;
j--;
}
}
}

int main() {
int size;
scanf("%d", &size);

int *s = (int *) malloc(sizeof(*s) * size);

for (int i = 0; i < size; ++i) {
int q;
scanf("%d", &q);

s[i] = q;
}

insert_sort(s, size);

for (int x = 0; x < size; ++x) {
printf("%d", s[x]);
if (x != size-1) {
printf(" ");
}
}

return 0;
}

Time complexity: $O(n^2)$ worst case, but since n is relatively small, it is doable.

Solution 2 - std::sort

std::sort on C++ reference

Implementation in C++:

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);

int n;
std::cin >> n;

std::vector<int> h;
while (n--) {
int height;
std::cin >> height;
h.push_back(height);
}

std::sort(h.begin(), h.end());

for (const auto &height: h) {
std::cout << height << " ";
}
return 0;
}


Time complexity: $O(n\cdot\log(n))$