Come ordinare un array in Java

L'ordinamento è una delle operazioni più comuni e necessarie nella programmazione. Rappresenta l'ordinamento di alcuni insiemi di elementi in un ordine specifico. Questo articolo riguarda i metodi standard per l'ordinamento degli array in Java.

Brevemente sull'ordinamento

Quindi, l'ordinamento è l'ordinamento di un insieme di dati. Nel nostro caso, array. Lo scopo dell'ordinamento di array o altre strutture dati è facilitare la ricerca, la manipolazione o l'analisi dei dati nella raccolta. I programmatori hanno bisogno dell'ordinamento così spesso che qualsiasi linguaggio di programmazione include metodi incorporati per ordinare array, elenchi e altre strutture di dati ordinate. Per utilizzare tali metodi, chiamali. L'operazione è semplificata il più possibile. Di solito, i metodi integrati sono ottimizzati al massimo; nella maggior parte dei casi, usarli per il tuo lavoro o per i tuoi progetti è una buona idea. Tuttavia, quasi tutti i programmatori, durante i propri studi, hanno bisogno di implementare autonomamente algoritmi di ordinamento. Pertanto, questi esercizi perfetti ti insegnano a comprendere l'essenza stessa della programmazione. Inoltre, a volte sono necessari metodi di ordinamento non standard nel lavoro. Esistono molti algoritmi di ordinamento. Hanno punti di forza e di debolezza a seconda del tipo o della dimensione dei set di dati. Gli algoritmi di ordinamento standard includono l'ordinamento a bolle, l'ordinamento per selezione, l'ordinamento per inserimento, l'ordinamento per unione e il Quicksort.

Metodo integrato per l'ordinamento degli array in Java: Arrays.sort

Cominciamo con il più semplice. Qualcuno ha già scritto per noi un metodo per ordinare gli array in Java. Questo metodo si trova nella classe Arrays , più specificamente java.util.Arrays . Questa classe contiene vari metodi per lavorare con gli array, come l'ordinamento e la ricerca. Il metodo Arrays.sort fornisce un modo conveniente per ordinare gli array in Java, indipendentemente dal fatto che contengano stringhe, numeri interi o altri elementi. Esistono diverse varianti del metodo Arrays.sort in Java. Ecco alcuni metodi di ordinamento comunemente usati dalla classe Arrays :

• Arrays.sort(Array) : usalo per ordinare array di tipi primitivi o oggetti in ordine crescente. Utilizza l'ordine naturale degli elementi.
• Arrays.sort(Array, fromIndex, toIndex) : questo metodo di ordinamento sovraccaricato consente di ordinare solo una parte dell'array specificato dai parametri fromIndex e toIndex.
• Arrays.sort(Array, comparator) : questo serve per ordinare array di oggetti utilizzando un comparatore personalizzato. Il comparatore definisce l'ordinamento degli elementi.
• Arrays.parallelSort(Array) : questa versione del metodo ordina l' array in parallelo, utilizzando più thread per migliorare le prestazioni. È utile per ordinare array di grandi dimensioni.
• Arrays.parallelSort(Array, fromIndex, toIndex) : questa versione sovraccaricata del metodo parallelSort consente di ordinare un intervallo specifico di elementi in Array .

Permettono di disporre rapidamente gli elementi in base al loro ordine naturale o utilizzando un comparatore personalizzato. Esploriamo questo metodo con due esempi, uno dei quali riguarda le stringhe.

Esempio 1: ordinamento delle stringhe

Supponiamo di avere una serie di strumenti musicali a corda: "violino", "viola", "violoncello" e "contrabbasso". Possiamo usare il metodo Array.sort per disporli in ordine alfabetico.

import java.util.Arrays;
//Arrays.sort example
public class StringSortExample {
    public static void main(String[] args) {
        String[] instruments = {"violin", "viola", "cello", "double bass"};

        Arrays.sort(instruments);

        System.out.println("Sorted Instruments:");
        for (String instrument : instruments) {
            System.out.println(instrument);
        }
    }
}

L'output è qui: In questo programma, innanzitutto, importiamo la classe java.util.Arrays per ottenere l'accesso al metodo Array.sort . Quindi creiamo un array di stringhe chiamato Instruments contenente i nomi degli strumenti musicali. Successivamente, chiamiamo Arrays.sort(instruments) . Quindi questo metodo ottiene un array, ordina gli elementi in ordine crescente in base al loro ordine naturale (alfabetico). Infine, eseguiamo il loop dell'array ordinato e stampiamo ogni strumento.

Esempio 2: ordinamento di numeri interi

Consideriamo un altro esempio in cui ordiniamo un array di numeri interi in ordine crescente.

import java.util.Arrays;

public class IntegerSortExample {
    public static void main(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);
        }
    }
}

Produzione: Qui creiamo un array di numeri interi chiamato numeri con diversi elementi non ordinati. Successivamente, chiamiamo Arrays.sort(numbers) per ordinare un array in ordine crescente. Si noti che il metodo Array.sort modifica l'array originale sul posto. Quindi, per mantenere l' Array originale , creane una copia prima di ordinarla.

Esempio 3: ordine decrescente

E l'ordinamento discendente? È anche facile con Arrays.sort . Basta usare un comparatore personalizzato. Ecco un esempio:

import java.util.Arrays;
import java.util.Comparator;
//Arrays.sort with custom comparator example
public class DescendingSortExample {
    public static void main(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);
        }
    }
}

L'output è il seguente: Qui abbiamo una serie di numeri interi chiamati numeri. Passando Comparator.reverseOrder() come secondo argomento al metodo Arrays.sort , specifichiamo un comparatore personalizzato che ordina gli elementi in ordine decrescente. Il metodo Comparator.reverseOrder() restituisce un comparatore che inverte l'ordinamento naturale degli elementi. Tieni presente che qui utilizziamo la classe wrapper Integer invece del tipo int primitivo perché il metodo Comparator.reverseOrder() richiede oggetti. Se disponi di un array di valori int primitivi, dovresti anche convertirli in oggetti Integer prima di utilizzare questo approccio. Utilizzando un comparatore personalizzato, puoi facilmente ordinare l'array in ordine decrescente utilizzando il metodo Arrays.sort in Java.

Algoritmi di ordinamento classici autoprodotti in Java

Hai già visto i compiti di ordinamento degli array se stai studiando informatica in modo indipendente o all'università. Esistono molti algoritmi di ordinamento diversi e ne implementeremo alcuni in questo articolo. In generale, più un algoritmo è facile da implementare, meno è efficiente. I programmatori misurano l'efficienza degli algoritmi in base al tempo di funzionamento e alla memoria spesa per le risorse. Non è questo l'argomento del nostro articolo, ma ricordiamo che Arrays.sort in Java è un algoritmo efficace.

Ordinamento a bolle

Cominciamo con l'algoritmo più popolare tra gli studenti: Bubble sort. È semplice: l'algoritmo confronta due elementi e poi li scambia se sono nell'ordine sbagliato, e così via fino alla fine dell'array. Si scopre che gli elementi più piccoli "galleggiano" fino alla fine dell'Array , come bolle nella soda che scoppiano in cima.

public class BubbleSort {

       public static void bubbleSort(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;
                   }
               }
           }
       }

       public static void main(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 + " ");
           }
       }
}

Qui il metodo accetta un array di numeri interi come input. Il ciclo esterno va da 0 a n-1. Qui n è la dimensione dell'array. Il ciclo interno confronta gli elementi adiacenti. Se l'ordine è sbagliato, il metodo li scambia. Questa procedura viene ripetuta finché l'intero array non è stato ordinato. Ecco un output del nostro programma:

Ordinamento della selezione

L'algoritmo di selezione ordina un array trovando ripetutamente l'elemento più piccolo della parte non ordinata e posizionandolo all'inizio. Scriviamolo in Java:

public class SelectionSort {
   public static void selectionSort(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 array
           for (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 part
           int temp = myArray[minIndex];
           myArray[minIndex] = myArray[i];
           myArray[i] = temp;
       }
   }

   public static void main(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 + " ");
       }
   }
}

Ecco un output del programma: Spieghiamolo passo dopo passo. Il ciclo esterno scorre dall'inizio dell'Array al penultimo elemento (fino a n-1). Questo ciclo seleziona ogni elemento uno per uno come punto iniziale della parte non ordinata dell'Array . All'interno del ciclo esterno, inizializziamo minIndex sull'indice corrente i , presupponendo che sia l'indice dell'elemento più piccolo nella parte non ordinata di Array . Il ciclo interno inizia da i+1 e arriva fino all'ultimo elemento di Array . Cerca l'indice dell'elemento più piccolo nella parte non ordinata dell'Array confrontando ciascun elemento con l'elemento minimo corrente ( arr[minIndex] ). Se troviamo un elemento più piccolo dell'elemento minimo corrente, aggiorniamo minIndex all'indice del nuovo elemento minimo. Una volta completato il ciclo interno, abbiamo trovato l'indice dell'elemento minimo nella parte non ordinata di Array . Successivamente scambiamo l'elemento minimo con il primo elemento della parte non ordinata utilizzando una variabile temporanea temp. Il ciclo esterno continua finché tutti gli elementi non vengono ordinati, estendendo gradualmente la parte ordinata di Array . Infine, l' Array ordinato viene stampato nel metodo main prima e dopo aver chiamato il metodo SelectionSort .

Unisci ordinamento

Merge Sort è un algoritmo divide et impera che divide ricorsivamente l' Array in sottoarray più piccoli, li ordina e quindi li unisce per ottenere un array ordinato. Merge Sort è stabile e ampiamente utilizzato, soprattutto quando sono richieste stabilità e complessità temporale garantita nel caso peggiore.

public class MergeSort {

      //Merge Sort array
      public static void mergeSort(int[] myArray) {
        if (myArray.length <= 1) {
            return;
        }

        int mid = myArray.length / 2;
        int[] left = new int[mid];
        int[] right = new int[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);
    }

    public static void merge(int[] arr, int[] left, int[] right) {
        int i = 0; // index for left subarray
        int j = 0; // index for right subarray
        int k = 0; // index for merged array

        while (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++];
        }
    }

    public static void main(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 + " ");
        }
    }
}

L'output qui è: Spieghiamo più precisamente come funziona. L'algoritmo divide l' Array in due parti ricorsivamente fino al raggiungimento del caso base (quando l' Array ha uno o zero elementi). Quindi unisce nuovamente le metà ordinate utilizzando il metodo di unione. Il metodo di unione accetta tre array come input: l' array originale e i sottoarray sinistro e destro (sinistro e destro). Confronta gli elementi dei sottoarray sinistro e destro e li unisce nell'array originale in ordine ordinato.

Ordinamento di inserimento

L'ordinamento per inserimento funziona inserendo ripetutamente un elemento dalla parte non ordinata nella sua posizione corretta nella parte ordinata. Funziona bene con set di dati di piccole dimensioni o dati quasi ordinati.

public class InsertionSort {
    public static void insertionSort(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;
        }
    }

    public static void main(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 + " ");
        }
    }
}

L'output del programma è proprio come al solito: Qui il metodo insertSort implementa l'algoritmo Insertion Sort. Itera attraverso l' Array e considera ogni elemento come una chiave. Confronta la chiave con gli elementi precedenti e li sposta di una posizione avanti se sono maggiori, spostando effettivamente gli elementi per fare spazio alla chiave nella posizione corretta. Il ciclo esterno scorre dal secondo elemento ( i = 1 ) all'ultimo elemento dell'Array. Il ciclo interno inizia dall'elemento corrente ( arr[i] ) e va indietro ( j = i - 1 ) finché non trova la posizione corretta per la chiave o raggiunge l'inizio dell'Array . All'interno del ciclo interno, se un elemento ( arr[j] ) è maggiore della chiave, viene spostato di una posizione in avanti ( arr[j + 1] = arr[j] ) per fare spazio alla chiave. Questo processo continua finché non viene trovata la posizione corretta per la chiave. Una volta completato il ciclo interno, la chiave viene posizionata nella posizione corretta ( arr[j + 1] = key ). Nel metodo main, un array di esempio viene creato e stampato prima e dopo l'ordinamento utilizzando il metodo insertSort .

Ordinamento rapido

Quick Sort è un algoritmo divide et impera che seleziona un elemento pivot e partiziona l'array attorno al pivot. Di norma, l'ordinamento rapido è più veloce dell'ordinamento mediante unione per set di dati di piccole e medie dimensioni grazie ai suoi fattori costanti bassi.

public class QuickSort {

       public static void quickSort(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);
           }
       }

       public static int partition(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;
       }

       public static void swap(int[] arr, int i, int j) {
           int temp = arr[i];
           arr[i] = arr[j];
           arr[j] = temp;
       }

       public static void main(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 + " ");
           }
       }
}

L'output è qui: Quindi qui abbiamo tre metodi per implementare l'ordinamento rapido. Il metodo quickSort accetta tre parametri: l' array da ordinare, l'indice basso del sottoarray e l'indice alto del sottoarray. Inizialmente controlla se il sottoarray ha più di un elemento. In tal caso, seleziona un pivot utilizzando il metodo di partizione, ordina ricorsivamente il sottoarray prima del pivot e ordina ricorsivamente il sottoarray dopo il pivot. Il metodo di partizione seleziona il pivot come ultimo elemento del sottoarray ( arr[high] ). Imposta l'indice di partizione (i) sull'indice basso meno 1. Quindi scorre dall'indice basso all'indice alto - 1 e controlla se ciascun elemento è inferiore o uguale al pivot. In tal caso, scambia l'elemento con l'elemento all'indice della partizione (i) e incrementa l'indice della partizione. Infine, scambia l'elemento pivot con l'elemento all'indice della partizione + 1 e restituisce l'indice della partizione. Il metodo di partizione seleziona il pivot come ultimo elemento del sottoarray ( arr[high] ). Imposta l'indice di partizione (i) sull'indice basso meno 1. Quindi scorre dall'indice basso all'indice alto - 1 e controlla se ogni elemento è più piccolo o uguale al pivot. In tal caso, scambia l'elemento con l'elemento all'indice della partizione (i) e incrementa l'indice della partizione. Infine, scambia l'elemento pivot con l'elemento all'indice della partizione + 1 e restituisce l'indice della partizione. Il metodo swap è un metodo di utilità utilizzato per scambiare due elementi nell'Array . Nel metodo main , un array di esempio viene creato e stampato prima e dopo l'ordinamento utilizzando il metodo quickSort .

Conclusioni

Da questo articolo hai scoperto come ordinare un array in linguaggio Java. È possibile utilizzare un metodo Arrays.sort integrato o scrivere le proprie implementazioni di metodi di ordinamento popolari come bubble sort, merge sort e così via. Inoltre puoi provare a invadere il tuo metodo di ordinamento. Dipende dal tuo compito. Se hai bisogno di risolvere velocemente un problema di ordinamento, usa semplicemente un metodo già scritto. Se impari a programmare e cerchi di migliorare, è davvero una buona idea scrivere alcuni metodi di ordinamento da solo.