The answer would be actually much simpler if the collapse produced a black hole. It can be easily shown to have entropy vastly exceeding the entropy of any gas of the same mass.
Concerning your main question, the answer is, of course, that any system with many degrees of freedom - both in classical physics as well as quantum physics - always satisfies the second law of thermodynamics. The second law may always be proved - quite generally. The proofs are the proofs of the H-theorem or its generalization for any physical system you consider.
Just think about the "balls" in the phase space - any phase space - how it gets deformed via the time evolution. The "smoothened" version of this evolved "spaghetti" has a higher volume whose logarithm represents the entropy increase.
If you didn't allow the molecules to emit photons when they collide, they wouldn't ever shrink spontaneously by obeying the laws of gravity. The probability that a molecule slows down (or gets closer) under the gravitational influence of the other molecules would be equal to the probability that it speeds up (or gets further) - in average. If you introduce some objects and terms in the Hamiltonian that allow inelastic collisions, these inelastic collisions will selectively slow down the molecules that happened to be closer to each other, which is the mechanism that will be reducing the average distance between the molecules (the actual rate will depend on the gravitational attraction, too).
I wrote photons because, obviously, the probability of the emission of a photon is much higher for real-world gases because most of their interactions are electromagnetic interactions. Because a photon carries as much entropy as a graviton would, but you produce many more photons by random collisions, the entropy increase is stored in the photons. The entropy carried by gravitons is smaller by dozens of orders of magnitude.