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:
[quote=“Felipe”]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:
vc vai verificar q o seu codigo vai reconhecer “aaz” como igual a “aa16”…[/quote]
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).
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
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 [/quote]
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…)…
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).
#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).
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!
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…
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();
}
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();
}
[quote=“Felipe”]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…[/quote]
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…
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
9023157468
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)
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);
}
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;
}
}
}
[quote=“Felipe”]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):
[code]
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;
}
}
}
[/code][/quote]
Poe o mesmo valor em todos (ao inves de Math.random() ) e o seu quicksort esta dando stack overflow
[quote=“mavi”][quote=“Felipe”]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):
[code]
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;
}
}
}
[/code][/quote]
Poe o mesmo valor em todos (ao inves de Math.random() ) e o seu quicksort esta dando stack overflow :P[/quote]
PS: voce pode usar o System.arraycopy para copiar o array (sem ter que ficar gerando e percorrendo ele).
