Implementazione del bubble sort in Java

Esistono numerosi algoritmi di ordinamento, molti dei quali sono molto specifici e sono stati sviluppati per risolvere una gamma ristretta di problemi e lavorare con tipi specifici di dati. Ma tra tutta questa diversità, l’algoritmo più semplice è meritatamente il bubble sort, che può essere implementato in qualsiasi linguaggio di programmazione. Nonostante la sua semplicità, è alla base di molti algoritmi piuttosto complessi. Un altro vantaggio altrettanto importante è la sua semplicità e, quindi, può essere ricordato e implementato immediatamente, senza avere davanti a sé alcuna letteratura aggiuntiva.

introduzione

L'intera Internet moderna è costituita da un numero enorme di diversi tipi di strutture dati raccolte nei database. Memorizzano tutti i tipi di informazioni, dai dati personali degli utenti al nucleo semantico di sistemi automatizzati altamente intelligenti. Inutile dire che l’ordinamento dei dati gioca un ruolo estremamente importante in questa enorme quantità di informazioni strutturate. L'ordinamento può essere un passaggio obbligatorio prima di cercare qualsiasi informazione nel database e la conoscenza degli algoritmi di ordinamento gioca un ruolo molto importante nella programmazione.

Smistamento attraverso gli occhi delle macchine e gli occhi umani

Immaginiamo di dover ordinare 5 colonne di diverse altezze in ordine crescente. Queste colonne possono significare qualsiasi tipo di informazione (prezzi delle azioni, larghezza di banda del canale di comunicazione, ecc.); puoi presentare alcune delle tue versioni di questa attività per renderla più chiara. Bene, ad esempio, ordineremo i Vendicatori in base all'altezza: A differenza di un programma per computer, l'ordinamento non sarà difficile per te, perché puoi vedere l'intera immagine e capire immediatamente quale eroe deve essere spostato e dove affinché l'ordinamento in base all'altezza venga completato con successo. Probabilmente hai già intuito che per ordinare questa struttura di dati in ordine crescente, basta scambiare i posti di Hulk e Iron Man:

Fatto!

E questo completerà l'ordinamento con successo. Tuttavia, il computer, a differenza di te, è alquanto stupido e non vede l'intera struttura dei dati nel suo insieme. Il suo programma di controllo può confrontare solo due valori contemporaneamente. Per risolvere questo problema dovrà inserire due numeri nella sua memoria ed eseguire su di essi un'operazione di confronto, per poi passare ad un'altra coppia di numeri e così via finché non avrà analizzato tutti i dati. Pertanto, qualsiasi algoritmo di ordinamento può essere molto semplificato sotto forma di tre passaggi:

• Confronta due elementi;
• Scambia o copiane uno;
• Vai all'elemento successivo;

Algoritmi diversi possono eseguire queste operazioni in modi diversi, ma passeremo a considerare come funziona il bubble sort.

Algoritmo di ordinamento a bolle

L'ordinamento delle bolle è considerato il più semplice, ma prima di descrivere questo algoritmo, immaginiamo come ordineresti i Vendicatori in altezza se potessi, come una macchina, confrontare solo due eroi tra loro in un periodo di tempo. Molto probabilmente, faresti quanto segue (in modo ottimale):

• Ti sposti all'elemento zero del nostro array (Black Widow);
• Confronta l'elemento zero (Vedova Nera) con il primo (Hulk);
• Se l'elemento alla posizione zero è più alto, li inverti;
• Altrimenti, se l'elemento in posizione zero è più piccolo, li lasci al loro posto;
• Spostati in una posizione a destra e ripeti il ​​confronto (confronta Hulk con il Capitano)

Dopo aver esaminato l'intero elenco in un unico passaggio con tale algoritmo, l'ordinamento non verrà completato completamente. D'altra parte, l'elemento più grande nell'elenco verrà spostato nella posizione all'estrema destra. Questo accadrà sempre, perché non appena trovi l'elemento più grande, cambierai costantemente posto finché non lo sposterai fino alla fine. Cioè, non appena il programma "trova" Hulk nell'array, lo sposterà ulteriormente fino alla fine dell'elenco: Questo è il motivo per cui questo algoritmo è chiamato bubble sort, perché come risultato del suo funzionamento, l'elemento più grande nell'elenco sarà in cima all'array e tutti gli elementi più piccoli verranno spostati di una posizione a sinistra: Per completare l'ordinamento, dovrai tornare all'inizio dell'array e ripetere nuovamente i cinque passaggi sopra descritti, spostandoti nuovamente da sinistra a destra, confrontando e spostando gli elementi secondo necessità. Ma questa volta devi fermare l'algoritmo un elemento prima della fine dell'array, perché sappiamo già che l'elemento più grande (Hulk) è assolutamente nella posizione più a destra: Quindi il programma deve avere due loop. Per maggiore chiarezza, prima di passare alla revisione del codice del programma, è possibile vedere una visualizzazione di come funziona il bubble sort a questo link: Visualizzazione di come funziona il bubble sort

Implementazione del bubble sort in Java

Per dimostrare come funziona l'ordinamento in Java, ecco il codice del programma:

• crea un array di 5 elementi;
• vi carica l'Ascesa dei Vendicatori;
• visualizza il contenuto dell'array;
• implementa l'ordinamento a bolle;
• visualizza nuovamente l'array ordinato.

Puoi visualizzare il codice qui sotto e persino scaricarlo nel tuo IDE IntelliJ preferito . Verrà analizzato di seguito:

class ArrayBubble{
    private long[] a;   // array reference
    private int elems;  //number of elements in the array

    public ArrayBubble(int max){    //class constructor
        a = new long[max];          //create an array with size max
        elems = 0;                  //when created, the array contains 0 elements
    }

    public void into(long value){   // method for inserting an element into an array
        a[elems] = value;           //insert value into array a
        elems++;                    //array size increases
    }

    public void printer(){          // method for outputting an array to the console
        for (int i = 0; i < elems; i++){    //for each element in the array
            System.out.print(a[i] + " ");   // output to console
            System.out.println("");         //a new line
        }
        System.out.println("----End array output----");
    }

    private void toSwap(int first, int second){ //method swaps a pair of array numbers
        long dummy = a[first];      // put the first element into a temporary variable
        a[first] = a[second];       // put the second element in place of the first
        a[second] = dummy;          //instead of the second element, write the first from temporary memory
    }

    public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
        for (int out = elems - 1; out >= 1; out--){  //Outer loop
            for (int in = 0; in < out; in++){       //Inner loop
                if(a[in] > a[in + 1])               //If the order of the elements is wrong
                    toSwap(in, in + 1);             // call the swapping method
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBubble array = new ArrayBubble(5); //Create array array with 5 elements

        array.into(163);       //fill the array
        array.into(300);
        array.into(184);
        array.into(191);
        array.into(174);

        array.printer();            //display elements before sorting
        array.bubbleSorter();       //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
        array.printer();            // print the sorted list again
    }
}

Nonostante i commenti dettagliati nel codice, forniamo una descrizione di alcuni dei metodi presentati nel programma. I metodi chiave che svolgono il lavoro principale del programma sono scritti nella classe ArrayBubble. La classe contiene un costruttore e diversi metodi:

• into– metodo di inserimento di elementi in un array;
• printer– visualizza il contenuto dell'array riga per riga;

• toSwap– riorganizza gli elementi se necessario. Per fare ciò, viene utilizzata una variabile temporanea dummy, nella quale viene scritto il valore del primo numero e al posto del primo numero viene scritto il valore del secondo numero. Il contenuto della variabile temporanea viene quindi scritto nel secondo numero. Questa è una tecnica standard per scambiare due elementi;

  e infine il metodo principale:

• bubbleSorter– che svolge il lavoro principale e ordina i dati memorizzati nell'array, lo presenteremo di nuovo separatamente:

  public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
      for (int out = elems - 1; out >= 1; out--){  //Outer loop
          for (int in = 0; in < out; in++){       //Inner loop
              if(a[in] > a[in + 1])               //If the order of the elements is wrong
                  toSwap(in, in + 1);             // call the swapping method
          }
      }
  }

Qui dovresti prestare attenzione a due contatori: esterno oute interno in. Il contatore esternoout inizia ad enumerare i valori dalla fine dell'array e diminuisce gradualmente di uno ad ogni nuovo passaggio. outAd ogni nuovo passaggio la variabile viene spostata ulteriormente a sinistra in modo da non influenzare i valori già ordinati sul lato destro dell'array. Il contatore internoin inizia ad enumerare i valori dall'inizio dell'array e aumenta gradualmente di uno ad ogni nuovo passaggio. L'incremento inavviene fino a raggiungere out(l'ultimo elemento analizzato nel passaggio corrente). Il ciclo interno inconfronta due celle adiacenti ine in+1. Se inin è memorizzato un numero maggiore di in+1, viene chiamato il metodo toSwap, che scambia le posizioni di questi due numeri.

Conclusione

L'algoritmo di bubble sort è uno dei più lenti. Se l'array è composto da N elementi, i confronti verranno eseguiti N-1 al primo passaggio, N-2 al secondo, quindi N-3 e così via. Cioè, verrà effettuato il numero totale di passaggi: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 Pertanto, durante l'ordinamento, l'algoritmo esegue circa 0,5x(N ^2) confronti. Per N = 5, il numero di confronti sarà circa 10, per N = 10 il numero di confronti aumenterà a 45. Pertanto, all'aumentare del numero di elementi, la complessità dell'ordinamento aumenta in modo significativo: La velocità dell'algoritmo è influenzata non solo dal numero di passaggi, ma anche dal numero di permutazioni da effettuare. Per i dati casuali, il numero medio di permutazioni è (N^2) / 4, ovvero circa la metà del numero di passaggi. Tuttavia, nel peggiore dei casi, il numero di permutazioni può anche essere N^2 / 2 - questo è il caso se i dati vengono inizialmente ordinati in ordine inverso. Nonostante si tratti di un algoritmo di ordinamento piuttosto lento, è abbastanza importante conoscere e capire come funziona e, come accennato in precedenza, costituisce la base per algoritmi più complessi. Dio mio!