Olá galera a algum tempo atrás eu fiz uma pergunta sobre Comb Sort aqui, porém como meu trabalho sobre pilhas era para entregar antes deste me envolvi mais com pilhas ( lembrando que as respostas que obtive foram de grande ajuda =] ). Então agora entra o Comb Sort: Tenho este código ( retirado do wikipédia) porém não entendi ele muito bem ( talvez pq ainda não trabalhei com generics ) [code] public static <E extends Comparable<? super E>> void sort(E[] input) {
int gap = input.length;
boolean swapped = true;
while (gap > 1 || swapped) {
if (gap > 1)
gap = (int) (gap / 1.247330950103979);
int i = 0;
swapped = false;
while (i + gap < input.length) {
if (input[i].compareTo(input[i + gap]) > 0) {
E t = input[i];
input[i] = input[i + gap];
input[i + gap] = t;
swapped = true;
}
i++;
}
}
}[/code]
Alguém poderia me ajudar a entende-lo ? E como seria uma aplicaçãozinha básica, baseada nesse código? ( não precisam me dar o código feito, visto que quero aprender como funciona ) !!! Meu intuito é o de explicar para sala como o código funciona e com referência nesse método de ordenação desenvolver um código para que sirva de exemplo !!!
Eu já tinha falado em trocar
public static <E extends Comparable<? super E>> void sort(E[] input) {
por
public static void sort(String[] input) {
para você ficar mais à vontade (o algoritmo continua o mesmo, só que para strings).
Uma forma de você descobrir como funciona o algoritmo é vê-lo funcionar passo a passo. Pegue esse programa e o rode no debugger da sua IDE (Eclipse, Netbeans) para você ver que elementos são trocados com que elementos.
[quote=entanglement]Eu já tinha falado em trocar
public static <E extends Comparable<? super E>> void sort(E[] input) {
por
public static void sort(String[] input) {
para você ficar mais à vontade (o algoritmo continua o mesmo, só que para strings).
Uma forma de você descobrir como funciona o algoritmo é vê-lo funcionar passo a passo. Pegue esse programa e o rode no debugger da sua IDE (Eclipse, Netbeans) para você ver que elementos são trocados com que elementos.
[/quote]
Então cara, o que eu não entendi é o que cada parte do código faz entendeu? No caso desse código para coloca-lo em funcionamento eu teria que fazer uma outra classe que receberia os valores dentro desse vetor input correto?
[quote=entanglement]1) Você tem de jogar esse método dentro de uma classe, para que essa classe alimente esse método com vários dados que você vai usar para testar o algoritmo.
- Uma forma de você entender o que cada linha faz é:
a) Ler direitinho o que está escrito naquele artigo de onde você copiou o programa, e
b) Criar um programa que chama esse método com alguns dados desordenados, e então acompanhar a execução do método linha por linha, usando um debugger. Garanto que isso vai lhe dar uma boa ideia do que está acontecendo - basta ter um pouco de paciência para ver que, aos poucos, os ddos vão ficando ordenados. [/quote]
Vlw cara, vou testar aqui !!!
[quote=entanglement]1) Você tem de jogar esse método dentro de uma classe, para que essa classe alimente esse método com vários dados que você vai usar para testar o algoritmo.
- Uma forma de você entender o que cada linha faz é:
a) Ler direitinho o que está escrito naquele artigo de onde você copiou o programa, e
b) Criar um programa que chama esse método com alguns dados desordenados, e então acompanhar a execução do método linha por linha, usando um debugger. Garanto que isso vai lhe dar uma boa ideia do que está acontecendo - basta ter um pouco de paciência para ver que, aos poucos, os ddos vão ficando ordenados. [/quote]
Cara só uma duvida: caso eu somente atribua os dados ao vetor ele deveria mostrar eles sendo organizados no debugger? Estou fazendo desta forma:
edit
O erro acima eu consegui resolver ( o problema era na classe principal que estava como sor.sort(null)), só que agora ele da java.lang.ArrayIndexOutOfBoundsException
Classe Sort
[code]public class Sort {
public static void sort(String[] input) {
input[5]="Francisco";
input[7]="João";
input[9]="Alex";
input[3]="Joana";
input[2]="Aline";
input[6]="Natália";
input[4]="Jéssica";
input[1]="Alexia";
input[8]="Caio";
input[0]="Leandro";
int gap = input.length;
boolean swapped = true;
while (gap > 1 || swapped) {
if (gap > 1)
gap = (int) (gap / 1.247330950103979);
int i = 0;
swapped = false;
while (i + gap < input.length) {
if (input[i].compareTo(input[i + gap]) > 0) {
String t = input[i];
input[i] = input[i + gap];
input[i + gap] = t;
swapped = true;
}
i++;
}
}
}
}[/code]
Classe Principal
public class Principal {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Sort sor = new Sort ();
sor.sort(args);
}
}
Fiz um pouco diferente mas consegui. Vou deixar o código caso esteja com a mesma duvida:
[code] import javax.swing.JOptionPane;
public class Sort {
public static void main(String[] args){
int i=0;
String [] preencher= new String [10];
for(i=0;i<10;i++){
preencher[i]=JOptionPane.showInputDialog("Digite o elemento");
}
int gap = preencher.length;
boolean swapped = true;
while (gap > 1 || swapped) {
if (gap > 1)
gap =(int) (gap / 1.247330950103979);
i = 0;
swapped = false;
while (i + gap < preencher.length) {
if (preencher[i].compareTo(preencher[i + gap]) > 0) {
String t = preencher[i];
preencher[i] = preencher[i + gap];
preencher[i + gap] = t;
swapped = true;
}
i++;
}
}
for(i=0;i<10;i++){
JOptionPane.showMessageDialog(null,preencher[i]);
}
}
}
[/code]
Porém eu só não consegui entender direito o que esse trecho faz:
while (i + gap < preencher.length) {
if (preencher[i].compareTo(preencher[i + gap]) > 0) {
String t = preencher[i];
preencher[i] = preencher[i + gap];
preencher[i + gap] = t;
swapped = true;
}
i++;
}
}
for(i=0;i<10;i++){
JOptionPane.showMessageDialog(null,preencher[i]);
}
}
}
Se alguém pudesse me explicar ficaria grato !!!