Primeira Implementação: Partição Básica

Dada uma matriz, ordená-la de forma que todos os elementos menores que o último elemento fiquem à sua esquerda, e todos os elementos maiores fiquem à sua direita. Os elementos nas partições esquerda e direita não precisam estar ordenados internamente.

Exemplo: Para a matriz [5, 6, 3, 1, 2, 3], após a ordenação obtemos [3, 1, 2, 3, 5, 6]. O último elemento original era 3, e agora todos os elementos menores ou iguais a 3 estão à esquerda, enquanto os maiores estão à direita.

Lógica de resolução:

1. Definimos uma região de elementos menores que o alvo, começando antes do primeiro elemento (índice -1), chamada de limiteMenor.
2. Criamos um ponteiro móvel, inicialmente apontando para o primeiro elemento, chamado de indiceAtual.
3. Percorremos a matriz: enquento o indiceAtual for menor que o tamanho da matriz, comparamos o elemento atual com o último elemento. Se for menor ou igual, trocamos com o próximo elemento após limiteMenor e incrementamos ambos. Caso contrário, apenas avançamos o indiceAtual.

Código de implementação:

```

private void exibirMatriz(int[] matriz) {
    for (int elemento : matriz) {
        System.err.print(elemento + " ");
    }
}

private void trocarElementos(int[] matriz, int posA, int posB) {
    int temporario = matriz[posA];
    matriz[posA] = matriz[posB];
    matriz[posB] = temporario;
}

public void ordenacaoRapidaBasica(int[] matriz) {
    int limiteMenor = -1;
    int indiceAtual = 0;
    int ultimoElemento = matriz.length - 1;
    
    while (indiceAtual <= ultimoElemento) {
        if (matriz[indiceAtual] <= matriz[ultimoElemento]) {
            limiteMenor++;
            trocarElementos(matriz, limiteMenor, indiceAtual);
            indiceAtual++;
        } else {
            indiceAtual++;
        }
    }
}

@Test
public void testeOrdenacaoBasica() {
    int[] matriz = {5, 6, 3, 1, 2, 3};
    ordenacaoRapidaBasica(matriz);
    exibirMatriz(matriz);
}

    

#### Segunda Implementação: Partição Tríplice

Nesta versão, além de separar elementos menores e maiores que o pivô, também agrupamos os elementos iguais ao pivô no centro.

Exemplo: Para a matriz \[5, 6, 3, 1, 2, 3\], após a ordenação obtemos \[1, 2, 3, 3, 5, 6\]. Todos os elementos menores que 3 estão à esquerda, os maiores à direita, e os iguais ao centro.

**Lógica de resolução:**

1. Mantemos a região de elementos menores (limiteMenor).
2. Adicionamos uma região de elementos maiores (limiteMaior), inicialmente apontando para o último elemento.
3. No loop, se o elemento atual for menor que o pivô, trocamos com o próximo após limiteMenor. Se for maior, trocamos com o elemento anterior ao limiteMaior e decrementamos limiteMaior. Se for igual, apenas avançamos.
 
**Código de implementação:**

 
    ```

    public void ordenacaoRapidaTríplice(int[] matriz) {
        int limiteMenor = -1;
        int indiceAtual = 0;
        int limiteMaior = matriz.length - 1;
        
        while (indiceAtual <= limiteMaior) {
            if (matriz[indiceAtual] < matriz[matriz.length - 1]) {
                limiteMenor++;
                trocarElementos(matriz, limiteMenor, indiceAtual);
                indiceAtual++;
            } else if (matriz[indiceAtual] > matriz[matriz.length - 1]) {
                limiteMaior--;
                trocarElementos(matriz, limiteMaior, indiceAtual);
            } else {
                indiceAtual++;
            }
        }
        trocarElementos(matriz, limiteMaior, matriz.length - 1);
    }

    @Test
    public void testeOrdenacaoTríplice() {
        int[] matriz = {5, 6, 3, 1, 2, 3};
        ordenacaoRapidaTríplice(matriz);
        exibirMatriz(matriz);
    }
    

Terceira Implementação: Ordenação Completa Recursiva

Esta versão estende a partição tríplice para ordenar completamente a matriz através da recursão aplicada às partições esquerda e direita.

Lógica de resolução:

1. Aplicamos a partição tríplice para posicionar corretamente o pivô.
2. Recursivamente aplicamos o mesmo processo à partição esquerda (elemantos menores que o pivô).
3. Recursivamente aplicamos o mesmo processo à partição direita (elementos maiores que o pivô).

Código de implementação:

```

public int[] particionarMatriz(int[] matriz, int inicio, int fim) {
    int indiceAtual = inicio;
    int limiteMaior = fim;
    
    while (indiceAtual < limiteMaior) {
        if (matriz[indiceAtual] < matriz[fim]) {
            trocarElementos(matriz, inicio, indiceAtual);
            inicio++;
            indiceAtual++;
        } else if (matriz[indiceAtual] > matriz[fim]) {
            limiteMaior--;
            trocarElementos(matriz, limiteMaior, indiceAtual);
        } else {
            indiceAtual++;
        }
    }
    trocarElementos(matriz, limiteMaior, fim);
    return new int[]{inicio, limiteMaior};
}

public void ordenacaoRapidaCompleta(int[] matriz, int limiteEsquerdo, int limiteDireito) {
    if (matriz == null || matriz.length < 2) {
        return;
    }
    if (limiteEsquerdo >= limiteDireito) {
        return;
    }
    
    int[] indices = particionarMatriz(matriz, limiteEsquerdo, limiteDireito);
    ordenacaoRapidaCompleta(matriz, limiteEsquerdo, indices[0] - 1);
    ordenacaoRapidaCompleta(matriz, indices[1] + 1, limiteDireito);
}

@Test
public void testeOrdenacaoCompleta() {
    int[] matriz = {5, 6, 3, 1, 2, 3};
    ordenacaoRapidaCompleta(matriz, 0, matriz.length - 1);
    exibirMatriz(matriz);
}

    

</div></div>