Como criar um método de ordenação QuickSort para ordenar um vetor de objetos

gustavo_scarpim · Março 13, 2019, 4:29am

Tenho uma dúvida de como faço para ordenar um vetor de objeto utilizando o método QuickSort. Esse é o método QuickSort utilizado para organizar um vetor do tipo Double

public boolean quickSort(double[] vetor, int inicio, int fim) {
	if (vetor == null) return false;
	
	if (inicio < fim) {
		int posicaoPivo = separar(vetor, inicio, fim);
		System.out.println("Parcial"); visualizar(vetor);
		quickSort(vetor, inicio, posicaoPivo - 1);
		quickSort(vetor, posicaoPivo + 1, fim);
	}
	
	return true;
}

private int separar(double[] vetor, int inicio, int fim) {
	double pivo = vetor[inicio];
	int i = inicio + 1, f = fim;
	
	while(i <= f) {
		if(vetor[i] <= pivo)
			i++;
		else if (pivo < vetor[f])
			f--;
		else {
			double troca = vetor[i];
			vetor[i] = vetor[f];
			vetor[f] = troca;
			i++;
			f--;
		}
	}
	
	vetor[inicio] = vetor[f];
	vetor[f] = pivo;
	return f;
}

darlan_machado · Março 13, 2019, 1:55pm

Você vai criar da mesma maneira. Porém, terá de definir qual será o critério de comparação para ordenação, qual será o atributo do objeto que determinará qual é o “maior” e qual o “menor”.

gustavo_scarpim · Março 13, 2019, 7:51pm

Tem como dar um help, não estou conseguindo ordenar por ordem crescente o salário separado e o nome de cada pessoa por ordem alfabética, tem como você me dar um exemplo explicando como eu conseguiria fazer isso? Obrigado, tentei achar no Google, porém não encontrei nada que me ajude a fazer isso.

Ps. O método QuickSort e o Separar está em baixo desse sem alterações:

public class Nomes{

private Pessoas pes[];
private int N;

public static void main(String[] args) {

    Nomes principal = new Nomes();

}

public Nomes() {
    simulacaoLeituraDeDados();
    mostraPessoasCadastrados();
}

public void simulacaoLeituraDeDados() {
    N = 7; 
    pes = new Pessoas[N];
    pes[0] = new Pessoas("Matheus", 2000f, 'M');
    pes[1] = new Pessoas("Darlan", 1000, 'F');
    pes[2] = new Pessoas("Fernanda", 800, 'F');
    pes[3] = new Pessoas("Jair", 1500f, 'M');
    pes[4] = new Pessoas("Aldair", 6000f, 'M');
}

public void leituraDeDados() {
    String umNome;
    float umSalario;
    char umSexo;
    N = Integer.parseInt(JOptionPane.showInputDialog("Digite a quantidade de Pessoas:"));
    pes = new Pessoas[N];   
    for (int i = 0; i < N; i++) {
        umNome = JOptionPane.showInputDialog("Digite o nome da Pessoa" + (i + 1) + ": ");
        umSalario = Float.parseFloat(JOptionPane.showInputDialog("Digite o salário de " + umNome + ": "));
        umSexo = JOptionPane.showInputDialog("Digite o sexo desta Pessoa: ").charAt(0);
        umSexo = Character.toUpperCase(umSexo);
        pes[i] = new Pessoas(umNome, umSalario, umSexo); 
    }
}

public void mostraPessoasCadastrados() {
    String cad = "";
    for (int i = 0; i < N; i++) {
        cad += pes[i].toString() + "\n";
    }
    JTextArea outputArea = new JTextArea(15, 40);  //15 linhas e 40 colunas
    outputArea.setText(cad);
    JScrollPane rolagem = new JScrollPane(outputArea);
    JOptionPane.showMessageDialog(null, rolagem, "Dados das Pessoas cadastrados",
            JOptionPane.INFORMATION_MESSAGE);
}

darlan_machado · Março 13, 2019, 7:54pm

Antes de mais nada, queria dizer que este trecho do código deveria me fazer não ajudar…

Provavelmente você vai precisar implementar a interface Comparator e criar um comparador que considere os dois atributos ao mesmo tempo.

gustavo_scarpim · Março 14, 2019, 3:50am

Consegui fazer a ordenação de forma Crescente e Decrescente do salário, o que eu não estou conseguindo fazer é como inserir um CompareTo no método de ordenação QuickSort, consegui fazer no BoobleSort e no InsertionSort, porém não consigo no QuickSort, você poderia me dar um exemplo de como fazer isso? Desde já eu agradeço por tudo.
Ps. Ao invés do getSalario(), quero mudar para getNome(), mas sei que precisa mudar algo para poder ordena-lo, mas não sei como.

private int separar(Trabalhador[] vetor, int inicio, int fim) { 
        Trabalhador pivo = vetor[inicio];
        int i = inicio + 1, f = fim;
        while (i <= f) {
            if (vetor[i].getSalario() >= pivo.getSalario())  {
                i++;
            } else if (pivo.getSalario() > vetor[f].getSalario()) {
                f--;
            } else {
                Trabalhador troca = vetor[i];
                vetor[f] = vetor[i];
                vetor[i] = troca;
                i++;
                f--;
            }
        }
        vetor[inicio] = vetor[f]; 
        vetor[f] = pivo; 
        return f;
    }
}

darlan_machado · Março 14, 2019, 11:46am

Não é no método, é na classe que será comparada, cara.

staroski · Março 15, 2019, 1:34pm

import java.util.Comparator;

public class QuickSort<T> {

    public boolean quickSort(T[] vetor, Comparator<T> comparador) {
        if (vetor == null || comparador == null) {
            return false;
        }
        int inicio = 0;
        int fim = vetor.length - 1;
        return quickSort(vetor, comparador, inicio, fim);
    }

    private boolean quickSort(T[] vetor, Comparator<T> comparador, int inicio, int fim) {
        if (inicio < fim) {
            int posicaoPivo = separar(vetor, comparador, inicio, fim);
            quickSort(vetor, comparador, inicio, posicaoPivo - 1);
            quickSort(vetor, comparador, posicaoPivo + 1, fim);
        }

        return true;
    }

    private int separar(T[] vetor, Comparator<T> comparador, int inicio, int fim) {
        T pivo = vetor[inicio];
        int i = inicio + 1, f = fim;

        while (i <= f) {
            if (comparador.compare(vetor[i], pivo) <= 0) {
                i++;
            } else if (comparador.compare(pivo, vetor[f]) < 0) {
                f--;
            } else {
                T troca = vetor[i];
                vetor[i] = vetor[f];
                vetor[f] = troca;
                i++;
                f--;
            }
        }

        vetor[inicio] = vetor[f];
        vetor[f] = pivo;
        return f;
    }
}

Exemplo:

import java.util.Comparator;

public class Exemplo {

    public static void main(String[] args) {
        Exemplo programa = new Exemplo();
        programa.executar();
    }

    private void executar() {
        Pessoa[] pessoas = new Pessoa[5];
        pessoas[0] = new Pessoa("Matheus", 2000f, 'M');
        pessoas[1] = new Pessoa("Darlan", 1000, 'M');
        pessoas[2] = new Pessoa("Fernanda", 800, 'F');
        pessoas[3] = new Pessoa("Jair", 1500f, 'M');
        pessoas[4] = new Pessoa("Aldair", 6000f, 'M');
        visualizar(pessoas);

        QuickSort<Pessoa> algoritmo = new QuickSort<>();

        Comparator<Pessoa> comparadorNome = (pessoa1, pessoa2) -> pessoa1.getNome().compareTo(pessoa2.getNome());
        algoritmo.quickSort(pessoas, comparadorNome);
        visualizar(pessoas);

        Comparator<Pessoa> comparadorSalario = (pessoa1, pessoa2) -> Double.compare(pessoa1.getSalario(), pessoa2.getSalario());
        algoritmo.quickSort(pessoas, comparadorSalario);
        visualizar(pessoas);

        Comparator<Pessoa> comparadorSexo = (pessoa1, pessoa2) -> Character.compare(pessoa1.getSexo(), pessoa2.getSexo());
        algoritmo.quickSort(pessoas, comparadorSexo);
        visualizar(pessoas);
    }

    private void visualizar(Pessoa[] pessoas) {
        for (Pessoa pessoa : pessoas) {
            System.out.printf("%s    %f    %s%n", pessoa.getNome(), pessoa.getSalario(), pessoa.getSexo());
        }
        System.out.println();
    }
}

gustavo_scarpim · Março 15, 2019, 3:02pm

Não estou conseguindo chamar o método quickSort no meu public OrdenacaoString() , teria como me mostrar como que eu faço isso? Desde já eu agradeço por tudo!

package NomeString;

import java.util.Comparator;
import javax.swing.JOptionPane;
import javax.swing.JScrollPane;
import javax.swing.JTextArea;

public class OrdenacaoString {Texto pré-formatado
private Trabalhador trab[];//vetor trabalhador
private int N;

public static void main(String[] args) {

    OrdenacaoString principal = new OrdenacaoString();//objeto criado 
    
}

public OrdenacaoString() {
    simulacaoLeituraDeDados();
    quickSort(trab, 0, trab.length - 1);<- Não estou conseguindo chamar esse método quickSort para fazer a ordenação em ordem alfabética, teria como me mostrar pfv.
    mostraTrabalhadoresCadastrados();
}

public void simulacaoLeituraDeDados() {
    N = 7;
    trab = new Trabalhador[N];
    trab[0] = new Trabalhador("Julio", 2000f, 'M');
    trab[1] = new Trabalhador("Vitória", 1000, 'F');
    trab[2] = new Trabalhador("Renata", 800, 'F');
    trab[3] = new Trabalhador("Pedro", 1500f, 'M');
    trab[4] = new Trabalhador("Amilton", 6000f, 'M');
    trab[5] = new Trabalhador("Jorge", 2200f, 'M');
    trab[6] = new Trabalhador("Carlos", 3500f, 'M');
    visualizar(trab);
    
    OrdenacaoString<Trabalhador> algoritmo = new OrdenacaoString<>();

    Comparator<Trabalhador> comparadorNome = (trab1, trab2) -> trab1.getNome().compareTo(trab2.getNome());
    algoritmo.quickSort(trab, comparadorNome);
    visualizar(trab);

    Comparator<Trabalhador> comparadorSalario = (trab1, trab2) -> Double.compare(trab1.getSalario(), trab2.getSalario());
    algoritmo.quickSort(trab, comparadorSalario);
    visualizar(trab);

    Comparator<Trabalhador> comparadorSexo = (trab1, trab2) -> Character.compare(trab1.getSexo(), trab2.getSexo());
    algoritmo.quickSort(trab, comparadorSexo);
    visualizar(trab);
}

public void mostraTrabalhadoresCadastrados() {
    String cad = "";
    for (int i = 0; i < N; i++) {
        cad += trab[i].toString() + "\n";
    }
    JTextArea outputArea = new JTextArea(15, 40);  //15 linhas e 40 colunas
    outputArea.setText(cad);//JTextArea outputArea serve para criar um espaço para mostrar as informações
    JScrollPane rolagem = new JScrollPane(outputArea);//Fornece uma visão de rolagem. 
    JOptionPane.showMessageDialog(null, rolagem, "Dados dos trabalhadores cadastrados",
            JOptionPane.INFORMATION_MESSAGE);
}

  public boolean quickSort(T[] vetor, Comparator<T> comparador) {
        if (vetor == null || comparador == null) {
            return false;
        }
        int inicio = 0;
        int fim = vetor.length - 1;
        return quickSort(vetor, comparador, inicio, fim);
    }
    private boolean quickSort(T[] vetor, Comparator<T> comparador, int inicio, int fim) {
        if (inicio < fim) {
            int posicaoPivo = separar(vetor, comparador, inicio, fim);
            quickSort(vetor, comparador, inicio, posicaoPivo - 1);
            quickSort(vetor, comparador, posicaoPivo + 1, fim);
        }

        return true;
    }

private int separar(T[] vetor, Comparator<T> comparador, int inicio, int fim) {  
T pivo = vetor[inicio];
    int i = inicio + 1, f = fim;
    while (i <= f) {
        if (comparador.compare(vetor[i], pivo) <= 0) {
            i++;
        } else if (comparador.compare(pivo, vetor[f]) < 0) {
            f--;
        } else {
            T troca = vetor[i];
            vetor[i] = vetor[f];
            vetor[f] = troca;
            i++;
            f--;
        }
    }
    vetor[inicio] = vetor[f];
    vetor[f] = pivo;
    return f;
}
private void visualizar(Trabalhador[] trab) {
    for (Trabalhador pessoa : trab) {
        System.out.printf("%s    %f    %s%n", pessoa.getNome(), pessoa.getSalario(), pessoa.getSexo());
    }
    System.out.println();
}

}

staroski · Março 15, 2019, 4:13pm

Esse método é private, não é pra ser chamado a partir de outra classe.

A ordenação alfabética está sendo feita dentro do seu método simulacaoLeituraDeDados, mais precisamente nestas linhas:

Comparator<Trabalhador> comparadorNome = (trab1, trab2) -> trab1.getNome().compareTo(trab2.getNome()); // aqui você tem um comparador de nomes
algoritmo.quickSort(trab, comparadorNome); // aqui você está chamando o método quickSort

gustavo_scarpim · Março 15, 2019, 4:18pm

Mesmo chamando ele ali, os nomes não estão ficando em ordem alfabética quando executo o programa, fica num laço enorme até chegar num erro.
Sabe me informar o que devo fazer?
Está me dando os valores assim:
Julio 2000,000000 M
Vitória 1000,000000 F
Renata 800,000000 F
Pedro 1500,000000 M
Amilton 6000,000000 M
Jorge 2200,000000 M
Carlos 3500,000000 M

staroski · Março 15, 2019, 4:59pm

Primeiramente o código que você postou está com erros de compilação, então nem dá pra executar ele.

Após arrumar os erros de compilação, realmente acontece um laço enorme seguido de um estouro de pilha, o erro acontece pelo seguinte motivo:

No método main você chama o contrutor da classe OrdenacaoString;