Lista3 // Quicksort

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

using namespace std;

void quicksort(int ordem[], int left, int right);

int main() {
    int contador, tempo, tam, um;
    tempo = 0;
    contador = 0;

    scanf("%d", &contador);

    while (tempo < contador) {
        um = 0;
        bool b = false;
        if ((tempo > 0) && (tempo < contador)) {
            printf("\n");
        }
        scanf("%d", &tam);
        int ordem [tam];
        for (int i = 0; i < tam; i++) {
                 scanf("%d", &ordem[i]);
             }

        quicksort(ordem, 0,(tam - 1) );

             if (ordem[tam - 1] <= 3) {
                 for (int z = 0; z < tam; z++) {
                     if (z == 0) {
                         printf("%d",ordem[z]);
                     }
                     else {
                         printf(" %d", ordem[z]);
                     }
                 }
             }
             else {
                 for (int z = 0; z < tam; z++) {
                     if (ordem[z] == 1) {
                         printf("%d ", ordem[z]);
                         b = true;
                     }
                     else {
                         um = z;
                         z = tam;
                     }
                 }
                 if (b) {
                     for (int z = tam - 1; z >= um; z--) {
                       if (z == um) {
                         printf("%d", ordem[z]);
                       }
                       else {
                         printf("%d ", ordem[z]);
                       }
                     }

                 }
                 else {
                     for (int z = tam - 1; z >= 0; z--) {
                       if (z == 0) {
                         printf("%d", ordem[z]);
                       }
                       else {
                         printf("%d ", ordem[z]);
                       }
                     }
                 }

             }
             tempo++;
    }

    return 0;

}

void quicksort (int ordem[], int left, int right) {
    int m = left;
    int n = right;
    int pivot = (ordem[(left + right)/2]);
    int temp;

    //caso base
    while (m <= n) {

            while (ordem[m] < pivot) {
                m++;
            }

            while (ordem[n] > pivot) {
                n--;
            }
            //particao
            //caso base
            if (m <= n) {
                temp = ordem[m];
                ordem[m] = ordem[n];
                ordem[n] = temp;
                m++;
                n--;
            }
        }

        //recursao
        if (left < n) {
            quicksort(ordem, left, n);
        }

        if (m < right) {
            quicksort(ordem, m, right);
        }
}