Olá, estou precisando do método QuickSort implementado em Java, eu ja consegui um só que não to entendendo nada, alguém teria algum mais simples de entender para me conseguir… Obrigado!!!
Kra de antemão é bom vc tomar conhecimento q o algoritmo do QuickSort não é dificílimo, mas tb n é trivial, o algoritmo é aquele e pronto =PPP
Na wiki pedia tem td qt é algoritimo q vc quiser implementado em praticamente todas as linguagens imagináveis. Aí vai o link do quicksort:
É impressionante como o QuickSort fica bonito em uma linguagem funcional como o Haskell neh… 
Mas então cara, acho que a melhor forma de você entender esse algoritmo é o bom e velho “teste de mesa”. Pega um papel e uma caneta, e vai simulando passo a passo a execução do algoritmo, até entender o funcionamento!
Esse link do wikipedia que o colega mandou é excelente!
Boa sorte!
Ae valeu pelo apoio vo da uma estudada neste algoritmo, era o mesmo que eu tinha visto antes o problema eh que eu nao consegui conciliar o QuickSort do wikipedia com o meu algoritmo, nao consigo me achar, se alguem puder me mandar o funcionamento dele eu agredeço… Valeu!!!
Em qualquer livro de algorítmos / estrutura de dados descente você encontra a explicação detalhada do quicksort. Dá uma olhada na biblioteca da sua escola/faculdade.
QuickSort e tão tranquilinho …
qual é o seu probelma maior … fale ae que tento te ajudar.
[code]
package sort;
import javax.swing.;
import java.util.;
/**
This class implements a version of the
quicksort algorithm using a partition
algorithm that does not rely on the
first element of the array being vacant,
nor does it guarantee that the chosen
pivot value is at the split point of
the partition.
@author Cay Horstmann
*/
public class QuickSort extends Thread implements Runnable{
private Hashtable valores;
private Vector idValores;
private int type;
public static final int DOUBLE = 1,
INT = 2;
public QuickSort( Vector idValores, Hashtable valores, int type ){
start();
setIdValores( idValores );
setValores( valores );
setType( type );
}
/**
Sorts the array managed by this sorter
*/
public void sort(){
sort( 0, getIdValores().size() - 1 );
}
public void sort( int low, int high ){
int p = 0;
if ( low >= high )
return;
if( getType() == 1 ){
p = partitionDouble( low, high );
}
else if( getType() == 2 ){
p = partitionInt( low, high );
}
sort(low, p);
sort(p + 1, high);
}
private int partitionDouble( int low, int high )
{
// First element
double pivot = Double.parseDouble( getValores().get( getIdValores().get( low ).toString() ).toString() );
// Middle element
//int middle = (low + high) / 2;
//int pivot = a[middle];
int i = low - 1;
int j = high + 1;
while (i < j){
i++;
while ( Double.parseDouble( getValores().get( getIdValores().get( i ).toString() ).toString() ) < pivot )
i++;
j--;
while ( Double.parseDouble( getValores().get( getIdValores().get( j ).toString() ).toString() ) > pivot )
j--;
if ( i < j )
swap( i, j );
}
return j;
}
private int partitionInt( int low, int high )
{
// First element
int pivot = Integer.parseInt( getValores().get( getIdValores().get( low ).toString() ).toString() );
// Middle element
//int middle = (low + high) / 2;
//int pivot = a[middle];
int i = low - 1;
int j = high + 1;
while (i < j){
i++;
while ( Integer.parseInt( getValores().get( getIdValores().get( i ).toString() ).toString() ) < pivot )
i++;
j--;
while ( Integer.parseInt( getValores().get( getIdValores().get( j ).toString() ).toString() ) > pivot )
j--;
if ( i < j )
swap( i, j );
}
return j;
}
/**
Swaps two entries of the array.
@param i the first position to swap
@param j the second position to swap
*/
private void swap( int i, int j ){
String npTempI = "",
npTempJ = "";
npTempI = getIdValores().get( i ).toString();
npTempJ = getIdValores().get( j ).toString();
getIdValores().remove( i );
getIdValores().add( i, npTempJ );
getIdValores().remove( j );
getIdValores().add( j, npTempI );
}
Este ai eh o metodo que eu consegui, ta e agora onde eu coloco o vetor que eu possuo que no caso seria “vContPalavras”.
Falow
perae vo vo se consigo agora…
[code]package sort;
import javax.swing.;
import java.util.;
/**
This class implements a version of the
quicksort algorithm using a partition
algorithm that does not rely on the
first element of the array being vacant,
nor does it guarantee that the chosen
pivot value is at the split point of
the partition.
@author Cay Horstmann
*/
public class QuickSort extends Thread implements Runnable{
private Hashtable valores;
private Vector idValores;
private int type;
public static final int DOUBLE = 1,
INT = 2;
public QuickSort( Vector idValores, Hashtable valores, int type ){
start();
setIdValores( idValores );
setValores( valores );
setType( type );
}
/**
Sorts the array managed by this sorter
*/
public void sort(){
sort( 0, getIdValores().size() - 1 );
}
public void sort( int low, int high ){
int p = 0;
if ( low >= high )
return;
if( getType() == 1 ){
p = partitionDouble( low, high );
}
else if( getType() == 2 ){
p = partitionInt( low, high );
}
sort(low, p);
sort(p + 1, high);
}
private int partitionDouble( int low, int high )
{
// First element
double pivot = Double.parseDouble( getValores().get( getIdValores().get( low ).toString() ).toString() );
// Middle element
//int middle = (low + high) / 2;
//int pivot = a[middle];
int i = low - 1;
int j = high + 1;
while (i < j){
i++;
while ( Double.parseDouble( getValores().get( getIdValores().get( i ).toString() ).toString() ) < pivot )
i++;
j--;
while ( Double.parseDouble( getValores().get( getIdValores().get( j ).toString() ).toString() ) > pivot )
j--;
if ( i < j )
swap( i, j );
}
return j;
}
private int partitionInt( int low, int high )
{
// First element
int pivot = Integer.parseInt( getValores().get( getIdValores().get( low ).toString() ).toString() );
// Middle element
//int middle = (low + high) / 2;
//int pivot = a[middle];
int i = low - 1;
int j = high + 1;
while (i < j){
i++;
while ( Integer.parseInt( getValores().get( getIdValores().get( i ).toString() ).toString() ) < pivot )
i++;
j--;
while ( Integer.parseInt( getValores().get( getIdValores().get( j ).toString() ).toString() ) > pivot )
j--;
if ( i < j )
swap( i, j );
}
return j;
}
/**
Swaps two entries of the array.
@param i the first position to swap
@param j the second position to swap
*/
private void swap( int i, int j ){
String npTempI = "",
npTempJ = "";
npTempI = getIdValores().get( i ).toString();
npTempJ = getIdValores().get( j ).toString();
getIdValores().remove( i );
getIdValores().add( i, npTempJ );
getIdValores().remove( j );
getIdValores().add( j, npTempI );
}
[/code]
Entendi!!! sou novo aqui. HEHEHE