Ordenar lista enlazada manual con algoritmo de ordenación de burbujas en Java

1. Clasificación de burbujas en Java
2. Lista enlazada manual de clasificación de burbuja en Java
3. Lista enlazada de clasificación de clase en Java

Ordenación de burbujas es el algoritmo de estructura de datos más común utilizado para ordenar la recopilación de datos. Funciona iterando e intercambiando los elementos adyacentes en el orden incorrecto hasta que sean correctos.

Primero le mostraremos la demostración de clasificación básica. Luego implementaremos dos algoritmos de ordenación de burbujas para ordenar listas enlazadas en Java.

Clasificación de burbujas en Java

Mantengamos las cosas esenciales sin entrar en el aspecto aritmético de la clasificación. Atravesaremos una matriz desde el principio hasta el índice final en el tipo de burbuja.

Entonces solo puede comparar el índice actual con el siguiente índice. El concepto central de esta fórmula es cuando los elementos presentes se vuelven más grandes que el siguiente elemento.

Sintaxis:

for (int A = 0; A < sort - 1; A++)
  for (int B = 0; B < sort - A - 1; B++)
    if (DEMO[B] > DEMO[B + 1]) {
      // Swapping of array
      int temp = DEMO[B];
      DEMO[B] = DEMO[B + 1];
      DEMO[B + 1] = temp;
    }

Ahora ejecutemos un algoritmo simple de clasificación de burbujas en Java. Pero primero, eche un vistazo al estado inicial de los índices no ordenados del array.

Array: {43, 65, 21, 64, 12, 6, 1}

El siguiente bloque de código realizará una clasificación de burbuja en este índice del array aplicando este algoritmo de clasificación básico.

Cabe mencionar que siempre podemos modificar esta fórmula dependiendo de nuestros requerimientos. Sin embargo, el núcleo debe seguir siendo básico para formar claridad en este momento.

Código:

// In this program, we will sort an array DEMO using the bubble sort algorithm
// Main class
public class BubbleSortLinkListExample1 {
  // Main function
  private void bubbleSort(int DEMO[]) {
    // Using .length to determine entire length of array's index
    int sort = DEMO.length;
    // If array's length is less than int sort, increase it by 1
    for (int A = 0; A < sort - 1; A++)
      // Formula 1
      for (int B = 0; B < sort - A - 1; B++)
        if (DEMO[B] > DEMO[B + 1]) {
          // Swapping of array
          int temp = DEMO[B];
          DEMO[B] = DEMO[B + 1];
          DEMO[B + 1] = temp;
        }
  }
  /* Now we are going to print DEMO array*/
  void printArray(int DEMO[]) {
    int sort = DEMO.length;
    for (int A = 0; A < sort; ++A) System.out.print(DEMO[A] + " ");
    System.out.println();
  }
  // We are going to implement a driver algorithm for sorting our DEMO array
  public static void main(String args[]) {
    BubbleSortLinkListExample1 ob = new BubbleSortLinkListExample1();
    int DEMO[] = {43, 65, 21, 64, 12, 6, 1};
    ob.bubbleSort(DEMO);
    System.out.println("After the array has been sorted!");
    ob.printArray(DEMO);
  }
}

Después de clasificar esta matriz en orden ascendente, obtenemos la salida de Java.

Producción :

After the array has been sorted!
1 6 12 21 43 64 65

Lista enlazada manual de clasificación de burbuja en Java

La clasificación manual de la lista enlazada también es un método sencillo en la clasificación de burbujas.

¿Hemos discutido atravesar datos anteriormente? Ahora, lo practicaremos.

Los nodos nos permiten atravesar datos de un nodo al siguiente.

Mire nuestro modelo de demostración a continuación. Dado que realizamos la clasificación en el ejemplo anterior, es importante enfatizar los nodos aquí.

Lista enlazada de clasificación de clase en Java

Como entendimos, aplicamos esta clase para formar nodos en Java.

Código:

class SortLL {
  public static class Mynode {
    int indx;
    Mynode fwdMynode;

    public Mynode(int indx) {
      this.indx = indx;
      this.fwdMynode = null;
    }
    public int getindx() {
      return this.indx;
    }
  }

Puede usar estas clases por separado y llamar a sus objetos, pero esa es una forma larga y complicada. Por lo tanto, hemos guardado todas las clases en un archivo.

Asimismo, utilizaremos la función .getNextNode(), recupera el siguiente elemento de la clase sin argumentos. Debe estar familiarizado con el concepto, así que ejecutemos el algoritmo de clasificación manual de burbujas sin más preámbulos.

1. Lista enlazada antes de ordenar:

   

   Código:

   class SortLL {
     public static class Mynode {
       int indx;
       Mynode fwdMynode;
   
       public Mynode(int indx) {
         this.indx = indx;
         this.fwdMynode = null;
       }
       public int getindx() {
         return this.indx;
       }
     }
     // My node class
     private Mynode head;
     private int size;
     public SortLL() {
       this.head = null;
       this.size = 0;
     }
     public void add(int indx) {
       Mynode Mynode = new Mynode(indx);
       if (head == null) {
         head = Mynode;
       } else {
         Mynode CN = head;
         while (CN.fwdMynode != null) {
           CN = CN.fwdMynode;
         }
         CN.fwdMynode = Mynode;
       }
       size++;
     }
     public void sort() {
       if (size > 1) {
         boolean dtr;
         do {
           Mynode thisMynode = head;
           Mynode ladtMynode = null;
           Mynode fwd = head.fwdMynode;
           dtr = false;
   
           while (fwd != null) {
             if (thisMynode.indx > fwd.indx) {
               dtr = true;
               if (ladtMynode != null) {
                 Mynode sig = fwd.fwdMynode;
   
                 ladtMynode.fwdMynode = fwd;
                 fwd.fwdMynode = thisMynode;
                 thisMynode.fwdMynode = sig;
               } else {
                 Mynode sig = fwd.fwdMynode;
                 head = fwd;
                 fwd.fwdMynode = thisMynode;
                 thisMynode.fwdMynode = sig;
               }
               ladtMynode = fwd;
               fwd = thisMynode.fwdMynode;
             } else {
               ladtMynode = thisMynode;
               thisMynode = fwd;
               fwd = fwd.fwdMynode;
             }
           }
         } while (dtr);
       }
     }
     public int listSize() {
       return size;
     }
     public void printindx() {
       Mynode CN = head;
   
       while (CN != null) {
         int indx = CN.getindx();
         System.out.print(indx + " ");
         CN = CN.fwdMynode;
       }
       System.out.println();
     }
     public boolean isEmpty() {
       return size == 0;
     }
   }
   // indxInterface class
   class SrtBubb {
     public static void main(String[] args) {
       SortLL s = new SortLL();
       s.add(12);
       s.add(2);
       s.add(7);
       s.add(19);
       s.add(23);
       s.add(9);
       System.out.println("Before Performing Bubble Sort");
       s.printindx();
       s.sort();
       System.out.println("After Performing Bubble Sort");
       s.printindx();
       System.out.println("Size of the linked list is: " + s.listSize());
     }
   }
   

2. Después de realizar la clasificación de burbujas manual:

   

   Producción:

   Before Performing Bubble Sort
   12 2 7 19 23 9
   After Performing Bubble Sort
   2 7 9 12 19 23
   Size of the linked list is: 6
   

Puede modificar este programa según sus requisitos. Pero este es el método más práctico para que los principiantes entiendan la clasificación manual de listas enlazadas mediante la clasificación de burbujas.

Suponga que todavía está confundido acerca de este tema. También le proporcionamos el código en el directorio de archivos.