Ordem alfabética

[omegatigerPJ]

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?

[Rubem_AzenhaPJ]

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
• ???

[omegatigerPJ]

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?

[renan_danielPJ]

Cara o que vc pode estar fazendo é jogando em um ArrayList e executando o sort.

Ex:

[code]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);        
}    

}[/code]

A saida vai estar ordenada…

Te ajudou…?

[maviPJ]

[quote=“renan_daniel”]Cara o que vc pode estar fazendo é jogando em um ArrayList e executando o sort.

Ex:

[code]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);        
}    

}[/code]

A saida vai estar ordenada…

Te ajudou…?[/quote]

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;
}

[omegatigerPJ]

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!

[jack_ganzhaPJ]

Olá, renam, não precisa fazer o for para preencher a List com os objetos do array. Basta fazer assim:

[code]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);
}

}[/code]

[quote=“omegatiger”]Poderia me explicar sobre os valores que apresentou neste seu Sort?

“if(strArrayAt >= 97 && strArrayAt <= 122)” [/quote]
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…

[maviPJ]

[quote=“omegatiger”]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![/quote]

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

[renan_danielPJ]

[quote=“jack_-_ganzha”]Olá, renam, não precisa fazer o for para preencher a List com os objetos do array. Basta fazer assim:

[code]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);
}

}[/code]

Essa eu naum conhecia, valeu…

[FelipePJ]

[quote=“mavi”][quote=“renan_daniel”]Cara o que vc pode estar fazendo é jogando em um ArrayList e executando o sort.

Ex:

[code]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);        
}    

}[/code]

A saida vai estar ordenada…

Te ajudou…?[/quote]

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; } [/quote]

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);

[omegatigerPJ]

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...

[maviPJ]

[quote=“Felipe”][quote=“mavi”][quote=“renan_daniel”]Cara o que vc pode estar fazendo é jogando em um ArrayList e executando o sort.

Ex:

[code]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);        
}    

}[/code]

A saida vai estar ordenada…

Te ajudou…?[/quote]

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; } [/quote]

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); [/quote]

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.

[FelipePJ]

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…

[maviPJ]

[quote=“Felipe”]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…[/quote]

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.

[maviPJ]

[quote=“mavi”][quote=“Felipe”]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…[/quote]

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.[/quote]

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.

[maviPJ]

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.

[maviPJ]

[quote=“mavi”]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.[/quote]

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.

[maviPJ]

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

[maviPJ]

Note: Complexity is O(n2) for arbitrary data, but approaches O(n) if the list is nearly in order at the beginning. Bidirectional bubble sort usually does better than bubble sort since at least one item is moved forward or backward to its place in the list with each pass. Bubble sort moves items forward into place, but can only move items backward one location each pass.

Esse é o bubble bidirecional.

O quicksort provavelmente é linear.

[maviPJ]

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)