A classificação é uma das operações mais comuns e necessárias na programação. Representa a ordenação de algum conjunto de elementos em uma ordem específica. Este artigo é sobre métodos padrão para classificação de arrays em Java.
Resumidamente sobre classificação
Portanto, classificação é a ordenação de um conjunto de dados. No nosso caso, matrizes. O objetivo da classificação de arrays ou outras estruturas de dados é facilitar a localização, manipulação ou análise dos dados na coleção. Os programadores precisam de classificação com tanta frequência que qualquer linguagem de programação inclui métodos integrados para classificar matrizes, listas e outras estruturas de dados ordenadas. Para usar esses métodos, chame-os. A operação é simplificada tanto quanto possível. Normalmente, os métodos integrados são otimizados ao máximo; na maioria dos casos, usá-los em seu trabalho ou projetos é uma boa ideia. No entanto, quase todo programador, durante seus estudos, precisa implementar algoritmos de classificação por conta própria. Portanto, esses exercícios perfeitos ensinam você a compreender a própria essência da programação. Além disso, às vezes você precisa de métodos de classificação não padronizados no trabalho. Existem muitos algoritmos de classificação. Eles têm pontos fortes e fracos dependendo do tipo ou tamanho dos conjuntos de dados. Os algoritmos de classificação padrão incluem classificação por bolha, classificação por seleção, classificação por inserção, classificação por mesclagem e classificação rápida.
Método integrado para classificação de arrays em Java: Arrays.sort
Vamos começar com o mais simples. Alguém já escreveu um método para classificar arrays em Java para nós. Este método está na classe Arrays , mais especificamente java.util.Arrays . Esta classe contém vários métodos para trabalhar com arrays, como classificação e pesquisa. O método Arrays.sort fornece uma maneira conveniente de classificar arrays em Java, independentemente de eles conterem strings, inteiros ou outros elementos. Existem diversas variações do método Arrays.sort em Java. Aqui estão alguns métodos de classificação comumente usados da classe Arrays :
Arrays.sort(Array) : use-o para classificar arrays de tipos primitivos ou objetos em ordem crescente. Ele usa a ordem natural dos elementos.
Arrays.sort(Array, fromIndex, toIndex) : Este método de classificação sobrecarregado permite classificar apenas uma parte do Array especificado pelos parâmetros fromIndex e toIndex.
Arrays.sort(Array, comparator) : este é para classificar arrays de objetos usando um comparador personalizado. O comparador define a ordem dos elementos.
Arrays.parallelSort(Array) : Esta versão do método classifica o Array em paralelo, utilizando vários threads para melhorar o desempenho. É benéfico para classificar grandes matrizes.
Arrays.parallelSort(Array, fromIndex, toIndex) : Esta versão sobrecarregada do método parallelSort permite classificar um intervalo específico de elementos no Array .
Eles permitem organizar rapidamente os elementos com base em sua ordem natural ou usando um comparador personalizado. Vamos explorar esse método com dois exemplos, um deles envolvendo strings.
Exemplo 1: Classificando Strings
Suponha que temos uma variedade de instrumentos musicais de cordas: "violino", "viola", "violoncelo" e "contrabaixo". Podemos usar o método Array.sort para organizá-los em ordem alfabética.
Neste programa, primeiro importamos a classe java.util.Arrays para obter acesso ao método Array.sort . Em seguida, criamos um array de strings chamado instrumentos contendo os nomes dos instrumentos musicais. Depois disso, chamamos Arrays.sort(instruments) . Portanto, este método obtém um array, classifica os elementos em ordem crescente com base em sua ordem natural (alfabética). Finalmente, percorremos o Array classificado e imprimimos cada instrumento.
Exemplo 2: Classificação de números inteiros
Vamos considerar outro exemplo em que classificamos um array de inteiros em ordem crescente.
importjava.util.Arrays;publicclassIntegerSortExample{publicstaticvoidmain(String[] args){int[] numbers ={8,2,7,3,1,5};//sort an array using Arrays.sort Arrays.sort(numbers);System.out.println("Sorted Numbers:");for(int number : numbers){System.out.println(number);}}}
Saída:
Números classificados: 1 2 3 5 7 8
Aqui criamos uma matriz inteira chamada números com vários elementos não classificados. A seguir, chamamos Arrays.sort(numbers) para classificar um array em ordem crescente. Observe que o método Array.sort modifica o array original no local. Portanto, para manter o Array original , faça uma cópia antes de classificar.
Exemplo 3: ordem decrescente
E quanto à classificação decrescente? Também é fácil com Arrays.sort . Basta usar um comparador personalizado. Aqui está um exemplo:
importjava.util.Arrays;importjava.util.Comparator;//Arrays.sort with custom comparator example publicclassDescendingSortExample{publicstaticvoidmain(String[] args){Integer[] numbers ={8,2,7,3,1,5};//sort an Array using Arrays.sort Arrays.sort(numbers,Comparator.reverseOrder());System.out.println("Sorted Numbers (Descending):");for(int number : numbers){System.out.println(number);}}}
A saída é a próxima:
Números classificados (descendente): 8 7 5 3 2 1
Aqui temos uma matriz de inteiros chamados números. Ao passar Comparator.reverseOrder() como segundo argumento para o método Arrays.sort , especificamos um comparador personalizado que classifica os elementos em ordem decrescente. O método Comparator.reverseOrder() retorna um comparador que inverte a ordem natural dos elementos. Observe que aqui usamos a classe wrapper Integer em vez do tipo primitivo int porque o método Comparator.reverseOrder() requer objetos. Se você tiver uma matriz de valores int primitivos, também precisará convertê-los em objetos Integer antes de usar essa abordagem. Usando um comparador personalizado, você pode classificar facilmente o array em ordem decrescente usando o método Arrays.sort em Java.
Algoritmos de classificação clássicos auto-escritos em Java
Você já viu tarefas de classificação de Array se estiver estudando Ciência da Computação de forma independente ou na universidade. Existem muitos algoritmos de classificação diferentes e implementaremos alguns deles neste artigo. Geralmente, quanto mais fácil de implementar um algoritmo, menos eficiente ele é. Os programadores medem a eficiência dos algoritmos pelo tempo de sua operação e pela memória gasta em recursos. Esse não é o assunto do nosso artigo, mas mencionamos que Arrays.sort em Java é um algoritmo eficaz.
Tipo de bolha
Vamos começar com o algoritmo mais popular entre os estudantes: Bubble sort. É simples: o algoritmo compara dois elementos e depois os troca se estiverem na ordem errada, e assim por diante até o final do array. Acontece que elementos menores "flutuam" até o final do Array , como bolhas de refrigerante até o topo.
publicclassBubbleSort{publicstaticvoidbubbleSort(int[] myArray){int n = myArray.length;for(int i =0; i < n -1; i++){for(int j =0; j < n - i -1; j++){if(myArray[j]> myArray[j +1]){// Swap myArray[j] and myArray[j+1]int temp = myArray[j];
myArray[j]= myArray[j +1];
myArray[j +1]= temp;}}}}publicstaticvoidmain(String[] args){int[] arr ={18,28,2,7,90,45};System.out.println("Array before sorting:");for(int num : arr){System.out.print(num +" ");}bubbleSort(arr);System.out.println("\nArray after sorting:");for(int num : arr){System.out.print(num +" ");}}}
Aqui, o método recebe uma matriz de inteiros como entrada. O loop externo vai de 0 a n-1. Aqui n é o tamanho do array. O loop interno compara elementos adjacentes. Se a ordem estiver errada, o método os troca. Este procedimento é repetido até que todo o array seja classificado. Aqui está uma saída do nosso programa:
Matriz antes da classificação: 18 28 2 7 90 45 Matriz após a classificação: 2 7 18 28 45 90
Ordenação por seleção
O algoritmo de seleção classifica um array encontrando repetidamente o menor elemento da parte não classificada e colocando-o no início. Vamos escrever em Java:
publicclassSelectionSort{publicstaticvoidselectionSort(int[] myArray){int n = myArray.length;for(int i =0; i < n -1; i++){int minIndex = i;// Find the index of the minimum element in the unsorted part of the arrayfor(int j = i +1; j < n; j++){if(myArray[j]< myArray[minIndex]){
minIndex = j;}}// Swap the minimum element with the first element of the unsorted partint temp = myArray[minIndex];
myArray[minIndex]= myArray[i];
myArray[i]= temp;}}publicstaticvoidmain(String[] args){int[] arr ={18,28,45,2,90,7};System.out.println("Array before sorting:");for(int num : arr){System.out.print(num +" ");}selectionSort(arr);System.out.println("\nArray after sorting:");for(int num : arr){System.out.print(num +" ");}}}
Aqui está uma saída do programa:
Matriz antes da classificação: 18 28 45 2 90 7 Matriz após a classificação: 2 7 18 28 45 90
Vamos explicar passo a passo. O loop externo itera desde o início do Array até o penúltimo elemento (até n-1). Este loop seleciona cada elemento um por um como o ponto inicial da parte não classificada do Array . Dentro do loop externo, inicializamos minIndex com o índice atual i , assumindo que seja o índice do menor item na parte não classificada do Array . O loop interno começa em i+1 e vai até o último elemento do Array . Ele procura o índice do menor item na parte não classificada do Array comparando cada elemento com o elemento mínimo atual ( arr[minIndex] ). Se encontrarmos um elemento menor que o elemento mínimo atual, atualizamos minIndex para o índice do novo elemento mínimo. Após a conclusão do loop interno, encontramos o índice do elemento mínimo na parte não classificada do Array . Em seguida, trocamos o elemento mínimo pelo primeiro elemento da parte não classificada usando uma variável temporária temp. O loop externo continua até que todos os elementos sejam classificados, estendendo gradualmente a parte classificada do Array . Finalmente, o Array classificado é impresso no método principal antes e depois de chamar o método selectionSort .
Mesclar classificação
Merge Sort é um algoritmo de divisão e conquista que divide recursivamente o array em submatrizes menores, classifica-os e depois os mescla para obter um array classificado. Merge Sort é estável e amplamente utilizado, especialmente quando são necessárias estabilidade e complexidade de tempo garantida no pior caso.
publicclassMergeSort{//Merge Sort array publicstaticvoidmergeSort(int[] myArray){if(myArray.length <=1){return;}int mid = myArray.length /2;int[] left =newint[mid];int[] right =newint[myArray.length - mid];System.arraycopy(myArray,0, left,0, mid);System.arraycopy(myArray, mid, right,0, myArray.length - mid);mergeSort(left);mergeSort(right);merge(myArray, left, right);}publicstaticvoidmerge(int[] arr,int[] left,int[] right){int i =0;// index for left subarrayint j =0;// index for right subarrayint k =0;// index for merged arraywhile(i < left.length && j < right.length){if(left[i]<= right[j]){
arr[k++]= left[i++];}else{
arr[k++]= right[j++];}}while(i < left.length){
arr[k++]= left[i++];}while(j < right.length){
arr[k++]= right[j++];}}publicstaticvoidmain(String[] args){int[] arr ={18,2,28,7,90,45};System.out.println("Array before sorting:");for(int num : arr){System.out.print(num +" ");}mergeSort(arr);System.out.println("\nArray after sorting:");for(int num : arr){System.out.print(num +" ");}}}
A saída aqui é:
Matriz antes da classificação: 18 2 28 7 90 45 Matriz após a classificação: 2 7 18 28 45 90
Vamos explicar com mais precisão como funciona. O algoritmo divide o Array em duas partes recursivamente até que o caso base seja alcançado (quando o Array possui um ou zero elementos). Em seguida, ele mescla as metades classificadas novamente usando o método de mesclagem. O método merge recebe três arrays como entrada: o Array original e os subarrays esquerdo e direito (esquerdo e direito). Ele compara os elementos dos subarrays esquerdo e direito e os mescla no Array original em ordem de classificação.
Classificação de inserção
A classificação por inserção funciona inserindo repetidamente um elemento da parte não classificada em sua posição correta na parte classificada. Ele funciona bem para pequenos conjuntos de dados ou dados quase classificados.
publicclassInsertionSort{publicstaticvoidinsertionSort(int[] myArray){int n = myArray.length;for(int i =1; i < n; i++){int key = myArray[i];int j = i -1;while(j >=0&& myArray[j]> key){
myArray[j +1]= myArray[j];
j--;}
myArray[j +1]= key;}}publicstaticvoidmain(String[] args){int[] arr ={18,90,7,28,45,2};System.out.println("Array before sorting:");for(int num : arr){System.out.print(num +" ");}insertionSort(arr);System.out.println("\nArray after sorting:");for(int num : arr){System.out.print(num +" ");}}}
A saída do programa é como de costume:
Matriz antes da classificação: 18 90 7 28 45 2 Matriz após a classificação: 2 7 18 28 45 90
Aqui, o método insertSort implementa o algoritmo Insertion Sort. Ele itera pelo Array e considera cada elemento como uma chave. Ele compara a tonalidade com os elementos anteriores e os move uma posição à frente se forem maiores, efetivamente deslocando os elementos para abrir espaço para a tonalidade na posição correta.
O loop externo itera do segundo elemento ( i = 1 ) até o último elemento do Array. O loop interno começa no elemento atual ( arr[i] ) e vai para trás ( j = i - 1 ) até encontrar a posição correta para a chave ou atingir o início do Array . Dentro do loop interno, se um elemento ( arr[j] ) for maior que a chave, ele será deslocado uma posição à frente ( arr[j + 1] = arr[j] ) para abrir espaço para a chave. Este processo continua até que a posição correta da chave seja encontrada. Após a conclusão do loop interno, a chave é colocada na posição correta ( arr[j + 1] = key ). No método principal, um array de exemplo é criado e impresso antes e depois da classificação usando o método insertSort .
Ordenação rápida
Quick Sort é um algoritmo de divisão e conquista que seleciona um elemento pivô e particiona o Array em torno do pivô. Como regra, a classificação rápida é mais rápida que a classificação por mesclagem para conjuntos de dados pequenos e médios devido aos seus fatores constantes baixos.
publicclassQuickSort{publicstaticvoidquickSort(int[] myArray,int low,int high){if(low < high){int pivotIndex =partition(myArray, low, high);quickSort(myArray, low, pivotIndex -1);quickSort(myArray, pivotIndex +1, high);}}publicstaticintpartition(int[] arr,int low,int high){int pivot = arr[high];int i = low -1;for(int j = low; j < high; j++){if(arr[j]<= pivot){
i++;swap(arr, i, j);}}swap(arr, i +1, high);return i +1;}publicstaticvoidswap(int[] arr,int i,int j){int temp = arr[i];
arr[i]= arr[j];
arr[j]= temp;}publicstaticvoidmain(String[] args){int[] arr ={18,28,2,90,7,45};System.out.println("Array before sorting:");for(int num : arr){System.out.print(num +" ");}quickSort(arr,0, arr.length -1);System.out.println("\nArray after sorting:");for(int num : arr){System.out.print(num +" ");}}}
A saída está aqui:
Matriz antes da classificação: 18 28 2 90 7 45 Matriz após a classificação: 2 7 18 28 45 90
Então aqui temos três métodos para implementar a classificação rápida. O método quickSort usa três parâmetros: o Array a ser classificado, o índice baixo do subarray e o índice alto do subarray. Inicialmente, verifica se o subarray possui mais de um elemento. Nesse caso, ele seleciona um pivô usando o método de partição, classifica recursivamente a submatriz antes do pivô e classifica recursivamente a submatriz após o pivô. O método de partição seleciona o pivô como o último elemento do subarray ( arr[high] ). Ele define o índice de partição (i) para o índice baixo menos 1. Em seguida, ele itera do índice baixo para o índice alto - 1 e verifica se cada elemento é menor ou igual ao pivô. Nesse caso, ele troca o elemento pelo elemento no índice de partição (i) e incrementa o índice de partição. Finalmente, ele troca o elemento pivô pelo elemento no índice de partição + 1 e retorna o índice de partição. O método de partição seleciona o pivô como o último elemento do subarray ( arr[high] ). Ele define o índice de partição (i) para o índice baixo menos 1. Em seguida, itera do índice baixo para o índice alto - 1 e verifica se cada item é menor ou igual ao pivô. Nesse caso, ele troca o elemento pelo elemento no índice de partição (i) e incrementa o índice de partição. Finalmente, ele troca o elemento pivô pelo elemento no índice de partição + 1 e retorna o índice de partição. O método swap é um método utilitário usado para trocar dois elementos no Array . No método principal , um array de exemplo é criado e impresso antes e depois da classificação usando o método quickSort .
Conclusões
Neste artigo você descobriu como classificar um array na linguagem Java. Você pode usar um método Arrays.sort integrado ou escrever suas próprias implementações de métodos de classificação populares, como classificação por bolha, classificação por mesclagem e assim por diante. Além disso, você pode tentar invadir seu próprio método de classificação. Depende da sua tarefa. Se você precisar resolver um problema de classificação rapidamente, basta usar um método pré-escrito. Se você aprender programação e tentar ser melhor nisso, é realmente uma boa ideia escrever alguns métodos de classificação sozinho.
