Quicksort em java?

7 de março de 2007 7 respostas

tamanini 7 de março de 2007

Boa tarde, pessoal.

Eu estou começando em java e gostaria que alguém pudesse me ajudar nesse algoritmo quicksort, eu achei alguns exemplos pelo google, mas não consigo fazer com que funcione, eu peguei os mais simples, no caso os que tem menos códigos, pois gostaria de entender melhor o conceito do quicksort.
Segue abaixo os dois exemplos modificados, mas estão com problemas:

public class quicksort {

   /**
    * @param args
    */
   public static void main(String[] args) {
      // TODO Auto-generated method stub
      
                // Inicio da parte que acrescentei...
      int vet[] = new int[9];
      
      vet[0] = 5;
      vet[1] = 8;
      vet[2] = 7;
      vet[3] = 2;
      vet[4] = 3;
      vet[5] = 9;
      vet[6] = 1;
      vet[7] = 6;
      vet[8] = 10;
      vet[9] = 4;
      
      quicksort(vet, vet[6], vet[8]);
                // Fim da parte que acrescentei...

   }   
   
   public void quicksort (int[] a, int lo, int hi){
//        lo is the lower index, hi is the upper index
//        of the region of array a that is to be sorted
          int i=lo, j=hi, h;
          int x=a[(lo+hi)/2];

          //  partition
          do
          {   
              while (a[i]<x) i++;
              while (a[j]>x) j--;
              if (i&lt=j)
              {
                  h=a[i]; a[i]=a[j]; a[j]=h;
                  i++; j--;
              }
          } while (i&lt=j);

          //  recursion
          if (lo<j) quicksort(a, lo, j);
          if (i><hi) quicksort(a, i, hi);
      }

}

2º exemplo:

public class quicksort2 {

   /**
    * @param args
    */
   public static void main(String[] args) {
      // TODO Auto-generated method stub
               
      // inicio da parte que acrescentei!
      int array[] = new int[10];
      
      array[0] = 3;
      array[1] = 9;
      array[2] = 0;
      array[3] = 4;
      array[4] = 6;
      array[5] = 2;
      array[6] = 8;
      array[7] = 1;
      array[8] = 7;
      array[9] = 10;
      array[10] = 5;
      
      quicksort(0, array.length - 1, array);
                // fim da parte que acrescentei!
   }
   
   public void quicksort(int p, int q, int array[]){
       if (p >&lt q){
          int x = particao(p, q, array);
          quicksort(p, x - 1, array);
          quicksort(x + 1, q, array);
       }
   }
   public int particao(int p, int q, int array[]){
       int j = p - 1;
       int aux = array[q];
       for (int i = p; i &lt= q; i++){
              if (array[i] &lt= aux) troca(array, i, ++j);
       }
       return j;
   }
}

7 Respostas

emmanuel.silva 7 de mar. de 2007

De uma olhada nesse aqui, ve se é o que você precisa

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

public class Quicksort {
    public static final Random RND = new Random();      
    private 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 &lt end; ++ i) {
            if (cmp.compare(array[i], pivot) &lt= 0) {
                swap(array, index++, i);
        }   }
        swap(array, index, end);        
        return (index);
    }
    private void qsort(Object[] array, int begin, int end, Comparator cmp) {
        if (end &gt begin) {
            int index = partition(array, begin, end, cmp);
            qsort(array, begin, index - 1, cmp);
            qsort(array, index + 1,  end,  cmp);
    }   }
    public void sort(Object[] array, Comparator cmp) {
        qsort(array, 0, array.length - 1, cmp);
    }
}

tamanini 7 de mar. de 2007

Esse código é do site do wikipedia, correto?
Eu vi esse exemplo, mas achei muito complexo para quem está iniciando em java como eu.
Esses dois códigos que passei pelo que eu vi, estão corretos, só que falta fazer uma chamada a função e isso eu não sei como fazer, os exemplos que peguei foram dos sites abaixo:
1º exemplo:
http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/quick/quicken.htm

2º exemplo:
http://www.portaljava.com.br/home//modules.php?name=Content&pa=showpage&pid=56

emmanuel.silva 7 de mar. de 2007

Eu postei esse porque achei que era mais facil…

tamanini 7 de mar. de 2007

hehehe

É que para iniciante fica complicado, ainda mais para quem só sabe fazer declarar variáveis, fazer condições, laços e função com passagem por referência e um pouco de recursividade.
Por exemplo eu não saberia explicar essas linhas:

public static final Random RND = new Random();

Object tmp = array[i] // Por que Object?

import java.util.Comparator;
private int partition(… Comparator cmp){ // O que faz esse Comparator?

Saberia me explicar o funcionamento do código?

Achei um outro código aqui no site, só a única coisa é que também utiliza algumas bibliotecas para interagir com o usuário:
http://www.portaljava.com/home/modules.php?name=Forums&file=viewtopic&p=128860&highlight=quicksort#128860

Fabiano 7 de mar. de 2007

tamanini, estudei os dois exemplos que você postou e fiz da seguinte forma. O primeiro exemplo:

public class QuickSort {
	
	public static int array[] = new int[11];
	
	public static void main(String[] args) {
		QuickSort qs = new QuickSort();
		
		// inicio da parte que acrescentei!
		array[0] = 3;
		array[1] = 9;
		array[2] = 0;
		array[3] = 4;
		array[4] = 6;
		array[5] = 2;
		array[6] = 8;
		array[7] = 1;
		array[8] = 7;
		array[9] = 10;
		array[10] = 5;
		
		qs.quickSort(array[2],array[9]);
		// fim da parte que acrescentei!
		
		for (int i = 0; i &lt array.length; i++) {
			System.out.println(array[i]);
		}
	}
	
	public void quickSort ( int lo, int hi){
		//        lo is the lower index, hi is the upper index
		//        of the region of array a that is to be sorted
		int i=lo, j=hi, h;
		int x=array[(lo+hi)/2];
		
		//  partition
		do
		{   
			while (array[i]<x) i++;
			while (array[j]>x) j--;
			if (i&lt=j)
			{
				h=array[i]; array[i]=array[j]; array[j]=h;
				i++; j--;
			}
		} while (i&lt=j);
		
		//  recursion
		if (lo<j) quickSort(lo, j);
		if (i><hi) quickSort(i, hi);
	}
}

Já o segundo exemplo:

public class QuickSort {
	
	public static int array[] = new int[11];

	public static void main(String[] args) {
		QuickSort qs = new QuickSort();
		
		// inicio da parte que acrescentei!
		array[0] = 3;
		array[1] = 9;
		array[2] = 0;
		array[3] = 4;
		array[4] = 6;
		array[5] = 2;
		array[6] = 8;
		array[7] = 1;
		array[8] = 7;
		array[9] = 10;
		array[10] = 5;
		
		qs.quicksort(0, array.length - 1);
		// fim da parte que acrescentei!
		
		for (int i = 0; i &lt array.length; i++) {
			System.out.println(array[i]);
		}
	}
	
	public void quicksort(int p, int q){
		if (p &lt q){
			int x = particao(p, q);
			quicksort(p, x - 1);
			quicksort(x + 1, q);
		}
	}
	
	public int particao(int p, int q){
		int j = p - 1;
		int aux = array[q];
		for (int i = p; i &lt= q; i++){
			if (array[i] &lt= aux) troca(array, i, ++j);
		}
		return j;
	}
	
	public void troca(int array[], int i, int j){
		int aux = array[i];
		array[i] = array[j];
		array[j] = aux;
	}	
}

O terceiro exemplo só bati o olho, vou ver melhor depois…

Quanto ao código que nosso amigo emmanuel postou, também queria entender o Comparator. Inclusive acho que não precisa entrar nessa complexidade (inclusive o exemplo não tem o método main, como executo então já que não sei o que passar no "Comparator"?). Depois eu vou dar uma estudada nos códigos, é legal voltar aos tempos de faculdade, hehehehe…

Sds

tamanini 9 de mar. de 2007

Obrigado pela ajuda Fabiano, vou testar aqui.
Eu gostaria de entender melhor o funcionamento do algoritmo quicksort e por isso peguei alguns exemplos simples com vetor, mas na verdade, tenho que trabalhar com matriz e não com vetor como fiz no exemplo e ainda ordenar em ordem decrescente a matriz e para preencher o array, irei fazer um laço escadinha.
Já estou apanhando nos primeiros trabalhos da facul, imagine quando chegar na metade do ano. hehehe

tamanini 12 de mar. de 2007

E aí pessoal, alguém mais pode me ajudar a resolver esse problema?

Criado 7 de março de 2007

Ultima resposta 12 de mar. de 2007

Respostas 7

Participantes 3

7 Respostas

Topicos relacionados