I think what you’re to do is grouping by category which Connections does not currently support.
The only option would be to use the shortcode on the same page, once for each category. The problem with that is each instance of the shortcode will be affected by the search which would give “weird” end user experience.
Sorry, but I can not think of a way to do what you want. The only recommendation I would make is to remove search completely.