Selection Sort e Quick Sort

4 de julho de 2008 6 respostas

alebae 4 de julho de 2008

Olá, bom dia a todos.
Sou novo aqui no GUJ e também no Java.
Estou há quase 2 semanas tentando finalizar um código para trabalho acadêmico, assim sendo tenho 2 dúvidas quanto ao código que implementei, através de algoritmos de livros específicos. Bom vamos lá. A primeira é a comparação de String com um vetor int[]. Eu sei que é meio absurdo, mas nos algoritmos de Quick e Selection Sort eu precisava escolher um dos três atributos (String nome, int matricula, int curso) e ordernar por esses 2 métodos de classificação de dados. A matricula e curso por serem int eu consegui, porém o String nome, não consegue. Eu sei que é meio primário isso, mas to começando há pouco tempo no Java e na área de programação, já procurei em fóruns, e achei o equals (mas compara 2 Strings e eu só tenho 1) e o compareTo, que não me ajudaram. Existe outro método que poderia "amenizar o absurdo" da comparação int/string?

import java.io.*;
import java.util.*;
public class TabelaTrabalho {
    int[] matricula = {12345, 24567, 456789, 12345, 24567, 456789, 12345, 24567, 456789, 67890, 456783 };
    int[] curso = {1,2,3,4,5,6,7 ,8, 9, 10, 11};
    String[] nome = {"João", "Maria", "Fernando", "José", "Pedro", "Carlos", "Tiago", "Mário", "Carla", "Leandro", "Raul" };
    private int numElementos;
    private int tab[];

    public TabelaTrabalho(int numElementos, int[] tab) {
        this.numElementos = numElementos;
        this.tab = tab;
    }
    
    
    
    public void exibeTabela(){
        System.out.println("Tabela: ");
        for(int i=0; i < numElementos; i++)
            System.out.println(" " + tab[i]);
                    System.out.println();
    }
    
     
     public void SelectionSort(){
         //variáveis
         int chave[] = null;
         int endereco[] = null;
         int i,j,min,ch;
         for(i =0; i < numElementos; i++){
             min = i;
             for(j = i+1; j < numElementos; j++){
                 if(chave[j] < chave[min]){
                     min = j;
             ch = chave[i];
             chave[i] = chave[min];
             chave[min] = ch;
             matricula[i] = endereco[i];
             
             
             endereco[i] = endereco[min];
             endereco[min] = matricula[i];
             
             
             
                 }
             }
         }
         
         }
     
      public void SelectionSort2(){
         //variáveis
         int chave[] = null;
         int endereco[] = null;
         int i,j,min,ch;
         for(i =0; i < numElementos; i++){
             min = i;
             for(j = i+1; j < numElementos; j++){
                 if(chave[j] < chave[min]){
                     min = j;
             ch = chave[i];
             chave[i] = chave[min];
             chave[min] = ch;
             curso[i] = endereco[i];
             
             endereco[i] = endereco[min];
             
             endereco[min] = curso[i];
             
             
                 }
             }
         }
         
         }
       public void SelectionSort3(){
         //variáveis
         int chave[] = null;
         int endereco[] = null;
         int i,j,min,ch;
         for(i =0; i < numElementos; i++){
             min = i;
             for(j = i+1; j < numElementos; j++){
                 if(chave[j] < chave[min]){
                     min = j;
             ch = chave[i];
             chave[i] = chave[min];
             chave[min] = ch;
           //  nome[i] = endereco[i];
             
             endereco[i] = endereco[min];
             
             //endereco[min] = nome[i];
             
                 }
             }
         }
         
         }
     
     
     public void QuickSort(){
         sort(0, this.numElementos -1);
     }

    private void sort(int esquerda, int direita) {
       int posEsqAux;
       int posDirAux;
       int pivo;
       int vetor[] = null;
       
       posEsqAux = esquerda;
       posDirAux = direita;
       
       pivo = tab[(esquerda + direita)/2];
       
       while(posEsqAux <= posDirAux){
           while(tab[posEsqAux] < pivo){
               posEsqAux = posEsqAux + 1;
               while(tab[posDirAux] > pivo){
                   posDirAux = posDirAux + 1;
                   if(posEsqAux <= posDirAux){
                       vetor[posEsqAux] = tab[posEsqAux];
                       vetor[posEsqAux] = tab[posEsqAux];
                       vetor[posEsqAux] = tab[posEsqAux];
                       tab[posEsqAux] = tab[posDirAux];
                       tab[posDirAux] = vetor[posDirAux];
                       tab[posDirAux] = vetor[posDirAux];
                       tab[posDirAux] = vetor[posDirAux];
                       posEsqAux = posEsqAux + 1;
                       posDirAux = posDirAux - 1;
                   }
               }
               if(esquerda < direita){
                   sort(esquerda, posDirAux);
               }
               if(direita > posEsqAux){
                   sort(posEsqAux, direita);
               }
           }
       }
       
       
    }
     public void QuickSort2(){
         sort2(0, this.numElementos -1);
     }

    private void sort2(int esquerda, int direita) {
       int posEsqAux;
       int posDirAux;
       int pivo;
       int vetor[] = null;
       
       posEsqAux = esquerda;
       posDirAux = direita;
       
       pivo = tab[(esquerda + direita)/2];
       
       while(posEsqAux <= posDirAux){
           while(tab[posEsqAux] < pivo){
               posEsqAux = posEsqAux + 1;
               while(tab[posDirAux] > pivo){
                   posDirAux = posDirAux + 1;
                   if(posEsqAux <= posDirAux){
                       vetor[posEsqAux] = tab[posEsqAux];
                       vetor[posEsqAux] = tab[posEsqAux];
                       vetor[posEsqAux] = tab[posEsqAux];
                       tab[posEsqAux] = tab[posDirAux];
                       tab[posDirAux] = vetor[posDirAux];
                       tab[posDirAux] = vetor[posDirAux];
                       tab[posDirAux] = vetor[posDirAux];
                       posEsqAux = posEsqAux + 1;
                       posDirAux = posDirAux - 1;
                   }
               }
               if(esquerda < direita){
                   sort(esquerda, posDirAux);
               }
               if(direita > posEsqAux){
                   sort(posEsqAux, direita);
               }
           }
       }
       
       
    }
     public void QuickSort3(){
         sort3(0, this.numElementos -1);
     }

    private void sort3(int esquerda, int direita) {
       int posEsqAux;
       int posDirAux;
       int pivo;
       int vetor[] = null;
       
       posEsqAux = esquerda;
       posDirAux = direita;
       
       pivo = tab[(esquerda + direita)/2];
       
       while(posEsqAux <= posDirAux){
           while(tab[posEsqAux] < pivo){
               posEsqAux = posEsqAux + 1;
               while(tab[posDirAux] > pivo){
                   posDirAux = posDirAux + 1;
                   if(posEsqAux <= posDirAux){
                       vetor[posEsqAux] = tab[posEsqAux];
                       vetor[posEsqAux] = tab[posEsqAux];
                       vetor[posEsqAux] = tab[posEsqAux];
                       tab[posEsqAux] = tab[posDirAux];
                       tab[posDirAux] = vetor[posDirAux];
                       tab[posDirAux] = vetor[posDirAux];
                       tab[posDirAux] = vetor[posDirAux];
                       posEsqAux = posEsqAux + 1;
                       posDirAux = posDirAux - 1;
                   }
               }
               if(esquerda < direita){
                   sort(esquerda, posDirAux);
               }
               if(direita > posEsqAux){
                   sort(posEsqAux, direita);
               }
           }
       }
       
       
    }
     }

6 Respostas

ViniGodoy 4 de jul. de 2008

As strings implementam a interface comparable. O método compareTo da classe String retorna >0 se a string for maior que a recebida no parâmetro, <0 se for menor e 0 se forem iguais. Use esse método:

int compare = str1.compareTo(str2); if (compare > 0) { //str1 > str2? //blablabla } else if (compare < 0) { //str1 < str2 ? //blablabla } else { //str1 == str2 //blablabla }

ViniGodoy 4 de jul. de 2008

Me diga uma coisa... pq esses comandos parecem 3 vezes? Bastaria uma vez só:

vetor[posEsqAux] = tab[posEsqAux];  
vetor[posEsqAux] = tab[posEsqAux];  
vetor[posEsqAux] = tab[posEsqAux];  

tab[posDirAux] = vetor[posDirAux];  
tab[posDirAux] = vetor[posDirAux];  
tab[posDirAux] = vetor[posDirAux]

alebae 4 de jul. de 2008

Bom, foi falha minha, estava fazendo um testes e eu tripliquei a função, mas já corrigido.

Eu estou meio que me batendo com o compareTo. Eu teria somente 1 vetor de string (String[] nome), não saberia como comparar com outra String. Meu professor já tinha dito isso, mas não consegui entender direito essa questão.

Obrigado pela ajuda!

ViniGodoy 4 de jul. de 2008

Você vai ter que usar o compareTo mais ou menos assim:

nome[esquerda].compareTo(nome[direita]) > 0

alebae 6 de jul. de 2008

Muito obrigado ViniGodoy. Deu certinho!
Valeu, Abraço

alebae 7 de jul. de 2008

Olá, outro probleminha. Meu programinha tá entrando em looping, como resolver?

import java.util.Scanner;
import java.io.*;
public class Principal {
    public static void main(String args[]){
        int escolha=0;
        TabelaTrabalho tab = new TabelaTrabalho();
        Scanner sc = new Scanner(System.in);
        while (true){
	    System.out.println("ESCOLHA O ATRIBUTO A SER AVALIADO: ");
            System.out.println("1 - Nome;");   
            System.out.println("2 - MatrÃcula;");
            System.out.println("3 - Curso;");
            System.out.println("4 - Sair.");
            sc.nextInt();
            
            switch(escolha){
                case 1: 
                    Scanner atributoNome = new Scanner(System.in);
                    System.out.println("Por Quick Sort: \n");
                    tab.QuickSort();
                    System.out.println("Por Selection Sort: \n");
                    tab.SelectionSort();
                case 2:
                    Scanner atributoMatricula = new Scanner(System.in);
                    System.out.println("Por Quick Sort: \n");
                    tab.QuickSort2();
                    System.out.println("Por Selection Sort: \n");
                    tab.SelectionSort2();
                case 3:
                    Scanner atributoCurso = new Scanner(System.in);
                    System.out.println("Por Quick Sort: \n");
                    tab.QuickSort3();
                    System.out.println("Por Selection Sort: \n");
                    tab.SelectionSort3();
                case 4:
                    System.exit(0);
            }
    }
}
    public Aluno[] insereAlunos(){
        Aluno[] aluno = new Aluno[10];
                aluno[0] = new Aluno("Carlos", 12141, 47346);
		aluno[1] = new Aluno("Paulo", 64641, 454646);
		aluno[2] = new Aluno("MÃ¡rcia", 654751, 9988986);
		aluno[3] = new Aluno("Rubens", 1981, 877777);
		aluno[4] = new Aluno("JoÃ£o", 8787878, 6445456);
		aluno[5] = new Aluno("Tiago", 878781, 34436);
		aluno[6] = new Aluno("Mauro", 5331, 434346);
		aluno[8] = new Aluno("Paulinha", 34343441, 432346);
		aluno[7] = new Aluno("JosÃ©", 12878741, 478787846);
		aluno[9] = new Aluno("Cida", 534341, 4343546);
         return aluno;
    }
 }

import java.io.*;
import java.util.*;
public class TabelaTrabalho {
    private int numElementos;
    private Aluno tab[];

   TabelaTrabalho() {
        this.numElementos = numElementos;
        this.tab = tab;
    }

    public void exibeTabela(){
        System.out.println("Tabela: ");
        for(int i=0; i < numElementos; i++)
            System.out.println(" " + tab[i]);
                    System.out.println();
    }
    
    public void SelectionSort(){
         //variÃ¡veis
         int[] vetor = null;
         for(int i=0; i > numElementos - 1; i++){
             int min =i;
             
         for(int j=i+1; j < numElementos; j++){
                 if(vetor[j] < vetor[min]){
                     min=j;
                 }
                 
         tab[j].getNome().compareTo(tab[i].getNome());
         vetor[i] = vetor[min];
         tab[min].getNome().compareTo(tab[i].getNome());
             }
             
         }
         
         }
     
      public void SelectionSort2(){
         //variÃ¡veis
         
         for(int i=0; i > numElementos - 1; i++){
             int min =i;
             
         for(int j=i+1; j < numElementos; j++){
                 if(tab[j].getMatricula() < tab[min].getMatricula()){
                     min=j;
                 }
             
         if(tab[i].getMatricula() == tab[j].getMatricula()){
             tab[i] = tab[min];
             if(tab[min].getMatricula()==tab[i].getMatricula()){
                 System.out.println(tab[min]);
             }
             
         }
        
             }
             
         }
         
         }
        public void SelectionSort3(){
         //variÃ¡veis
         
         for(int i=0; i > numElementos - 1; i++){
             int min =i;
             
         for(int j=i+1; j < numElementos; j++){
                 if(tab[j].getMatricula() < tab[min].getMatricula()){
                     min=j;
                 }
             
         if(tab[i].getCurso() == tab[j].getCurso()){
             tab[i] = tab[min];
             if(tab[min].getCurso()==tab[i].getCurso()){
                 System.out.println(tab[min]);
             }
             
         }
        
             }
             
         }
         
         }
     
     
     public void QuickSort(){
         sort(0, this.numElementos -1);
     }

    private void sort(int esquerda, int direita) {
       int vetor[] = null;
       int pivo;
       int posEsqAux;
       int posDirAux;
       
       posEsqAux = esquerda;
       posDirAux = direita;
       
       pivo = vetor[(esquerda + direita)/2];
       
       while(posEsqAux <= posDirAux){
           while(vetor[posEsqAux] < pivo){
               posEsqAux = posEsqAux + 1;
           while(vetor[posDirAux] > pivo){
               posDirAux = posDirAux + 1;
               
           if(posEsqAux <= posDirAux){
               tab[posDirAux].getNome().compareTo(tab[posEsqAux].getNome());
               tab[posEsqAux] = tab[posDirAux];
               tab[posEsqAux].getNome().compareTo(tab[posDirAux].getNome());
               posEsqAux = posEsqAux +1;
               posDirAux = posDirAux -1;
           }
           }
           }
           if(esquerda < posDirAux){
               sort(esquerda, posDirAux);
           }
           if(direita > posEsqAux){
               sort(posEsqAux, direita);
           }
           
       }
       
       
    }
        public void QuickSort2(){
         sort2(0, this.numElementos -1);
     }

    private void sort2(int esquerda, int direita) {
       int vetor[]=null;
       int pivo;
       int posEsqAux;
       int posDirAux;
       
       posEsqAux = esquerda;
       posDirAux = direita;
       
       pivo = vetor[(esquerda + direita)/2];
       
       while(posEsqAux <= posDirAux){
           while(vetor[posEsqAux] < pivo){
               posEsqAux = posEsqAux + 1;
           while(vetor[posDirAux] > pivo){
               posDirAux = posDirAux + 1;
               
           if(posEsqAux <= posDirAux){
               if(tab[posDirAux].getMatricula() == tab[posEsqAux].getMatricula())
               tab[posEsqAux] = tab[posDirAux];
               if(tab[posEsqAux].getMatricula() == tab[posDirAux].getMatricula())
               posEsqAux = posEsqAux +1;
               posDirAux = posDirAux -1;
           }
           }
           }
           if(esquerda < posDirAux){
               sort(esquerda, posDirAux);
           }
           if(direita > posEsqAux){
               sort(posEsqAux, direita);
           }
           
       }
       
       
    }
    
    
     
 public void QuickSort3(){
         sort3(0, this.numElementos -1);
     }

    private void sort3(int esquerda, int direita) {
       int vetor[]=null;
       int pivo;
       int posEsqAux;
       int posDirAux;
       
       posEsqAux = esquerda;
       posDirAux = direita;
       
       pivo = vetor[(esquerda + direita)/2];
       
       while(posEsqAux <= posDirAux){
           while(vetor[posEsqAux] < pivo){
               posEsqAux = posEsqAux + 1;
           while(vetor[posDirAux] > pivo){
               posDirAux = posDirAux + 1;
               
           if(posEsqAux <= posDirAux){
               if(tab[posDirAux].getCurso() == tab[posEsqAux].getCurso())
               tab[posEsqAux] = tab[posDirAux];
               if(tab[posEsqAux].getCurso() == tab[posDirAux].getCurso())
               posEsqAux = posEsqAux +1;
               posDirAux = posDirAux -1;
           }
           }
           }
           if(esquerda < posDirAux){
               sort(esquerda, posDirAux);
           }
           if(direita > posEsqAux){
               sort(posEsqAux, direita);
           }
           
       }
       
       
    }

}

Criado 4 de julho de 2008

Ultima resposta 7 de jul. de 2008

Respostas 6

Participantes 2

6 Respostas

Topicos relacionados