Mais uma ordenação de array de Strings - Desenvolva o algoritmo!

Programação Java
#1

Olá pessoal,

este tópico trata mais uma vez sobre um assunto que já foi muito discutido aqui no fórum e já tem até um tutorial na comunidade. É só fazer uma busca por “ordenar array” que vocês irão ver.

Este tópico será mais um dentre tantos outros que tratam de ordenação de arrays mas de um caso bem particular: Como ordenar um array de strings numéricos!

A solução aqui apresentada não esta completa e espero que alguém possa complementar a minha solução para que esta fique então a mais eficiente e eficaz possível.

O Problema: Imagine o array

         String numStrings[] = {"20","2","1","11","10","22"};

Se você usar o método ‘Arrays.sort(numStrings)’ você terá o vetor ordenado como {“1”,“10”,“11”,“2”,“20”,“22”} e convenhamos, não é ordenação natural que gostaríamos de obter. A ordenação deveria ser numérica e não lexicográfica.

A ordem lexicográfica entre strings é análoga à ordem das palavras em um dicionário. Ela se baseia na ordenação dos caracteres estabelecida na tabela ISO8859-1, da mesma forma que a ordem das palavras em um dicionário se baseia na ordenação das letras no alfabeto. Para comparar duas strings s e t, procura-se a primeira posição, digamos k, em que as duas strings diferem. Se s[k] vem antes de t[k] na tabela ISO então s é lexicograficamente menor que t.

Mas como obter o vetor ordenado numericamente, {“1”,“2”,“10”,“11”,“20”,“22”} ?

Segue a baixo a minha solução com algumas limitações:

                Arrays.sort(numStrings,new Comparator(){
                        // Este Comparator serve para ordenar strings numéricas em ordem crescente
                        public int compare(Object o1, Object o2) {
                            String str1 = (String)o1;
                            String str2 = (String)o2;
                            
                            // verifica se o primeiro char da string1 é numérico
                            if(Character.isDigit(str1.charAt(0))){
                                // verifica se o primeiro char da string2 é numérico
                                if(Character.isDigit(str2.charAt(0))){
                                    // Somente se ambos forem que é feita a comparação
                                    if( Integer.parseInt(str1) > Integer.parseInt(str2) )
                                        return 1; // -1 se for descrescente
                                    else
                                        return -1; // 1 se for descrescente
                            
                                }
                            }
                            return 0;
                        }
                    }
                );

O código é auto-explicavel.

Como o código a cima é limitado:

  • As strings do vetor só são identificadas como numéricas se estas começarem com um caractere numérico.
  • As strings presentes no vetor devem ser estritamente NUMÉRICAS! Ou seja, strings do tipo “1a”, “2will”, “123_3”, “3.1415” e etc não irá funcionar. Será gerado um erro!
  • As strings numéricas não pode ter parte fracionária. Deve ser números inteiros.

Como melhorar o código a cima:

  • Antes de fazer a comparação, verificar se a string é completamente numérica.
  • Ordenar strings no formato “[chars][ints]”. Algo do tipo {“img1.jpg”,“img2.jpg”,“img10.jpg”,“img11.jpg”,“img20.jpg”,“img22.jpg”} .
  • Poder ordenar strings numéricas com parte fracionária.

É isso ae pessoal. Espero que alguém esteja disposto a incrementar o código que eu sugeri para que este então se torne um bom algoritmo de referência para toda a comunidade.

Abraços.

PS: Se tiver algum erro ae por favor me corrijam! Se tiver alguma outra solução já conhecida por favor divulguem!

#2

Eu sabia que tinha alguma coisa parecida guardada.

import java.util.*;
import java.util.regex.*;

class CompareStrings {
    
    private static Pattern patStartsWithNumber = Pattern.compile ("^\s*([-+]?\d+)\s*");
	
    /**
	 * Compara duas strings, de modo que leve em conta se elas
	 * começam por um valor numérico, e ordene corretamente. 
	 * Por exemplo: "6dias" &lt "12meses".
	 */
    public static int numericCompare (final String s1, final String s2) {

	    Matcher match1 = patStartsWithNumber.matcher (s1);
	    Matcher match2 = patStartsWithNumber.matcher (s2);
		if (match1.find() && match2.find()) {
		    // Aqui vamos comparar os valores numéricos
		    long n1 = Long.parseLong (match1.group().trim());
            long n2 = Long.parseLong (match2.group().trim());
            if (n1 &lt n2) return -1; else if (n1 &gt n2) return +1;
			// Como as partes numéricas batem, devemos checar agora a parte string
			String resto1 = s1.substring (match1.end());
			String resto2 = s2.substring (match2.end());
			return resto1.compareTo(resto2);
		}

		return s1.compareTo(s2);
	}
	
	public static void main(String[] args) {
	    String[] teste = {
		    "12 meses",
		    "6 dias", 
			"10horas",
			"10anos",
			"-10horas",
			"20",
			"Araraquara", // vem depois dos dígitos
			"#bleargh!", // vem antes dos dígitos
		};
		Arrays.sort (teste, new Comparator() {
		     public int compare (Object obj1, Object obj2) {
			     return numericCompare ((String) obj1, (String) obj2);
			 }
		});
		System.out.println (Arrays.asList (teste));
	}
}
#3

Caramba! O Thingol já tava com a solução na ponta dos dedos! :shock:

\o/

Mandou ver!

Alguém mais tem outra sugestão? :?:

#4