Sobre o Quicksort

[nipo_style]

Eu procurei no google, aki no guj, e em vários sites, e não consegui achar nenhum código de Quicksort que eu conseguisse usar, ou algum que eu consiga usar

eu peguei este do wikipedia, mas não sei como passar esse parametro Comparator, eu preciso ordenar um vetor de Strings em ordem alfabetica, e não consigo usar, ai vai o codigo do quicksort que eu peguei:

import java.util.Comparator;
import java.util.Random;

public class Quicksort {
    public static final Random RND = new Random();      
    private static void swap(Object[] array, int i, int j) {
        Object tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    private int partition(Object[] array, int begin, int end, Comparator cmp) {
        int index = begin + RND.nextInt(end - begin + 1);
        Object pivot = array[index];
        swap(array, index, end);                
        for (int i = index = begin; i < end; ++ i) {
            if (cmp.compare(array[i+1], pivot) <= 0) {
                swap(array, index++, i);
        }   }
        swap(array, index, end);        
        return (index);
    }
    private void qsort(Object[] array, int begin, int end, Comparator cmp) {
        if (end > begin) {
            int index = partition(array, begin, end, cmp);
            qsort(array, begin, index, cmp);
            qsort(array, index,  end,  cmp);
    }   }
    public void sort(Object[] array, Comparator cmp) {
        qsort(array, 0, array.length - 1, cmp);
    }
}

Se alguem puder me explicar o funcionamento disso vai ser de muito ajuda, muito obrigado!!
abraço

[Bruno_Laturner]

Já viu parte da Wikipédia Inglesa sobre o algorítmo? Lá tem uma explicação bem completa. Aliás só de ver a animação e saber o que um algorítimo “dividir e conquistar” significa, dá pra saber o que acontece.

Ele divide um array em duas partes, que subsequentemente também dividem-se por duas partes, e vai dividindo até um ponto onde não dá pra dividir mais, e ordena essa subpartição do array. Ordenando todas as suas pequenas partes, ao final fica tudo ordenado.

Comparator é uma interface, então desenvolva uma classe que implemente os métodos definidos por ela, de acordo com a sua especificação, e instancie um objeto dessa classe, passando por parâmetro p/ a função qsort.

[Rapapel]

[quote=nipo_style]Eu procurei no google, aki no guj, e em vários sites, e não consegui achar nenhum código de Quicksort que eu conseguisse usar, ou algum que eu consiga usar

eu peguei este do wikipedia, mas não sei como passar esse parametro Comparator, eu preciso ordenar um vetor de Strings em ordem alfabetica, e não consigo usar, ai vai o codigo do quicksort que eu peguei:

import java.util.Comparator;
import java.util.Random;

public class Quicksort {
    public static final Random RND = new Random();      
    private static void swap(Object[] array, int i, int j) {
        Object tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    private int partition(Object[] array, int begin, int end, Comparator cmp) {
        int index = begin + RND.nextInt(end - begin + 1);
        Object pivot = array[index];
        swap(array, index, end);                
        for (int i = index = begin; i < end; ++ i) {
            if (cmp.compare(array[i+1], pivot) <= 0) {
                swap(array, index++, i);
        }   }
        swap(array, index, end);        
        return (index);
    }
    private void qsort(Object[] array, int begin, int end, Comparator cmp) {
        if (end > begin) {
            int index = partition(array, begin, end, cmp);
            qsort(array, begin, index, cmp);
            qsort(array, index,  end,  cmp);
    }   }
    public void sort(Object[] array, Comparator cmp) {
        qsort(array, 0, array.length - 1, cmp);
    }
}

Se alguem puder me explicar o funcionamento disso vai ser de muito ajuda, muito obrigado!!
abraço[/quote]

Amigo você pode comparar assim. Use Arrays.asList, transforme o vetor de Strings em uma lista de Strings List ai vc usa Collections.sort(objetoLista)
Isso da certo porque a Classe String já tem um comparador para definir qual é maior ou menor. implemente Comparable e seu e metodo compareTo para definir uma comparação entre outros tipos de objetos.

               String[] array = new String[3];
		array[0] = "C";
		array[1] = "B";
		array[2] = "A";
		
		List<String> lista = Arrays.asList(array);
		
		Collections.sort(lista);
		
		for(String el : lista){
			System.out.println(el);
		}

[nipo_style]

renrutal, essa parte teorica do quicksort eu entendi, mas eu nao entendo eh o funcionamento do codigo msm, e nao consegui usar por causa do parametro Comparator, vc disse pra eu implementar a interface, eu implementei, e agora tenho que implementar o metodo compare() e n sei oq colocar. Eu qro que o Quicksort compare se uma string eh maior q a outra, eu sei que existe um metodo String.compareTo() para isso, entao finalmente oq devo colocar dentro do metodo implementado compare()?

rapapel, desculpa minha ignorancia mas preciso de um modo bem simplees, mas vlw!

vlww! abraço

[tnaires]

Ué, retorne o resultado de s1.compareTo(s2)…

[cassio]

O que está gerando dúvidas aqui é que esse exemplo não ordena apenas strings. Ele ordena qualquer coisa, qualquer tipo de objeto. basta ver que o parâmetro que o método recebe é um Object[] (vetor de objetos, genérico). Por isso a necessidade de passar também um Comparator, pois dependendo do tipo de objeto presente no seu array, o significado de “maior” ou “menor” muda.
Comparator é uma interface. Assim, basta criar uma classe do tipo SuaClasseComparator que implemente a interface Comparator. Essa interface possui dois métodos: equals() e compareTo(). Implemente esses métodos de forma a refletir corretamente o que significa um objeto da sua classe ser menor, igual ou maior que outro semelhante. Consulte o javadoc da interface Comparator para maiores detalhes de como isso pode ser feito.

[Bruno_Laturner]

[quote=nipo_style]renrutal, essa parte teorica do quicksort eu entendi, mas eu nao entendo eh o funcionamento do codigo msm, e nao consegui usar por causa do parametro Comparator, vc disse pra eu implementar a interface, eu implementei, e agora tenho que implementar o metodo compare() e n sei oq colocar. Eu qro que o Quicksort compare se uma string eh maior q a outra, eu sei que existe um metodo String.compareTo() para isso, entao finalmente oq devo colocar dentro do metodo implementado compare()?

rapapel, desculpa minha ignorancia mas preciso de um modo bem simplees, mas vlw!

vlww! abraço[/quote]

compare é implementado da seguinte maneira:

class IdadeComparator implements Comparator<Pessoa>
{
  public int compare(Pessoa o1, Pessoa o2)
  {
    // Digamos os objetos comparados são Pessoas
    // e que nós desejamos comparar suas idades
    int idade1 = o1.getIdade();
    int idade2 = o2.getIdade();

    // compare funciona da seguinte maneira:
    //
    // retorna valores menores que zero caso
    //   o 1º item for menor que 2º
    if (idade1 < idade2)
      return -1;

    // retorna valores maiores que zero caso
    //   o 1º item for maior que 2º
    else if (idade1 > idade2)
      return 1;

    // retorna 0 caso o 1º item seja igual ao 2º
    // portanto:
    else
      return 0;
  }
}

Quando este IdadeComparator for passado a um método de ordenação(sort), ele vai ordenar uma Collection por idade.

No caso de Strings e e qualquer classe que implemente a interface Comparable, compare pode ser resumudo à:

public int compare(String o1, String o2) { return o1.compareTo(o2); }Isso, claro, depois de fazer as devidas checagens de nulidade dos parâmetros passados.

Ou para facilitar, e se for o que deseja, use o método estático da classe, String.CASE_INSENSITIVE_ORDER, ele retorna com Comparator, que compara com compareToIgnoreCase.

Edit:
Aliás, quando for comparar números [não muito grandes], faça somente:

  public int compare(Pessoa o1, Pessoa o2)
  {
      return o1.getIdade() - o2.getIdade();
  }

[tnaires]

[quote=renrutal]compare é implementado da seguinte maneira:

[code]
class IdadeComparator implements Comparator
{
public int compare(Pessoa o1, Pessoa o2)
{
// Digamos os objetos comparados são Pessoas
// e que nós desejamos comparar suas idades
int idade1 = o1.getIdade();
int idade2 = o2.getIdade();

// compare funciona da seguinte maneira:
//
// retorna valores menores que zero caso
//   o 1º item for menor que 2º
if (idade1 < idade2)
  return -1;

// retorna valores maiores que zero caso
//   o 1º item for maior que 2º
else if (idade1 > idade2)
  return 1;

// retorna 0 caso o 1º item seja igual ao 2º
// portanto:
else
  return 0;

}
}
[/code][/quote]
O código desse método pode ser resumido para:

public int compare(Pessoa p1, Pessoa p2) { return p1.getIdade() - p2.getIdade(); }

[Bruno_Laturner]

O código desse método pode ser resumido para:

Volte e leia o meu post até o final

[tnaires]

[quote=tnaires]O código desse método pode ser resumido para:

Volte e leia o meu post até o final ;)[/quote]
Que vacilo! :oops:
Desculpas.

[nipo_style]

entendi o metodo compare, mas oq eu passo no parametro do Quicksort??
ele pede: sort(Object[] array, Comparator cmp)
o primeiro eh o vetor, o segundo eu tentei fazer “this”, tentei o nome da classe que implementa a interface Comparator, mas da erro
“Cannot use this in a static context”
vlww, abraço

[Bruno_Laturner]

Se ele está esperando um objeto, passe um objeto:

new IdadeComparator()

[nipo_style]

Gente, ta acontecendo o seguinte aqui: “Exception in thread “main” java.lang.StackOverflowError”
Eu criei os comparators como vcs disseram, um pra comparar RegistroDicionario.portugues, outro RegistroDicionario.ingles.
instanciei td certinho e botei no metodo do quicksort, mas da erro!
o algoritmo do quicksort ta errado??
codigo:

public class Programa {

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		
		RegistroDicionario[] vet = new RegistroDicionario[20];
		
		for (int i = 0; i < vet.length; i++) {
			vet[i] = new RegistroDicionario();
		}
		
		vet[0].portugues = "Carro";
		vet[0].ingles = "Car";
		
		vet[1].portugues = "Estudante";
		vet[1].ingles = "Student";
		
		vet[2].portugues = "Computador";
		vet[2].ingles = "Computer";
		
		vet[3].portugues = "Teclado";
		vet[3].ingles = "Keyboard";
		
		vet[4].portugues = "Telefone";
		vet[4].ingles = "Phone";
		
		vet[5].portugues = "Papel";
		vet[5].ingles = "Paper";
		
		vet[6].portugues = "Mercado";
		vet[6].ingles = "Market";
		
		vet[7].portugues = "Relógio";
		vet[7].ingles = "Clock";
		
		vet[8].portugues = "Chave";
		vet[8].ingles = "Key";
		
		vet[9].portugues = "Café";
		vet[9].ingles = "Coffee";
		
		vet[10].portugues = "Leite";
		vet[10].ingles = "Milk";
		
		vet[11].portugues = "Calendário";
		vet[11].ingles = "Calendar";
		
		vet[12].portugues = "Perigo";
		vet[12].ingles = "Danger";
		
		vet[13].portugues = "Semana";
		vet[13].ingles = "Week";
		
		vet[14].portugues = "Dia";
		vet[14].ingles = "Day";
		
		vet[15].portugues = "Mês";
		vet[15].ingles = "Month";
		
		vet[16].portugues = "Ano";
		vet[16].ingles = "Year";
		
		vet[17].portugues = "Mesa";
		vet[17].ingles = "Table";
		
		vet[18].portugues = "Cadeira";
		vet[18].ingles = "Chair";
		
		vet[19].portugues = "Livro";
		vet[19].ingles = "Book";
		
		System.out.println("Português ou Inglês?");
		String resposta = input.next();
		
		if(resposta.equalsIgnoreCase("Português") ||
				resposta.equalsIgnoreCase("Portugues")) {
			System.out.println("Vetor desordenado: ");
			for (int i = 0; i < vet.length; i++) {
				System.out.println(vet[i].portugues);
			}
		}
		if(resposta.equalsIgnoreCase("Inglês") ||
				resposta.equalsIgnoreCase("Ingles")) {
			System.out.println("Vetor desordenado: ");
			for (int i = 0; i < vet.length; i++) {
				System.out.println(vet[i].ingles);
			}
		}
		
		System.out.println("Vetor ordenado: ");
		if(resposta.equalsIgnoreCase("Português") ||
				resposta.equalsIgnoreCase("Portugues")) {
			
			//QUICKSORT
			Quicksort qs = new Quicksort();
			qs.sort(vet, new PortuguesComparator());
			
			for (int i = 0; i < vet.length; i++) {
				System.out.println(vet[i].portugues);
			}
		}
		
		
	}

}

obrigado!
abrço

[nipo_style]

Alguém pode me ajudar???