Tenho vamos supoer uma classe de revistas, em um array será então dada as informações como nome da revista por exemplo. Porem gostaria de por em ordem elas e vi em algum lugar sobre ordenar arrays em ordem alfabética através disto: Arrays.sort(String[] vect) porém nao intendi muito bem alguem pode me esclarecer esta duvida?
Ordem alfabética
O
36 Respostas
R
na verdade a classe tem um método
public static void sort(Object[] a)
como String é subclasse de object, ela pode ser “sorteada” pela classe
o que essa classe faz?
ela ordena o vetor com base:
- com o hashCode() do objeto, que é um código que identifica o objeto
- com base no método compareTo() do objeto
- ???
O
Desculpa mais realmente sou um pouco leigo no assunto … é um Array vamos supor de varios titulos, esses titulos apresentam na Classe Livros, esses titulos eu pretendia pegar eles e por em ordem alfabética…vamos supor declarei assim private Livros[] lista_de_livros = new Livros[1000];
então nas lista_de_livros eu xamaria o getTitulo porém preciso ordenar alfabéticamente … pode ajudar? 
R
Cara o que vc pode estar fazendo é jogando em um ArrayList e executando o sort.
Ex:import java.util.*;
public class teste {
public static void main(String[] args) {
String a[] = {"Maria", "Joao", "Renan"};
ArrayList lista = new ArrayList();
for(int i = 0; i < a.length; i++) {
lista.add(a[i]);
}
Collections.sort(lista);
System.out.println(lista);
}
}
A saida vai estar ordenada...
Te ajudou...?
M
Cara o que vc pode estar fazendo é jogando em um ArrayList e executando o sort. Ex:import java.util.*; public class teste { public static void main(String[] args) { String a[] = {"Maria", "Joao", "Renan"}; ArrayList lista = new ArrayList(); for(int i = 0; i < a.length; i++) { lista.add(a[i]); } Collections.sort(lista); System.out.println(lista); } }A saida vai estar ordenada...
Te ajudou...?
Na verdade, a maneira que faço (e acho ideal) é escrever o algoritmo de sort, tipo (usei esse codigo, entao funciona):
public String [] sort(String [] strArray) throws Exception {
int j;
int limit = strArray.length;
int st = -1;
while(st < limit) {
st++;
limit--;
boolean swapped = false;
for(j = st; j < limit; j++) {
int strArrayAt = (int) strArray[j].charAt(0);
if(strArrayAt >= 97 && strArrayAt <= 122) {
strArrayAt = strArrayAt - 32;
}
int strArrayAtPlusOne = (int) strArray[j + 1].charAt(0);
if(strArrayAtPlusOne >= 97 && strArrayAtPlusOne <= 122) {
strArrayAtPlusOne = strArrayAtPlusOne - 32;
}
if(strArrayAt > strArrayAtPlusOne) {
String tempValue = strArray[j];
strArray[j] = strArray[j + 1];
strArray[j + 1] = tempValue;
swapped = true;
}
}
for(j = limit; --j >= st;) {
int strArrayAt = (int) strArray[j].charAt(0);
if(strArrayAt >= 97 && strArrayAt <= 122) {
strArrayAt = strArrayAt - 32;
}
int strArrayAtPlusOne = (int) strArray[j + 1].charAt(0);
if(strArrayAtPlusOne >= 97 && strArrayAtPlusOne <= 122) {
strArrayAtPlusOne = strArrayAtPlusOne - 32;
}
if(strArrayAt > strArrayAtPlusOne) {
String tempValue = strArray[j];
strArray[j] = strArray[j + 1];
strArray[j + 1] = tempValue;
swapped = true;
}
}
}
return strArray;
}
O
Poderia me explicar sobre os valores que apresentou neste seu Sort?
“if(strArrayAt >= 97 && strArrayAt <= 122)”
por exemplo esta linha realmente nao intendi como o metodo funciona =/. Obrigado!
J
Olá, renam, não precisa fazer o for para preencher a List com os objetos do array. Basta fazer assim:
Creio que esse if deve estar relacionado ao codigo ascii dos caracteres. Bom, melhor do que fazer a ordenação dessa maneira, seria criar um Comparator.
import java.util.*;
public class teste {
public static void main(String[] args) {
String a[] = {"Maria", "Joao", "Renan"};
List lista = Arrays.asList(a);
Collections.sort(lista);
System.out.println(lista);
}
}
Poderia me explicar sobre os valores que apresentou neste seu Sort?"if(strArrayAt >= 97 && strArrayAt <= 122)"
Creio que esse if deve estar relacionado ao codigo ascii dos caracteres. Bom, melhor do que fazer a ordenação dessa maneira, seria criar um Comparator.
valeuz...
M
Poderia me explicar sobre os valores que apresentou neste seu Sort?“
if(strArrayAt >= 97 && strArrayAt <= 122)”por exemplo esta linha realmente nao intendi como o metodo funciona =/. Obrigado!
Isso significa de A até Z em minusculo, em ASCII!
É uma versão bi-direcional do algoritmo da bolha.
Tem espaço pra melhorias aí (por exemplo, um ‘ç’ não seria considerado como ‘c’, e não seria ordenado direito (viria depois do z, por que o ASCII de ‘ç’ é maior que o ascii de ‘z’).
abs
R
[quote="jack_-_ganzha"]Olá, renam, não precisa fazer o for para preencher a List com os objetos do array. Basta fazer assim:
import java.util.*;
public class teste {
public static void main(String[] args) {
String a[] = {"Maria", "Joao", "Renan"};
List lista = Arrays.asList(a);
Collections.sort(lista);
System.out.println(lista);
}
}
Essa eu naum conhecia, valeu...
F
Cara o que vc pode estar fazendo é jogando em um ArrayList e executando o sort. Ex:import java.util.*; public class teste { public static void main(String[] args) { String a[] = {"Maria", "Joao", "Renan"}; ArrayList lista = new ArrayList(); for(int i = 0; i < a.length; i++) { lista.add(a[i]); } Collections.sort(lista); System.out.println(lista); } }A saida vai estar ordenada...
Te ajudou...?
Na verdade, a maneira que faço (e acho ideal) é escrever o algoritmo de sort, tipo (usei esse codigo, entao funciona):
public String [] sort(String [] strArray) throws Exception { int j; int limit = strArray.length; int st = -1; while(st < limit) { st++; limit--; boolean swapped = false; for(j = st; j < limit; j++) { int strArrayAt = (int) strArray[j].charAt(0); if(strArrayAt >= 97 && strArrayAt <= 122) { strArrayAt = strArrayAt - 32; } int strArrayAtPlusOne = (int) strArray[j + 1].charAt(0); if(strArrayAtPlusOne >= 97 && strArrayAtPlusOne <= 122) { strArrayAtPlusOne = strArrayAtPlusOne - 32; } if(strArrayAt > strArrayAtPlusOne) { String tempValue = strArray[j]; strArray[j] = strArray[j + 1]; strArray[j + 1] = tempValue; swapped = true; } } for(j = limit; --j >= st;) { int strArrayAt = (int) strArray[j].charAt(0); if(strArrayAt >= 97 && strArrayAt <= 122) { strArrayAt = strArrayAt - 32; } int strArrayAtPlusOne = (int) strArray[j + 1].charAt(0); if(strArrayAtPlusOne >= 97 && strArrayAtPlusOne <= 122) { strArrayAtPlusOne = strArrayAtPlusOne - 32; } if(strArrayAt > strArrayAtPlusOne) { String tempValue = strArray[j]; strArray[j] = strArray[j + 1]; strArray[j + 1] = tempValue; swapped = true; } } } return strArray; }
pra comparar Strings n eh mais facil fazer isso:
if (str1.compareTo(str2) > 0){
// a str1 vem depois de str2
}
else{
// a str1 vem antes (ou junto, caso o valor seja 0) da str2
}
alem de q no seu codigo vc esta comparando soh a primeira, pelo seu codigo essas duas strings seriam iguas:
azzzzz aa
e tipo, eu prefiro usar o quicksort:
public void troca(String array[], int i, int j){
String aux = array[i];
array[i] = array[j];
array[j] = aux;
}
public void quicksort(int p, int q, String array[]){
if (p < q){
int x = particao(p, q, array);
quicksort(p, x - 1, array);
quicksort(x + 1, q, array);
}
}
public int particao(int p, int q, String array[]){
int j = p - 1;
String aux = array[q];
for (int i = p; i <= q; i++){
if (array[i].compareTo(aux) <= 0) troca(array, i, ++j);
}
return j;
}
dai pra iniciar o quicksort chame:
quicksort(0, array.length - 1, array);
O
public void ordenar() {
Livros temp = new Livros();
temp = (Livros) lista_de_livros[i];
String a[] ={temp.getTitulo()};
List lista = Arrays.asList(a);
Collections.sort(lista);
System.out.println(lista);
}
//Preciso no Array a[] o Titulo dos livros que ja tem em um array. Ae não sei se devo percorrer o Array largando as variaveis realmente estou em duvidas sendo que vamos supor é um Array de lista_de_livros onde apresenta Titulos, Ano, Preco ... porem preciso apenas o titulo, será através dele a ordenagem ... porém nao consigo efetuar a operação...
M
Cara o que vc pode estar fazendo é jogando em um ArrayList e executando o sort. Ex:import java.util.*; public class teste { public static void main(String[] args) { String a[] = {"Maria", "Joao", "Renan"}; ArrayList lista = new ArrayList(); for(int i = 0; i < a.length; i++) { lista.add(a[i]); } Collections.sort(lista); System.out.println(lista); } }A saida vai estar ordenada...
Te ajudou...?
Na verdade, a maneira que faço (e acho ideal) é escrever o algoritmo de sort, tipo (usei esse codigo, entao funciona):
public String [] sort(String [] strArray) throws Exception { int j; int limit = strArray.length; int st = -1; while(st < limit) { st++; limit--; boolean swapped = false; for(j = st; j < limit; j++) { int strArrayAt = (int) strArray[j].charAt(0); if(strArrayAt >= 97 && strArrayAt <= 122) { strArrayAt = strArrayAt - 32; } int strArrayAtPlusOne = (int) strArray[j + 1].charAt(0); if(strArrayAtPlusOne >= 97 && strArrayAtPlusOne <= 122) { strArrayAtPlusOne = strArrayAtPlusOne - 32; } if(strArrayAt > strArrayAtPlusOne) { String tempValue = strArray[j]; strArray[j] = strArray[j + 1]; strArray[j + 1] = tempValue; swapped = true; } } for(j = limit; --j >= st;) { int strArrayAt = (int) strArray[j].charAt(0); if(strArrayAt >= 97 && strArrayAt <= 122) { strArrayAt = strArrayAt - 32; } int strArrayAtPlusOne = (int) strArray[j + 1].charAt(0); if(strArrayAtPlusOne >= 97 && strArrayAtPlusOne <= 122) { strArrayAtPlusOne = strArrayAtPlusOne - 32; } if(strArrayAt > strArrayAtPlusOne) { String tempValue = strArray[j]; strArray[j] = strArray[j + 1]; strArray[j + 1] = tempValue; swapped = true; } } } return strArray; }pra comparar Strings n eh mais facil fazer isso:
if (str1.compareTo(str2) > 0){ // a str1 vem depois de str2 } else{ // a str1 vem antes (ou junto, caso o valor seja 0) da str2 }alem de q no seu codigo vc esta comparando soh a primeira, pelo seu codigo essas duas strings seriam iguas:
azzzzz aae tipo, eu prefiro usar o quicksort:
public void troca(String array[], int i, int j){ String aux = array[i]; array[i] = array[j]; array[j] = aux; } public void quicksort(int p, int q, String array[]){ if (p < q){ int x = particao(p, q, array); quicksort(p, x - 1, array); quicksort(x + 1, q, array); } } public int particao(int p, int q, String array[]){ int j = p - 1; String aux = array[q]; for (int i = p; i <= q; i++){ if (array[i].compareTo(aux) <= 0) troca(array, i, ++j); } return j; }dai pra iniciar o quicksort chame:
quicksort(0, array.length - 1, array);
Nunca usei o quicksort, mas em termos de performance ele parece absurdamente horrivel (vide fato de ficar passando o array pra lá e pra cá...parece totalmente não escalável).
Enfim, como disse anteriormente, whatever floats your boat.
O que propus é muito mais rápido, e pouco eficaz (dependendo da aplicação)...mas no caso da minha aplicação (o chatserver da america online), me foi muito útil para ordenar os nomes dos usuários no drop down de usuários.
F
pelo contrario!!! o quicksort eh um dos metodos de ordenacao mais rapidos!!! isso pra n dizer o mais rapido…
qnto a passar os arrays, lembre-se de q os arrays sao passados por referencia, ou seja, eles vao passar apenas a posicao q o array ocupa na memoria, como se fosse passar um simpes int!!! eh por isso q se vc passar um array por um metodo, se vc alterar ele as alteracoes seram validas para o “original”
e tb, eu tava passando o array como argumento apenas pra mostrar como funciona, se o array estiver em uma variavel global vc n precisa ficar passando ele…
M
pelo contrario!!! o quicksort eh um dos metodos de ordenacao mais rapidos!!! isso pra n dizer o mais rapido…qnto a passar os arrays, lembre-se de q os arrays sao passados por referencia, ou seja, eles vao passar apenas a posicao q o array ocupa na memoria, como se fosse passar um simpes int!!! eh por isso q se vc passar um array por um metodo, se vc alterar ele as alteracoes seram validas para o “original”
e tb, eu tava passando o array como argumento apenas pra mostrar como funciona, se o array estiver em uma variavel global vc n precisa ficar passando ele…
Nah…
Eu escolhi o mais rápido que encontrei quando fiz a aplicação…e por via das dúvidas resolvi testar os códigos:
Resultado foi:
Bubble->Amostragem 0: 210ms
Bubble->Amostragem 1: 200ms
Bubble->Amostragem 2: 201ms
Bubble->Amostragem 3: 190ms
Bubble->Amostragem 4: 210ms
Bubble->Average: 202ms
Bubble->Output: 1,2,3,4,5,6,7,8,9,
Quicksort->Amostragem 0: 381ms
Quicksort->Amostragem 1: 380ms
Quicksort->Amostragem 2: 411ms
Quicksort->Amostragem 3: 370ms
Quicksort->Amostragem 4: 381ms
Quicksort->Average: 384ms
Quicksort->Output: 1,2,3,4,5,6,7,8,9,
O código que usei pra chegar a isso foi:
public class Bench {
public static void main(String [] argvs) throws Exception {
String [] abc = new String[] {"9", "3", "1", "2", "4", "8", "6", "7", "5"};
Bench bench = new Bench();
int len = abc.length;
int total = 0;
int iteration = 5;
// bubble
for(int x = 0; x < iteration; x++) {
long str = System.currentTimeMillis();
for(int y = 0; y < 100000; y++) {
bench.bubble(abc);
}
long end = System.currentTimeMillis();
total += end - str;
System.out.println("Bubble->Amostragem " + x + ": " + (end - str) + "ms");
}
System.out.println("Bubble->Average: " + Math.round(total / iteration) + "ms");
System.out.print("Bubble->Output: ");
for(int i = 0; i < len; i++) {
System.out.print(abc[i] + ",");
}
System.out.println("");
// quicksort
total = 0;
for(int x = 0; x < iteration; x++) {
long str = System.currentTimeMillis();
for(int y = 0; y < 100000; y++) {
bench.quicksort(0, len - 1, abc);
}
long end = System.currentTimeMillis();
total += end - str;
System.out.println("Quicksort->Amostragem " + x + ": " + (end - str) + "ms");
}
System.out.println("Quicksort->Average: " + Math.round(total / iteration) + "ms");
System.out.print("Quicksort->Output: ");
for(int i = 0; i < len; i++) {
System.out.print(abc[i] + ",");
}
System.out.println("");
}
void troca(String array[], int i, int j) {
String aux = array[i];
array[i] = array[j];
array[j] = aux;
}
void quicksort(int p, int q, String array[]) {
if (p < q) {
int x = particao(p, q, array);
quicksort(p, x - 1, array);
quicksort(x + 1, q, array);
}
}
int particao(int p, int q, String array[]){
int j = p - 1;
String aux = array[q];
for (int i = p; i <= q; i++){
if (array[i].compareTo(aux) <= 0) troca(array, i, ++j);
}
return j;
}
String [] bubble(String [] strArray) throws Exception {
int j;
int limit = strArray.length;
int st = -1;
while(st < limit) {
st++;
limit--;
boolean swapped = false;
for(j = st; j < limit; j++) {
int strArrayAt = (int) strArray[j].charAt(0);
if(strArrayAt >= 97 && strArrayAt <= 122) {
strArrayAt = strArrayAt - 32;
}
int strArrayAtPlusOne = (int) strArray[j + 1].charAt(0);
if(strArrayAtPlusOne >= 97 && strArrayAtPlusOne <= 122) {
strArrayAtPlusOne = strArrayAtPlusOne - 32;
}
if(strArrayAt > strArrayAtPlusOne) {
String tempValue = strArray[j];
strArray[j] = strArray[j + 1];
strArray[j + 1] = tempValue;
swapped = true;
}
}
for(j = limit; --j >= st;) {
int strArrayAt = (int) strArray[j].charAt(0);
if(strArrayAt >= 97 && strArrayAt <= 122) {
strArrayAt = strArrayAt - 32;
}
int strArrayAtPlusOne = (int) strArray[j + 1].charAt(0);
if(strArrayAtPlusOne >= 97 && strArrayAtPlusOne <= 122) {
strArrayAtPlusOne = strArrayAtPlusOne - 32;
}
if(strArrayAt > strArrayAtPlusOne) {
String tempValue = strArray[j];
strArray[j] = strArray[j + 1];
strArray[j + 1] = tempValue;
swapped = true;
}
}
}
return strArray;
}
}
Por um segundo pensei que eu estivesse errado sobre a velocidade…mas estava certo
Vivendo e aprendendo 
EDIT: Tinha esquecido de zerar o “total” e por isso nao estava correto o resultado.
M
pelo contrario!!! o quicksort eh um dos metodos de ordenacao mais rapidos!!! isso pra n dizer o mais rapido…qnto a passar os arrays, lembre-se de q os arrays sao passados por referencia, ou seja, eles vao passar apenas a posicao q o array ocupa na memoria, como se fosse passar um simpes int!!! eh por isso q se vc passar um array por um metodo, se vc alterar ele as alteracoes seram validas para o “original”
e tb, eu tava passando o array como argumento apenas pra mostrar como funciona, se o array estiver em uma variavel global vc n precisa ficar passando ele…
Nah…
Eu escolhi o mais rápido que encontrei quando fiz a aplicação…e por via das dúvidas resolvi testar os códigos:Resultado foi:
Bubble->Amostragem 0: 210ms Bubble->Amostragem 1: 200ms Bubble->Amostragem 2: 201ms Bubble->Amostragem 3: 190ms Bubble->Amostragem 4: 210ms Bubble->Average: 202ms Bubble->Output: 1,2,3,4,5,6,7,8,9, Quicksort->Amostragem 0: 381ms Quicksort->Amostragem 1: 380ms Quicksort->Amostragem 2: 411ms Quicksort->Amostragem 3: 370ms Quicksort->Amostragem 4: 381ms Quicksort->Average: 384ms Quicksort->Output: 1,2,3,4,5,6,7,8,9,O código que usei pra chegar a isso foi:
public class Bench { public static void main(String [] argvs) throws Exception { String [] abc = new String[] {"9", "3", "1", "2", "4", "8", "6", "7", "5"}; Bench bench = new Bench(); int len = abc.length; int total = 0; int iteration = 5; // bubble for(int x = 0; x < iteration; x++) { long str = System.currentTimeMillis(); for(int y = 0; y < 100000; y++) { bench.bubble(abc); } long end = System.currentTimeMillis(); total += end - str; System.out.println("Bubble->Amostragem " + x + ": " + (end - str) + "ms"); } System.out.println("Bubble->Average: " + Math.round(total / iteration) + "ms"); System.out.print("Bubble->Output: "); for(int i = 0; i < len; i++) { System.out.print(abc[i] + ","); } System.out.println(""); // quicksort total = 0; for(int x = 0; x < iteration; x++) { long str = System.currentTimeMillis(); for(int y = 0; y < 100000; y++) { bench.quicksort(0, len - 1, abc); } long end = System.currentTimeMillis(); total += end - str; System.out.println("Quicksort->Amostragem " + x + ": " + (end - str) + "ms"); } System.out.println("Quicksort->Average: " + Math.round(total / iteration) + "ms"); System.out.print("Quicksort->Output: "); for(int i = 0; i < len; i++) { System.out.print(abc[i] + ","); } System.out.println(""); } void troca(String array[], int i, int j) { String aux = array[i]; array[i] = array[j]; array[j] = aux; } void quicksort(int p, int q, String array[]) { if (p < q) { int x = particao(p, q, array); quicksort(p, x - 1, array); quicksort(x + 1, q, array); } } int particao(int p, int q, String array[]){ int j = p - 1; String aux = array[q]; for (int i = p; i <= q; i++){ if (array[i].compareTo(aux) <= 0) troca(array, i, ++j); } return j; } String [] bubble(String [] strArray) throws Exception { int j; int limit = strArray.length; int st = -1; while(st < limit) { st++; limit--; boolean swapped = false; for(j = st; j < limit; j++) { int strArrayAt = (int) strArray[j].charAt(0); if(strArrayAt >= 97 && strArrayAt <= 122) { strArrayAt = strArrayAt - 32; } int strArrayAtPlusOne = (int) strArray[j + 1].charAt(0); if(strArrayAtPlusOne >= 97 && strArrayAtPlusOne <= 122) { strArrayAtPlusOne = strArrayAtPlusOne - 32; } if(strArrayAt > strArrayAtPlusOne) { String tempValue = strArray[j]; strArray[j] = strArray[j + 1]; strArray[j + 1] = tempValue; swapped = true; } } for(j = limit; --j >= st;) { int strArrayAt = (int) strArray[j].charAt(0); if(strArrayAt >= 97 && strArrayAt <= 122) { strArrayAt = strArrayAt - 32; } int strArrayAtPlusOne = (int) strArray[j + 1].charAt(0); if(strArrayAtPlusOne >= 97 && strArrayAtPlusOne <= 122) { strArrayAtPlusOne = strArrayAtPlusOne - 32; } if(strArrayAt > strArrayAtPlusOne) { String tempValue = strArray[j]; strArray[j] = strArray[j + 1]; strArray[j + 1] = tempValue; swapped = true; } } } return strArray; } }Por um segundo pensei que eu estivesse errado sobre a velocidade…mas estava certo
Vivendo e aprendendoEDIT: Tinha esquecido de zerar o “total” e por isso nao estava correto o resultado.
Detalhe: esse codigo meu do bubble era pra ser bi-direcional, mas pelo que vi, fiz merda.
Comentando o laco for:
for(j = limit; --j >= st;) {
Funciona normalmente e a média cai pela metade, ficando ainda mais rápido.
M
Aff, olhando meu bubble sort melhor agora, dá até nojo.
Enfim, minha solução (obvio que o bubble nao fui eu que inventei né, so estou sugerindo) é mais rápida, porém o meu código está nojento (ver variavel swapped que nao serve pra nada por exemplo).
Vou re-escrever esse lixo e posto em 5 mins.
M
Aff, olhando meu bubble sort melhor agora, dá até nojo.Enfim, minha solução (obvio que o bubble nao fui eu que inventei né, so estou sugerindo) é mais rápida, porém o meu código está nojento (ver variavel swapped que nao serve pra nada por exemplo).
Vou re-escrever esse lixo e posto em 5 mins.
Ah, estava sujo mas nem tanto, enfim o codigo de comparacao estava ruim tambem…esse esta melhor, com o bubble bidirecional escrito da maneira certa, deu o seguinte:
Bubble->Amostragem 0: 130ms
Bubble->Amostragem 1: 100ms
Bubble->Amostragem 2: 90ms
Bubble->Amostragem 3: 130ms
Bubble->Amostragem 4: 90ms
Bubble->Average: 108ms
Bubble->Output: 3,4,5,6,7,8,
Quicksort->Amostragem 0: 191ms
Quicksort->Amostragem 1: 180ms
Quicksort->Amostragem 2: 190ms
Quicksort->Amostragem 3: 180ms
Quicksort->Amostragem 4: 181ms
Quicksort->Average: 184ms
Quicksort->Output: 3,4,5,6,7,8,
O codigo usado foi:
public class Bench {
public static void main(String [] argvs) throws Exception {
String [] ori = new String[] {"8", "5", "7", "6", "4", "3"};
String [] abc = ori.clone();
Bench bench = new Bench();
int len = abc.length;
int total = 0;
int iteration = 5;
long str, end;
// bubble
for(int x = 0; x < iteration; x++) {
str = System.currentTimeMillis();
for(int y = 0; y < 100000; y++) {
bench.bubble(abc);
}
end = System.currentTimeMillis();
total += end - str;
System.out.println("Bubble->Amostragem " + x + ": " + (end - str) + "ms");
}
System.out.println("Bubble->Average: " + Math.round(total / iteration) + "ms");
System.out.print("Bubble->Output: ");
for(int i = 0; i < len; i++) {
System.out.print(abc[i] + ",");
}
System.out.println("");
// quicksort
abc = ori.clone();
total = 0;
for(int x = 0; x < iteration; x++) {
str = System.currentTimeMillis();
for(int y = 0; y < 100000; y++) {
bench.quicksort(0, len - 1, abc);
}
end = System.currentTimeMillis();
total += end - str;
System.out.println("Quicksort->Amostragem " + x + ": " + (end - str) + "ms");
}
System.out.println("Quicksort->Average: " + Math.round(total / iteration) + "ms");
System.out.print("Quicksort->Output: ");
for(int i = 0; i < len; i++) {
System.out.print(abc[i] + ",");
}
System.out.println("");
}
void troca(String array[], int x, int y) {
String aux = array[x];
array[x] = array[y];
array[y] = aux;
}
void quicksort(int p, int q, String array[]) {
if(p < q) {
int x = particao(p, q, array);
quicksort(p, x - 1, array);
quicksort(x + 1, q, array);
}
}
int particao(int p, int q, String array[]) {
int j = p - 1;
String aux = array[q];
for(int i = p; i <= q; i++){
if (array[i].compareTo(aux) <= 0)
troca(array, i, ++j);
}
return j;
}
String [] bubble(String [] strArray) throws Exception {
int cur = 0;
int limit = strArray.length - 1;
int start = 0;
while(start < limit) {
for(cur = start; cur < limit; cur++) {
int strArrayAt = (int) strArray[cur].charAt(0);
if(strArrayAt >= 97 && strArrayAt <= 122) {
strArrayAt = strArrayAt - 32;
}
int strArrayAtPlusOne = (int) strArray[cur + 1].charAt(0);
if(strArrayAtPlusOne >= 97 && strArrayAtPlusOne <= 122) {
strArrayAtPlusOne = strArrayAtPlusOne - 32;
}
if(strArrayAt > strArrayAtPlusOne) {
String tempValue = strArray[cur];
strArray[cur] = strArray[cur + 1];
strArray[cur + 1] = tempValue;
}
}
for(cur = limit; --cur >= start;) {
int strArrayAt = (int) strArray[cur].charAt(0);
if(strArrayAt >= 97 && strArrayAt <= 122) {
strArrayAt = strArrayAt - 32;
}
int strArrayAtPlusOne = (int) strArray[cur + 1].charAt(0);
if(strArrayAtPlusOne >= 97 && strArrayAtPlusOne <= 122) {
strArrayAtPlusOne = strArrayAtPlusOne - 32;
}
if(strArrayAt > strArrayAtPlusOne) {
String tempValue = strArray[cur];
strArray[cur] = strArray[cur + 1];
strArray[cur + 1] = tempValue;
}
}
start++;
limit--;
}
return strArray;
}
}
O bubble bidirecional ainda esta ganhando.
Se nao me engano, no site da sun tinha 3 applets, cada um ordenava de um jeito…e acho que o bi era o mais rapido (motivo de eu usar ele).
Abs.
M
Cacete, to floodando aqui hoje 
Achei o link:
http://java.sun.com/applets/jdk/1.4/demo/applets/SortDemo/example1.html
Detalhe: o bubble sort parece estar perdendo nesse caso.
Talvez tenha vantagem e desvantagem em bubble X quicksort, ou seu algoritmo esteja mal escrito (pra ser sincero nem li ele direito, so olhei por cima).
Talvez o bubble bidi execute mais rapido que o quick em iteracoes pequenas (tipo a meia duzia de numeros que coloquei pra ordenar), mas peque na escalabilidade (ordenar em milhoes), enquanto o sort apanhe nos dados pequenos, mas não exponencie tão alto…
Enfim, sei lá, mas vou parar de brincar com os códigos por hoje por que preciso dormir
M
Esse é o bubble bidirecional.
O quicksort provavelmente é linear.
M
http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html
Mais um link legal.
Vendo o O-E Tran. Sort e o Shear Sort, só tenho uma coisa a dizer:
PQP
Absolutamente foda.
O shear sort deve ser no minimo 5 vezes mais rapido que o quick, que é no minimo 4 vezes mais rapido que o bubble (nos testes que fiz, por que varia obviamente de acordo com a quantidade)
Enfim…
Acho que vou brincar de fazer algoritmo rapido depois, pra ver se aproximo pelo menos do Shear Sort…(até parece né, a matemática envolvida é monstruosa, mas enfim, é legal “brincar” disso)
F
tipo, o seu bublesort esta sendo amis rapido pelos seguintes motivos:
:arrow: a comparacao, vc esta comparando soh a primeira letra, enquanto eu estou chamando um metodo da classe String para fazer isso, esse metodo vai continuar comparando se as letras forem iguais, e lembre-se chamada a metodo tb consome tempo
:arrow: esse ex eu fiz como um ex, eu postei desse jeito pra vcs verem como funciona, desse jeito fica MUITO mais rapido:
public void quicksort(int p, int q, String array[]){
if (p < q){
int j = p - 1;
String aux = array[q];
for (int i = p; i <= q; i++){
if (array[i].compareTo(aux) <= 0){
String aux2 = array[i];
array[i] = array[++j];
array[j] = aux2;
}
}
quicksort(p, j - 1, array);
quicksort(j + 1, q, array);
}
}
e tipo, teste denovo, soh q agora com o seguinte array:
String array[] = {"aaz", "aa16", "aah", "a716", "bah", "182", "132"};
vc vai verificar q o seu codigo vai reconhecer “aaz” como igual a “aa16”…
M
tipo, o seu bublesort esta sendo amis rapido pelos seguintes motivos::arrow: a comparacao, vc esta comparando soh a primeira letra, enquanto eu estou chamando um metodo da classe String para fazer isso, esse metodo vai continuar comparando se as letras forem iguais, e lembre-se chamada a metodo tb consome tempo
:arrow: esse ex eu fiz como um ex, eu postei desse jeito pra vcs verem como funciona, desse jeito fica MUITO mais rapido:
public void quicksort(int p, int q, String array[]){ if (p < q){ int j = p - 1; String aux = array[q]; for (int i = p; i <= q; i++){ if (array[i].compareTo(aux) <= 0){ String aux2 = array[i]; array[i] = array[++j]; array[j] = aux2; } } quicksort(p, j - 1, array); quicksort(j + 1, q, array); } }e tipo, teste denovo, soh q agora com o seguinte array:
String array[] = {"aaz", "aa16", "aah", "a716", "bah", "182", "132"};vc vai verificar q o seu codigo vai reconhecer “aaz” como igual a “aa16”…
Depois testo essa sua versão, e sobre a ordenação, sim, foi o que eu disse, mas nesse caso a solucao teria sido a melhor (ordenar so a primeira letra), ou ate mesmo se fosse um int [], afinal, é só o número pra comparar…depois vejo se testo mesmo…depois de ver o shear sort não tem nem por que discutir velocidade de bubble e quick
Além do que a fórmula diz tudo:
Bubble Sort is a sequential algorithm, with an average case time of O(n2).
Quick Sort is a sequential algorithm, with an average case time of O(n log n).
Odd-Even Transposition Sort is a parallel algorithm, with an worst case time of O(n), running on n processors. Its absolute speed up is O(log n), so its efficiency is O((log n)/n).
Shear Sort is a parallel algorithm, with an worst case time of O(n1/2 log n), running on n processors. Its absolute speed up is O(n1/2), so its efficiency is O(1/n1/2).
F
jah adiantando com um teste q eu fiz:
Buble tempo: 1499
Array:
182 132 aaz aa16 aah a716 bah
Quicksort tempo: 1248
Array:
132 182 a716 aa16 aah aaz bah
OBS: note que o seu buble sort n organiza apartir da segunda letra, ao contrario do quicksort, por isso ele esta conseguindo um desempenho um pouco maior do q um bublesort teria, pois n esta organizando devidamente…
cheguei nisso com esse codigo:
public class Teste{
public static void main(String args[]){
String array[], copia[] = {"aaz", "aa16", "aah", "a716", "bah", "182", "132"};
long ms = 0;
array = new String[copia.length];
copia(array, copia);
ms = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++){
copia(array, copia);
bubble(array);
}
System.out.println("Buble tempo: " + (System.currentTimeMillis() - ms));
System.out.println("Array: ");
for (int i = 0; i < array.length; i++) System.out.print(array[i] + " ");
System.out.println();
ms = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++){
copia(array, copia);
quicksort(0, array.length - 1, array);
}
System.out.println("Quicksort tempo: " + (System.currentTimeMillis() - ms));
System.out.println("Array: ");
for (int i = 0; i < array.length; i++) System.out.print(array[i] + " ");
System.out.println();
}
public static void copia(String array[], String copia[]){
for (int i = 0; i < array.length; i++) array[i] = copia[i];
}
public static void quicksort(int p, int q, String array[]){
if (p < q){
int j = p - 1;
String aux = array[q];
for (int i = p; i <= q; i++){
if (array[i].compareTo(aux) <= 0){
String aux2 = array[i];
array[i] = array[++j];
array[j] = aux2;
}
}
quicksort(p, j - 1, array);
quicksort(j + 1, q, array);
}
}
public static String[] bubble(String[] strArray){
int cur = 0;
int limit = strArray.length - 1;
int start = 0;
while(start < limit) {
for(cur = start; cur < limit; cur++) {
int strArrayAt = (int) strArray[cur].charAt(0);
if(strArrayAt >= 97 && strArrayAt <= 122) {
strArrayAt = strArrayAt - 32;
}
int strArrayAtPlusOne = (int) strArray[cur + 1].charAt(0);
if(strArrayAtPlusOne >= 97 && strArrayAtPlusOne <= 122) {
strArrayAtPlusOne = strArrayAtPlusOne - 32;
}
if(strArrayAt > strArrayAtPlusOne) {
String tempValue = strArray[cur];
strArray[cur] = strArray[cur + 1];
strArray[cur + 1] = tempValue;
}
}
for(cur = limit; --cur >= start;) {
int strArrayAt = (int) strArray[cur].charAt(0);
if(strArrayAt >= 97 && strArrayAt <= 122) {
strArrayAt = strArrayAt - 32;
}
int strArrayAtPlusOne = (int) strArray[cur + 1].charAt(0);
if(strArrayAtPlusOne >= 97 && strArrayAtPlusOne <= 122) {
strArrayAtPlusOne = strArrayAtPlusOne - 32;
}
if(strArrayAt > strArrayAtPlusOne) {
String tempValue = strArray[cur];
strArray[cur] = strArray[cur + 1];
strArray[cur + 1] = tempValue;
}
}
start++;
limit--;
}
return strArray;
}
}
OBS: tanto no quicksort como no buble eu copiei o array antigo, por como em arrays eh passado por referencia, n faz sentido organizar um array jah organizado, se for organizar arrays jah organizados o bubble sort provavelmente teria um desempenho mais proximo (ou talvez ateh melhor) q o quicksort, jah q o quicksort faz trocas com elementos iguals enquanto o bubblesort nao, por isso q eu n digo q o quicksort eh o mais rapido, e sim um dos mais rapidos, pq dependendo da situacao pode ser um outro metodo de ordenacao o mais apropriado 
M
jah adiantando com um teste q eu fiz:Buble tempo: 1499 Array: 182 132 aaz aa16 aah a716 bah Quicksort tempo: 1248 Array: 132 182 a716 aa16 aah aaz bahOBS: note que o seu buble sort n organiza apartir da segunda letra, ao contrario do quicksort, por isso ele esta conseguindo um desempenho um pouco maior do q um bublesort teria, pois n esta organizando devidamente…
cheguei nisso com esse codigo:
public class Teste{ public static void main(String args[]){ String array[], copia[] = {"aaz", "aa16", "aah", "a716", "bah", "182", "132"}; long ms = 0; array = new String[copia.length]; copia(array, copia); ms = System.currentTimeMillis(); for (int i = 0; i < 1000000; i++){ copia(array, copia); bubble(array); } System.out.println("Buble tempo: " + (System.currentTimeMillis() - ms)); System.out.println("Array: "); for (int i = 0; i < array.length; i++) System.out.print(array[i] + " "); System.out.println(); ms = System.currentTimeMillis(); for (int i = 0; i < 1000000; i++){ copia(array, copia); quicksort(0, array.length - 1, array); } System.out.println("Quicksort tempo: " + (System.currentTimeMillis() - ms)); System.out.println("Array: "); for (int i = 0; i < array.length; i++) System.out.print(array[i] + " "); System.out.println(); } public static void copia(String array[], String copia[]){ for (int i = 0; i < array.length; i++) array[i] = copia[i]; } public static void quicksort(int p, int q, String array[]){ if (p < q){ int j = p - 1; String aux = array[q]; for (int i = p; i <= q; i++){ if (array[i].compareTo(aux) <= 0){ String aux2 = array[i]; array[i] = array[++j]; array[j] = aux2; } } quicksort(p, j - 1, array); quicksort(j + 1, q, array); } } public static String[] bubble(String[] strArray){ int cur = 0; int limit = strArray.length - 1; int start = 0; while(start < limit) { for(cur = start; cur < limit; cur++) { int strArrayAt = (int) strArray[cur].charAt(0); if(strArrayAt >= 97 && strArrayAt <= 122) { strArrayAt = strArrayAt - 32; } int strArrayAtPlusOne = (int) strArray[cur + 1].charAt(0); if(strArrayAtPlusOne >= 97 && strArrayAtPlusOne <= 122) { strArrayAtPlusOne = strArrayAtPlusOne - 32; } if(strArrayAt > strArrayAtPlusOne) { String tempValue = strArray[cur]; strArray[cur] = strArray[cur + 1]; strArray[cur + 1] = tempValue; } } for(cur = limit; --cur >= start;) { int strArrayAt = (int) strArray[cur].charAt(0); if(strArrayAt >= 97 && strArrayAt <= 122) { strArrayAt = strArrayAt - 32; } int strArrayAtPlusOne = (int) strArray[cur + 1].charAt(0); if(strArrayAtPlusOne >= 97 && strArrayAtPlusOne <= 122) { strArrayAtPlusOne = strArrayAtPlusOne - 32; } if(strArrayAt > strArrayAtPlusOne) { String tempValue = strArray[cur]; strArray[cur] = strArray[cur + 1]; strArray[cur + 1] = tempValue; } } start++; limit--; } return strArray; } }OBS: tanto no quicksort como no buble eu copiei o array antigo, por como em arrays eh passado por referencia, n faz sentido organizar um array jah organizado, se for organizar arrays jah organizados o bubble sort provavelmente teria um desempenho mais proximo (ou talvez ateh melhor) q o quicksort, jah q o quicksort faz trocas com elementos iguals enquanto o bubblesort nao, por isso q eu n digo q o quicksort eh o mais rapido, e sim um dos mais rapidos, pq dependendo da situacao pode ser um outro metodo de ordenacao o mais apropriado
Sim, no ultimo post que coloquei, usei cópia ( .clone() ) pois estava usando por referencia no comeco e nem tinha percebido…tipo, na primeira rodada ja estava tudo organizado e ai o bench era inutil, mas no ultimo codigo que coloquei esta usando clonando o negocio e fazendo tudo direitinho…
O meu bubble so ve o primeiro caractere mesmo.
Vou rodar seu codigo agora aqui e tentar escrever alguma coisa mais rapida so por diversao mesmo (com certeza nao vou conseguir, mas enfim…)…
M
Ah, agora que vi o que voce quis dizer, realmente, ele estava usando o mesmo array ja ordenado…ugh, foi o sono
Mas…(versao ja esta vindo)
M
Ah, agora que vi o que voce quis dizer, realmente, ele estava usando o mesmo array ja ordenado…ugh, foi o sonoMas…(versao ja esta vindo)
public class Bench {
public static void main(String [] args) {
String [] array = {"aaz", "aa16", "aah", "a716", "bah", "182", "132"};
String [] copia = array.clone();
long str, end;
str = System.currentTimeMillis();
for(int i = 0; i < 250000; i++) {
copia = array.clone();
bubble(copia);
}
end = System.currentTimeMillis();
System.out.println("Buble tempo: " + (end - str));
System.out.println("Array: ");
for(int i = 0; i < array.length; i++)
System.out.print(array[i] + " ");
System.out.println();
str = System.currentTimeMillis();
for(int i = 0; i < 250000; i++) {
copia = array.clone();
quicksort(0, array.length - 1, array);
}
end = System.currentTimeMillis();
System.out.println("Quicksort tempo: " + (end - str));
System.out.println("Array: ");
for(int i = 0; i < array.length; i++)
System.out.print(array[i] + " ");
System.out.println();
}
public static void quicksort(int p, int q, String array[]){
if(p < q) {
int j = p - 1;
String aux = array[q];
for(int i = p; i <= q; i++) {
if(array[i].compareTo(aux) <= 0) {
String aux2 = array[i];
array[i] = array[++j];
array[j] = aux2;
}
}
quicksort(p, j - 1, array);
quicksort(j + 1, q, array);
}
}
public static String[] bubble(String[] strArray){
int cur = 0;
int limit = strArray.length - 1;
int start = 0;
while(start < limit) {
for(cur = start; cur < limit; cur++) {
int strArrayAt = (int) strArray[cur].charAt(0);
if(strArrayAt >= 97 && strArrayAt <= 122) {
strArrayAt = strArrayAt - 32;
}
int strArrayAtPlusOne = (int) strArray[cur + 1].charAt(0);
if(strArrayAtPlusOne >= 97 && strArrayAtPlusOne <= 122) {
strArrayAtPlusOne = strArrayAtPlusOne - 32;
}
if(strArrayAt > strArrayAtPlusOne) {
String tempValue = strArray[cur];
strArray[cur] = strArray[cur + 1];
strArray[cur + 1] = tempValue;
}
}
for(cur = limit; --cur >= start;) {
int strArrayAt = (int) strArray[cur].charAt(0);
if(strArrayAt >= 97 && strArrayAt <= 122) {
strArrayAt = strArrayAt - 32;
}
int strArrayAtPlusOne = (int) strArray[cur + 1].charAt(0);
if(strArrayAtPlusOne >= 97 && strArrayAtPlusOne <= 122) {
strArrayAtPlusOne = strArrayAtPlusOne - 32;
}
if(strArrayAt > strArrayAtPlusOne) {
String tempValue = strArray[cur];
strArray[cur] = strArray[cur + 1];
strArray[cur + 1] = tempValue;
}
}
start++;
limit--;
}
return strArray;
}
}
O bubble ainda está ganhando, MAS, reconheco que ele so ordena o primeiro caractere, e por isso, apesar de ser mais rápido NESSE caso, é obviamente menos eficiente (se comparasse todos caracteres, nesse caso, em que a string tem em media 3 letras, provavelmente demoraria o triplo).
Agora vou tentar fazer uma versao fuçada de um algoritmo que imaginei na hora fertil do dia (banheiro).
M
Detalhes constadados:
#1: Em um char só (“a”, “b”, “z”, “i”, “u”, “o”) a performance é quase igual (em um array pequeno, pois o bubble quanto maior o array, mais lento).
#2: A sua implementação considera que o ‘E’ vem antes do ‘a’ (normalmente isso não é bom, depende da aplicação).
F
tipo, vc n pode esquecer q o algoritimo eh de ordenacao, e nao de comparacao de Strings, portanto qndo se vai fazer ot este de qual algoritimo eh mais rapido, se usa int, dai eh soh x > y e pronto…
e como vc disse, o buble sort fica lento com arrays muito grandes, depois posto um teste aki para ilustrar isso… por isso q eu prefiro o quicksort, pq com arrays pequenos, a diferenca vai ser de alguns ms (talvez alguns poucos nano segundos), algo q nem vai dar pra notar a diferenca, e agora se o array tiver, por ex 10000 elementos, a deferenca vai ser grande, de varios segundos, dependendo do computador talvez ateh minutos!!!
e como eu jah disse, em cada situacao um metodo eh mais indicado, por ex, se vc tiver uma lista q jah esta organizada, e vc quiser adicionar um novo elemento na sequencia, se vc fizer um insertionsort sem o loop externo, vai ser MUITO mais rapido do q qquer outro metodo citado neste topico!
F
fiz um teste agora usando inteiros em q a diferenca ficou bem evidente:
quicksort levou 33 milisegundos e bublesort levou mais de 84 segundos, uma diferenca maior q 2000x!!!
usei esse codigo pra esse teste:
OBS: alterei seu codigo para funcionar com inteiros, caso eu tenha cometido algum equivoco ou deserrumado algo sem querer me avise
public class Teste{
public static void main(String args[]){
long ms;
int array[], copia[] = geraArray(100000);
array = new int[copia.length];
copia(array, copia);
ms = System.currentTimeMillis();
quicksort(0, array.length - 1, array);
System.out.println("Quicksort: " + (System.currentTimeMillis() - ms));
copia(array, copia);
ms = System.currentTimeMillis();
bubble(array);
System.out.println("Bubble: " + (System.currentTimeMillis() - ms));
}
public static void copia(int array[], int copia[]){
for (int i = 0; i < array.length; i++){
array[i] = copia[i];
}
}
public static int[] geraArray(int size){
int array[] = new int[size];
for (int i = 0; i < size; i++){
array[i] = (int)(Math.random() * size);
}
return array;
}
public static void quicksort(int p, int q, int array[]){
if (p < q){
int j = p - 1;
int aux = array[q];
for (int i = p; i <= q; i++){
if (array[i] <= aux){
int aux2 = array[i];
array[i] = array[++j];
array[j] = aux2;
}
}
quicksort(p, j - 1, array);
quicksort(j + 1, q, array);
}
}
public static int[] bubble(int[] intArray){
int cur = 0;
int limit = intArray.length - 1;
int start = 0;
while(start < limit) {
for(cur = start; cur < limit; cur++) {
if(intArray[cur] > intArray[cur + 1]) {
int tempValue = intArray[cur];
intArray[cur] = intArray[cur + 1];
intArray[cur + 1] = tempValue;
}
}
for(cur = limit; --cur >= start;) {
if(intArray[cur] > intArray[cur + 1]) {
int tempValue = intArray[cur];
intArray[cur] = intArray[cur + 1];
intArray[cur + 1] = tempValue;
}
}
start++;
limit--;
}
return intArray;
}
}
outra observacao, vc n precisa retornar o array, pois os arrays sao passados por referencia, entaum as modificacoes feitas no metodo vao afetar o array original (por isso q eh feita uma copia)…
qndo estavamos comparando strings a diferenca era pequena (e o bublesort chegava a ser mais rapido), pq alem de estarmos usando arrays muito pequenos (onde ainda assim o quicksort eh mais rapido, a nao ser claro se for um array de 1 ou 2 elementos), vc estava comparando apenas o primeiro caractere, como eu jah disse inumeras vezes, vc tb pode comparar apenas o primeiro caractere usando o quicksort, vai ficar ainda mais rapido, mas eu aconcelho suar o metodo compareTo que compara as strings ateh achar qual eh a q vem antes…
O
import java.util.*;
public class teste {
public static void main(String[] args) {
String a[] = {“Maria”, “Joao”, “Renan”};
List lista = Arrays.asList(a);
Collections.sort(lista);
System.out.println(lista);
}
}
Seguindo este exemplo mais simples que ja me basta ^^ nesta parte aqui oh “String a[] = {“Maria”, “Joao”, “Renan”};” eu gostaria de nao por maria, joao … eu ja tenho Titulos de livros para por ae que apresentam em outro Array ^^ como poderia jogar ali ? vamos supor …
Livros temp = new Livros();
temp = (Livros) lista_de_livros[i];
for (int i = 0; i < 10; i++)
{
String a[] = temp.getTitulo();
}
porém nao funciona desta forma =/
J
neste seu trecho voce quer pegar os titulos e preencher na ordem o vetor a que voce esta criando??
Livros temp = new Livros();
temp = (Livros) lista_de_livros[i];
for (int i = 0; i < 10; i++)
{
String a[] = temp.getTitulo();
}
entao voce deveria trazer a instancia de “a” para fora do laço, pois ele esta iterando isso vai dar erro de compilacao… e colocar o indice no vetor temp para pegar o titulo e entao colocar no “a”.
String[] a = new String[temp.length];
for(;;){
a = temp[i].get();
}
entendeu!
M
fiz um teste agora usando inteiros em q a diferenca ficou bem evidente:quicksort levou 33 milisegundos e bublesort levou mais de 84 segundos, uma diferenca maior q 2000x!!!
usei esse codigo pra esse teste:
OBS: alterei seu codigo para funcionar com inteiros, caso eu tenha cometido algum equivoco ou deserrumado algo sem querer me avise
public class Teste{ public static void main(String args[]){ long ms; int array[], copia[] = geraArray(100000); array = new int[copia.length]; copia(array, copia); ms = System.currentTimeMillis(); quicksort(0, array.length - 1, array); System.out.println("Quicksort: " + (System.currentTimeMillis() - ms)); copia(array, copia); ms = System.currentTimeMillis(); bubble(array); System.out.println("Bubble: " + (System.currentTimeMillis() - ms)); } public static void copia(int array[], int copia[]){ for (int i = 0; i < array.length; i++){ array[i] = copia[i]; } } public static int[] geraArray(int size){ int array[] = new int[size]; for (int i = 0; i < size; i++){ array[i] = (int)(Math.random() * size); } return array; } public static void quicksort(int p, int q, int array[]){ if (p < q){ int j = p - 1; int aux = array[q]; for (int i = p; i <= q; i++){ if (array[i] <= aux){ int aux2 = array[i]; array[i] = array[++j]; array[j] = aux2; } } quicksort(p, j - 1, array); quicksort(j + 1, q, array); } } public static int[] bubble(int[] intArray){ int cur = 0; int limit = intArray.length - 1; int start = 0; while(start < limit) { for(cur = start; cur < limit; cur++) { if(intArray[cur] > intArray[cur + 1]) { int tempValue = intArray[cur]; intArray[cur] = intArray[cur + 1]; intArray[cur + 1] = tempValue; } } for(cur = limit; --cur >= start;) { if(intArray[cur] > intArray[cur + 1]) { int tempValue = intArray[cur]; intArray[cur] = intArray[cur + 1]; intArray[cur + 1] = tempValue; } } start++; limit--; } return intArray; } }outra observacao, vc n precisa retornar o array, pois os arrays sao passados por referencia, entaum as modificacoes feitas no metodo vao afetar o array original (por isso q eh feita uma copia)…
qndo estavamos comparando strings a diferenca era pequena (e o bublesort chegava a ser mais rapido), pq alem de estarmos usando arrays muito pequenos (onde ainda assim o quicksort eh mais rapido, a nao ser claro se for um array de 1 ou 2 elementos), vc estava comparando apenas o primeiro caractere, como eu jah disse inumeras vezes, vc tb pode comparar apenas o primeiro caractere usando o quicksort, vai ficar ainda mais rapido, mas eu aconcelho suar o metodo compareTo que compara as strings ateh achar qual eh a q vem antes…
Eu ja desencanei do bubble, estou brincando com o meu proprio =]
Tive duas ideias, um vou chamar de chunk sorting e o outro sei la do que…
Organizando um array de int de 10 caracteres, o meu metodo esta 3x mais rapido que o quicksort por enquanto =]
Mas nao esta ordenando direito (bugs)…
A outra versao que pretendo fazer (o chunk sorting), nao sei por que, mas acho que ele vai usar o mesmo esquema do Shear Sort…sei la (vendo o applet deles funcionando, da impressao que o que é feito é a mesma coisa que pensei…mas acho que foi subconsciente, por que so pensei depois de ver :P)…
E sobre retornar o array, isso é verdade, MASSSSSSS
Fica muito feio algo como
String [] arr = new String[] {“abc”, “def”, “ghi”}.
sort(arr);
arr = Util.sort(arr); fica mais elegante e mais orientado a objeto, alem de ser padrao (todos os outros metodos retornariam algo…)…
E em termos de performance nao acho que faca diferenca, ja que retorna a referencia que ja tenho…
F
posta ai o codigo q vc ta fazendo… agora fiquei curioso ehhehehehe e qm sabe posso te ajudar a arrumar os bugs
M
Eu já devo ter perdido umas 2 horas nele…
A idéia é meio que sei lá, como se fosse um bubble feito em pequenos pedaços, ligados por elos (mas não é esse o que chamarei de chunk hehe, o de chunk vai ser meio que por estatistica de numero, pra determinar em que lugar do array deve ir o numero e etc)…
Seria algo como
[telefone removido]
Na vertical =
9
0
2
3
1
5
7
4
6
8
Tipo, vou tentar mostrar o que deve acontecer (e no programa eu tinha comecado a imprimir na tela pra ver o que acontece…vou identar usando — aqui)
0
2
3
9 — 1
----- 5
----- 7
----- 9 — 4
----------- 6
----------- 8
----------- 9
isso vai ficar
0
2
3
1
5
7
4
6
8
9
Essa é a primeira iteração (com as sub-iteracoes)…ai vem a segunda, comecando do seguro caractere:
0
1
2
3
5 — 4
----- 5
----- 6
----- 7 — 8
----------- 9
E fica [telefone removido]
Já foi ordenada completamente na segunda iteracao, mas caso nao fosse, seria ordenado no máximo na quarta, que é quando fecharia o elo dos caracteres (tipo, o primeiro comeca do primeiro caractere, depois comeca do segundo, depois do terceiro, depois faz uma ultima rodada com o primeiro)…
É isso hehe aí esta o codigo =)
public static void bubble(char [] chrArr) {
int cur = 0;
int count = chrArr.length;
// usado como 4 apenas pra testes, deve ser determinado automaticamente
int divisor = 4;
int loops = (int) Math.ceil(count / (double) divisor);
// loop principal do pedaco
System.out.println("Len: " + count + ", " + "Loops: " + loops);
for(int w = 0; w < loops; w++) {
int str = ((w + 1) * divisor) - 4 - (1 * w);
int end = str + 3;
System.out.println("Loop principal: " + str + " a " + end);
// loop para comparar cada caractere do chunk
for(int x = 0; x < 3; x++) {
// sum = indice do caractere do chunk
int sum = w + x;
// caractere sendo comparado
char chr = chrArr[sum];
// indice atual do caractere
int idx = sum;
System.out.println("\t" + sum + "," + chr);
for(int y = 0; y < 3; y++) {
char nxt = chrArr[w + y];
if(chr > nxt) {
idx = y;
}
}
if(idx != sum) {
chrArr[sum] = chrArr[idx];
chrArr[idx] = chr;
}
}
}
for(int x = 0; x < chrArr.length; x++) {
System.out.print(chrArr[x] + " ");
}
System.exit(0);
}
F
qnto ao site da sun q falava sobre os metodos de ordenacao, eu dei uma olhada, e fiz um testezinho basico (jah aproveitei pra por o insertionsort junto no teste), pelo que eu vi lah, o quicksort deles estava diferente do q eu uso, e pior, eu testei o deles e caiu em um loop infinito (bem, pelo menos tava demorando uns 30 sec pra organizar um array de 10 elementos hehehehe), e por isso fiz o teste com o quicksort q eu uso, pelos meus testes, o quicksort eh MUITO mais rapido q o shearsort… vejam o resultado:
OBS: a JVM soh libera 64MB de memoria, por isso qndo fui usar 10000000 elementos a memoria esgotou… mas notem a GRANDE diferenca, enquanto o shearsort levou mais de 10 minutos, enquanto o quicksort n levou nem meio segundo (os outros eu “travei” pq se n iam demorar muito hehehehe, o shearsort eu ia travar depois desse, se n tivesse o problema da memoria, e veria ateh onde o quicksort vai)
bem, com esse teste vi uma coisa: o quicksort faz juz ao “quick” que leva no nome
segue o codigo (ta compridinho):
public class Teste{
public static void main(String args[]){
long ms;
int array[], copia[];
for (int i = 0; i < 8; i++){
copia = geraArray((int)Math.pow(10, i));
array = new int[copia.length];
System.out.println("NUMERO DE ELEMENTOS: " + array.length);
copia(array, copia);
if (i < 6){
ms = System.currentTimeMillis();
bubblesort(array);
System.out.println("BubbleSort: " + (System.currentTimeMillis() - ms));
copia(array, copia);
ms = System.currentTimeMillis();
oddevensort(array);
System.out.println("OddEvenSort: " + (System.currentTimeMillis() - ms));
copia(array, copia);
ms = System.currentTimeMillis();
insertionsort(array);
System.out.println("InsertionSort: " + (System.currentTimeMillis() - ms));
copia(array, copia);
}
else{
System.out.println("BubbleSort: um monte");
System.out.println("OddEvenSort: um monte");
System.out.println("InsertionSort: um monte");
}
if (i < 7){
ms = System.currentTimeMillis();
shearsort(array);
System.out.println("ShearSort: " + (System.currentTimeMillis() - ms));
copia(array, copia);
}
else System.out.println("ShearSort: um monte");
ms = System.currentTimeMillis();
quicksort(0, array.length - 1, array);
System.out.println("QuickSort: " + (System.currentTimeMillis() - ms));
System.out.println();
}
}
public static void copia(int array[], int copia[]){
for (int i = 0; i < array.length; i++){
array[i] = copia[i];
}
}
public static int[] geraArray(int size){
int array[] = new int[size];
for (int i = 0; i < size; i++){
array[i] = (int)(Math.random() * size);
}
return array;
}
public static void insertionsort(int array[]){
int h, aux;
for (int i = 1; i < array.length; i++){
h = i - 1;
aux = array[i];
while (h >= 0 && aux < array[h]){
int aux2 = array[h];
array[h] = array[h + 1];
array[h + 1] = aux2;
h--;
}
}
}
static void oddevensort(int a[]){
for (int i = 0; i < a.length/2; i++ ) {
for (int j = 0; j+1 < a.length; j += 2)
if (a[j] > a[j+1]) {
int T = a[j];
a[j] = a[j+1];
a[j+1] = T;
}
for (int j = 1; j+1 < a.length; j += 2)
if (a[j] > a[j+1]) {
int T = a[j];
a[j] = a[j+1];
a[j+1] = T;
}
}
}
public static void quicksort(int p, int q, int array[]){
if (p < q){
int j = p - 1;
int aux = array[q];
for (int i = p; i <= q; i++){
if (array[i] <= aux){
int aux2 = array[i];
array[i] = array[++j];
array[j] = aux2;
}
}
quicksort(p, j - 1, array);
quicksort(j + 1, q, array);
}
}
public static void bubblesort(int[] array){
for (int i = array.length; --i >= 0;){
for (int j = 0; j < i; j++){
if (array[j] > array[j + 1]){
int aux = array[j];
array[j] = array[j + 1];
array[j + 1] = aux;
}
}
}
}
private static int Log, Rows, Cols;
static void shearsort(int a[]){
int pow=1, div=1;
int h[];
for(int i=1; i*i<=a.length; i++)
if (a.length % i == 0) div = i;
Rows = div; Cols = a.length / div;
for(Log=0; pow<=Rows; Log++)
pow = pow * 2;
h = new int[Rows];
for (int i=0; i<Rows; i++)
h[i]=i*Cols;
for (int k=0; k<Log; k++) {
for (int j=0; j<Cols/2; j++) {
for (int i=0; i<Rows; i++)
sortPart1(a,i*Cols,(i+1)*Cols,1,(i%2==0?true:false));
for (int i=0; i<Rows; i++)
sortPart2(a,i*Cols,(i+1)*Cols,1,(i%2==0?true:false));
}
for (int j=0; j<Rows/2; j++) {
for (int i=0; i<Cols; i++)
sortPart1(a,i,Rows*Cols+i,Cols,true);
for (int i=0; i<Cols; i++)
sortPart2(a,i,Rows*Cols+i,Cols,true);
}
}
for (int j=0; j<Cols/2; j++) {
for (int i=0; i<Rows; i++)
sortPart1(a,i*Cols,(i+1)*Cols,1,true);
for (int i=0; i<Rows; i++)
sortPart2(a,i*Cols,(i+1)*Cols,1,true);
}
for (int i=0; i<Rows; i++)
h[i]=-1;
}
private static void sortPart1(int a[], int Lo, int Hi, int Nx, boolean Up){
for (int j = Lo; j+Nx<Hi; j+=2*Nx)
if ((Up && a[j] > a[j+Nx]) || !Up && a[j] < a[j+Nx]) {
int T = a[j];
a[j] = a[j+Nx];
a[j+Nx] = T;
}
}
private static void sortPart2(int a[], int Lo, int Hi, int Nx, boolean Up){
for (int j = Lo+Nx; j+Nx<Hi; j+=2*Nx)
if ((Up && a[j] > a[j+Nx]) || !Up && a[j] < a[j+Nx]) {
int T = a[j];
a[j] = a[j+Nx];
a[j+Nx] = T;
}
}
}
M
qnto ao site da sun q falava sobre os metodos de ordenacao, eu dei uma olhada, e fiz um testezinho basico (jah aproveitei pra por o insertionsort junto no teste), pelo que eu vi lah, o quicksort deles estava diferente do q eu uso, e pior, eu testei o deles e caiu em um loop infinito (bem, pelo menos tava demorando uns 30 sec pra organizar um array de 10 elementos hehehehe), e por isso fiz o teste com o quicksort q eu uso, pelos meus testes, o quicksort eh MUITO mais rapido q o shearsort... vejam o resultado:NUMERO DE ELEMENTOS: 1 BubbleSort: 0 OddEvenSort: 0 InsertionSort: 0 ShearSort: 0 QuickSort: 0NUMERO DE ELEMENTOS: 10
BubbleSort: 0
OddEvenSort: 0
InsertionSort: 0
ShearSort: 0
QuickSort: 0NUMERO DE ELEMENTOS: 100
BubbleSort: 1
OddEvenSort: 2
InsertionSort: 0
ShearSort: 4
QuickSort: 0NUMERO DE ELEMENTOS: 1000
BubbleSort: 7
OddEvenSort: 9
InsertionSort: 5
ShearSort: 5
QuickSort: 2NUMERO DE ELEMENTOS: 10000
BubbleSort: 661
OddEvenSort: 630
InsertionSort: 315
ShearSort: 120
QuickSort: 3NUMERO DE ELEMENTOS: 100000
BubbleSort: 75894
OddEvenSort: 112651
InsertionSort: 36004
ShearSort: 5892
QuickSort: 39NUMERO DE ELEMENTOS: 1000000
BubbleSort: um monte
OddEvenSort: um monte
InsertionSort: um monte
ShearSort: 658970
QuickSort: 403Exception in thread "main" java.lang.OutOfMemoryError
OBS: a JVM soh libera 64MB de memoria, por isso qndo fui usar 10000000 elementos a memoria esgotou... mas notem a GRANDE diferenca, enquanto o shearsort levou mais de 10 minutos, enquanto o quicksort n levou nem meio segundo (os outros eu "travei" pq se n iam demorar muito hehehehe, o shearsort eu ia travar depois desse, se n tivesse o problema da memoria, e veria ateh onde o quicksort vai)
bem, com esse teste vi uma coisa: o quicksort faz juz ao "quick" que leva no nome :grin:
segue o codigo (ta compridinho):
public class Teste{ public static void main(String args[]){ long ms; int array[], copia[]; for (int i = 0; i < 8; i++){ copia = geraArray((int)Math.pow(10, i)); array = new int[copia.length]; System.out.println("NUMERO DE ELEMENTOS: " + array.length); copia(array, copia); if (i < 6){ ms = System.currentTimeMillis(); bubblesort(array); System.out.println("BubbleSort: " + (System.currentTimeMillis() - ms)); copia(array, copia); ms = System.currentTimeMillis(); oddevensort(array); System.out.println("OddEvenSort: " + (System.currentTimeMillis() - ms)); copia(array, copia); ms = System.currentTimeMillis(); insertionsort(array); System.out.println("InsertionSort: " + (System.currentTimeMillis() - ms)); copia(array, copia); } else{ System.out.println("BubbleSort: um monte"); System.out.println("OddEvenSort: um monte"); System.out.println("InsertionSort: um monte"); } if (i < 7){ ms = System.currentTimeMillis(); shearsort(array); System.out.println("ShearSort: " + (System.currentTimeMillis() - ms)); copia(array, copia); } else System.out.println("ShearSort: um monte"); ms = System.currentTimeMillis(); quicksort(0, array.length - 1, array); System.out.println("QuickSort: " + (System.currentTimeMillis() - ms)); System.out.println(); } } public static void copia(int array[], int copia[]){ for (int i = 0; i < array.length; i++){ array[i] = copia[i]; } } public static int[] geraArray(int size){ int array[] = new int[size]; for (int i = 0; i < size; i++){ array[i] = (int)(Math.random() * size); } return array; } public static void insertionsort(int array[]){ int h, aux; for (int i = 1; i < array.length; i++){ h = i - 1; aux = array[i]; while (h >= 0 && aux < array[h]){ int aux2 = array[h]; array[h] = array[h + 1]; array[h + 1] = aux2; h--; } } } static void oddevensort(int a[]){ for (int i = 0; i < a.length/2; i++ ) { for (int j = 0; j+1 < a.length; j += 2) if (a[j] > a[j+1]) { int T = a[j]; a[j] = a[j+1]; a[j+1] = T; } for (int j = 1; j+1 < a.length; j += 2) if (a[j] > a[j+1]) { int T = a[j]; a[j] = a[j+1]; a[j+1] = T; } } } public static void quicksort(int p, int q, int array[]){ if (p < q){ int j = p - 1; int aux = array[q]; for (int i = p; i <= q; i++){ if (array[i] <= aux){ int aux2 = array[i]; array[i] = array[++j]; array[j] = aux2; } } quicksort(p, j - 1, array); quicksort(j + 1, q, array); } } public static void bubblesort(int[] array){ for (int i = array.length; --i >= 0;){ for (int j = 0; j < i; j++){ if (array[j] > array[j + 1]){ int aux = array[j]; array[j] = array[j + 1]; array[j + 1] = aux; } } } } private static int Log, Rows, Cols; static void shearsort(int a[]){ int pow=1, div=1; int h[]; for(int i=1; i*i<=a.length; i++) if (a.length % i == 0) div = i; Rows = div; Cols = a.length / div; for(Log=0; pow<=Rows; Log++) pow = pow * 2; h = new int[Rows]; for (int i=0; i<Rows; i++) h[i]=i*Cols; for (int k=0; k<Log; k++) { for (int j=0; j<Cols/2; j++) { for (int i=0; i<Rows; i++) sortPart1(a,i*Cols,(i+1)*Cols,1,(i%2==0?true:false)); for (int i=0; i<Rows; i++) sortPart2(a,i*Cols,(i+1)*Cols,1,(i%2==0?true:false)); } for (int j=0; j<Rows/2; j++) { for (int i=0; i<Cols; i++) sortPart1(a,i,Rows*Cols+i,Cols,true); for (int i=0; i<Cols; i++) sortPart2(a,i,Rows*Cols+i,Cols,true); } } for (int j=0; j<Cols/2; j++) { for (int i=0; i<Rows; i++) sortPart1(a,i*Cols,(i+1)*Cols,1,true); for (int i=0; i<Rows; i++) sortPart2(a,i*Cols,(i+1)*Cols,1,true); } for (int i=0; i<Rows; i++) h[i]=-1; } private static void sortPart1(int a[], int Lo, int Hi, int Nx, boolean Up){ for (int j = Lo; j+Nx<Hi; j+=2*Nx) if ((Up && a[j] > a[j+Nx]) || !Up && a[j] < a[j+Nx]) { int T = a[j]; a[j] = a[j+Nx]; a[j+Nx] = T; } } private static void sortPart2(int a[], int Lo, int Hi, int Nx, boolean Up){ for (int j = Lo+Nx; j+Nx<Hi; j+=2*Nx) if ((Up && a[j] > a[j+Nx]) || !Up && a[j] < a[j+Nx]) { int T = a[j]; a[j] = a[j+Nx]; a[j+Nx] = T; } } }
Poe o mesmo valor em todos (ao inves de Math.random() ) e o seu quicksort esta dando stack overflow :P
M
qnto ao site da sun q falava sobre os metodos de ordenacao, eu dei uma olhada, e fiz um testezinho basico (jah aproveitei pra por o insertionsort junto no teste), pelo que eu vi lah, o quicksort deles estava diferente do q eu uso, e pior, eu testei o deles e caiu em um loop infinito (bem, pelo menos tava demorando uns 30 sec pra organizar um array de 10 elementos hehehehe), e por isso fiz o teste com o quicksort q eu uso, pelos meus testes, o quicksort eh MUITO mais rapido q o shearsort... vejam o resultado:NUMERO DE ELEMENTOS: 1 BubbleSort: 0 OddEvenSort: 0 InsertionSort: 0 ShearSort: 0 QuickSort: 0NUMERO DE ELEMENTOS: 10
BubbleSort: 0
OddEvenSort: 0
InsertionSort: 0
ShearSort: 0
QuickSort: 0NUMERO DE ELEMENTOS: 100
BubbleSort: 1
OddEvenSort: 2
InsertionSort: 0
ShearSort: 4
QuickSort: 0NUMERO DE ELEMENTOS: 1000
BubbleSort: 7
OddEvenSort: 9
InsertionSort: 5
ShearSort: 5
QuickSort: 2NUMERO DE ELEMENTOS: 10000
BubbleSort: 661
OddEvenSort: 630
InsertionSort: 315
ShearSort: 120
QuickSort: 3NUMERO DE ELEMENTOS: 100000
BubbleSort: 75894
OddEvenSort: 112651
InsertionSort: 36004
ShearSort: 5892
QuickSort: 39NUMERO DE ELEMENTOS: 1000000
BubbleSort: um monte
OddEvenSort: um monte
InsertionSort: um monte
ShearSort: 658970
QuickSort: 403Exception in thread "main" java.lang.OutOfMemoryError
OBS: a JVM soh libera 64MB de memoria, por isso qndo fui usar 10000000 elementos a memoria esgotou... mas notem a GRANDE diferenca, enquanto o shearsort levou mais de 10 minutos, enquanto o quicksort n levou nem meio segundo (os outros eu "travei" pq se n iam demorar muito hehehehe, o shearsort eu ia travar depois desse, se n tivesse o problema da memoria, e veria ateh onde o quicksort vai)
bem, com esse teste vi uma coisa: o quicksort faz juz ao "quick" que leva no nome :grin:
segue o codigo (ta compridinho):
public class Teste{ public static void main(String args[]){ long ms; int array[], copia[]; for (int i = 0; i < 8; i++){ copia = geraArray((int)Math.pow(10, i)); array = new int[copia.length]; System.out.println("NUMERO DE ELEMENTOS: " + array.length); copia(array, copia); if (i < 6){ ms = System.currentTimeMillis(); bubblesort(array); System.out.println("BubbleSort: " + (System.currentTimeMillis() - ms)); copia(array, copia); ms = System.currentTimeMillis(); oddevensort(array); System.out.println("OddEvenSort: " + (System.currentTimeMillis() - ms)); copia(array, copia); ms = System.currentTimeMillis(); insertionsort(array); System.out.println("InsertionSort: " + (System.currentTimeMillis() - ms)); copia(array, copia); } else{ System.out.println("BubbleSort: um monte"); System.out.println("OddEvenSort: um monte"); System.out.println("InsertionSort: um monte"); } if (i < 7){ ms = System.currentTimeMillis(); shearsort(array); System.out.println("ShearSort: " + (System.currentTimeMillis() - ms)); copia(array, copia); } else System.out.println("ShearSort: um monte"); ms = System.currentTimeMillis(); quicksort(0, array.length - 1, array); System.out.println("QuickSort: " + (System.currentTimeMillis() - ms)); System.out.println(); } } public static void copia(int array[], int copia[]){ for (int i = 0; i < array.length; i++){ array[i] = copia[i]; } } public static int[] geraArray(int size){ int array[] = new int[size]; for (int i = 0; i < size; i++){ array[i] = (int)(Math.random() * size); } return array; } public static void insertionsort(int array[]){ int h, aux; for (int i = 1; i < array.length; i++){ h = i - 1; aux = array[i]; while (h >= 0 && aux < array[h]){ int aux2 = array[h]; array[h] = array[h + 1]; array[h + 1] = aux2; h--; } } } static void oddevensort(int a[]){ for (int i = 0; i < a.length/2; i++ ) { for (int j = 0; j+1 < a.length; j += 2) if (a[j] > a[j+1]) { int T = a[j]; a[j] = a[j+1]; a[j+1] = T; } for (int j = 1; j+1 < a.length; j += 2) if (a[j] > a[j+1]) { int T = a[j]; a[j] = a[j+1]; a[j+1] = T; } } } public static void quicksort(int p, int q, int array[]){ if (p < q){ int j = p - 1; int aux = array[q]; for (int i = p; i <= q; i++){ if (array[i] <= aux){ int aux2 = array[i]; array[i] = array[++j]; array[j] = aux2; } } quicksort(p, j - 1, array); quicksort(j + 1, q, array); } } public static void bubblesort(int[] array){ for (int i = array.length; --i >= 0;){ for (int j = 0; j < i; j++){ if (array[j] > array[j + 1]){ int aux = array[j]; array[j] = array[j + 1]; array[j + 1] = aux; } } } } private static int Log, Rows, Cols; static void shearsort(int a[]){ int pow=1, div=1; int h[]; for(int i=1; i*i<=a.length; i++) if (a.length % i == 0) div = i; Rows = div; Cols = a.length / div; for(Log=0; pow<=Rows; Log++) pow = pow * 2; h = new int[Rows]; for (int i=0; i<Rows; i++) h[i]=i*Cols; for (int k=0; k<Log; k++) { for (int j=0; j<Cols/2; j++) { for (int i=0; i<Rows; i++) sortPart1(a,i*Cols,(i+1)*Cols,1,(i%2==0?true:false)); for (int i=0; i<Rows; i++) sortPart2(a,i*Cols,(i+1)*Cols,1,(i%2==0?true:false)); } for (int j=0; j<Rows/2; j++) { for (int i=0; i<Cols; i++) sortPart1(a,i,Rows*Cols+i,Cols,true); for (int i=0; i<Cols; i++) sortPart2(a,i,Rows*Cols+i,Cols,true); } } for (int j=0; j<Cols/2; j++) { for (int i=0; i<Rows; i++) sortPart1(a,i*Cols,(i+1)*Cols,1,true); for (int i=0; i<Rows; i++) sortPart2(a,i*Cols,(i+1)*Cols,1,true); } for (int i=0; i<Rows; i++) h[i]=-1; } private static void sortPart1(int a[], int Lo, int Hi, int Nx, boolean Up){ for (int j = Lo; j+Nx<Hi; j+=2*Nx) if ((Up && a[j] > a[j+Nx]) || !Up && a[j] < a[j+Nx]) { int T = a[j]; a[j] = a[j+Nx]; a[j+Nx] = T; } } private static void sortPart2(int a[], int Lo, int Hi, int Nx, boolean Up){ for (int j = Lo+Nx; j+Nx<Hi; j+=2*Nx) if ((Up && a[j] > a[j+Nx]) || !Up && a[j] < a[j+Nx]) { int T = a[j]; a[j] = a[j+Nx]; a[j+Nx] = T; } } }Poe o mesmo valor em todos (ao inves de Math.random() ) e o seu quicksort esta dando stack overflow :P
PS: voce pode usar o System.arraycopy para copiar o array (sem ter que ficar gerando e percorrendo ele).
Criado 22 de setembro de 2004
Ultima resposta 28 de set. de 2004
Respostas 36
Participantes 7
Alura O que é Python? — um guia completo para iniciar nessa linguagem de programação Acesse agora o guia sobre Python e inicie sua jornada nessa linguagem de programação: o que é e para que serve, sua sintaxe e como iniciar nela!
Casa do Codigo Engenharia de Prompt para Devs: Um guia para aprender a... Por Ricardo Pupo Larguesa — Casa do Codigo
Fiap Pos-Tech: Arquitetura e Desenvolvimento Java Uma jornada especialmente pensada para profissionais que desejam dar os próximos passos na área...