Fiz esse código para ordenar lexicograficamente arrays de String, mas não está funcionando, ele roda, mas a saída não é a esperada…
Alguém pode me ajudar? Pois já passei dias mexendo nesse código e não consegui achar o erro…
CÓDIGO:
[code]public class QuickS {
public int acharPivo(String[] s) {
return (int) Math.floor(s.length / 2);
}
public int particiona(String[] array, int i, int f) {
int a = i + 1;
int b = f;
int pivo = acharPivo(array);
while (a < b) {
while (a <= f && array[a].compareTo(array[pivo]) <= 0) {
a++;
}
while (array[b].compareTo(array[pivo]) > 0) {
b--;
}
if (a < b) {
String temp = array[a];
array[a] = array[b];
array[b] = temp;
}
}
String temp = array[b];
array[b] = array[i];
array[i] = temp;
return b;
}
public void quicksort(String[] array, int i, int f) {
if (i < f) {
int p = particiona(array, i, f);
quicksort(array, i, p - 1);
quicksort(array, p + 1, f);
}
}
public void quicksort(String[] array) {
quicksort(array, 0, (array.length - 1));
}
public static void main(String[] args) {
QuickS sorting = new QuickS();
String[] nomes = new String[6];
nomes[0] = "flavio";
nomes[1] = "fernanda";
nomes[2] = "lamartine";
nomes[3] = "ideginaldo";
nomes[4] = "luiza";
nomes[5] = "giselly";
for(int i = 0; i < 6; i++) {
System.out.print(nomes[i]);
System.out.print(" ");
}
System.out.println("");
sorting.quicksort(nomes);
for(int i = 0; i < 6; i++) {
System.out.print(nomes[i]);
System.out.print(" ");
}
}
Pessoal, eu ainda não consegui achar onde está o erro, quando estava no trabalho me ocorreu que poderia ser no método que acha o pivô, mas modifiquei e não era…
Quando uso o debug do Eclipse eu percebo que ele não ordena os elementos, apenas troca alguns de posição…
Pessoal!! Consegui!!! Resolvi postar aqui como resolvi esse problema, caso alguém se interesse…
1º - Quando eu chamava acharPivo no método particiona, ele sempre pegava o elemento do meio, mesmo que entrasse na recursão; resolvi isso adicionando dois int como parametros, um para indicar o começo e o outro prar indicar o fim de onde deve-se achar o pivo. Assim quando o método entra na recursão, ele checa quem é o pivo do subconjunto esquerdo, e depois do direito.
public int acharPivo(String[] s, int ini, int fim) {
// Também tirei o que seria a função chão: Math.floor
// Java já faz isso pra mim... :D
return (fim + ini / 2);
}
2º - Eu só estava trocando o elemento do começo pelo pivo depois de ter realizado todas as trocas, o que me dava uma troca errada por entrada na recursão, no final, todo minha saída estava desorganizada… Falta de atenção, pois no algoritmo, o pivo deve ser trocado logo no início… Assim meu código ficou dessa forma:
[code]public int particiona(String[] array, int i, int f) {
int a = i;
int b = f;
int pivo = acharPivo(array, i, f);
String temp = array[b];
array[b] = array[i];
array[i] = temp;
while (a < b) {
while (a <= f && array[a].compareTo(array[pivo]) <= 0) {
a++;
}
while (array[b].compareTo(array[pivo]) > 0) {
b--;
}
if (a < b) {
String temp2 = array[a];
array[a] = array[b];
array[b] = temp2;
}
}
return b;
}[/code]
O Resto continua igual… Quem se interessou em saber qual o erro, taí a resposta…
