Una lista enlazada es una estructura de datos lineal, en la que los elementos no se almacenan en ubicaciones de memoria contiguas.
Clasificación de los Nodes de una lista de enlaces individuales en orden ascendente:
Lista original
Lista ordenada
Podemos ordenar LinkedList por muchas técnicas de clasificación:
- Ordenamiento de burbuja
- Tipo de inserción
- Ordenación rápida
- Ordenar por fusión
Método 1: Ordenar usando Bubble Sort
- Para realizar esta tarea, mantenemos dos punteros: actual e índice.
- Inicialmente, el punto actual al Node principal y el índice apuntarán al Node próximo al actual.
- Recorra la lista hasta que los puntos actuales sean nulos, comparando los datos actuales con los datos del índice.
- Y para el valor de cada corriente, el índice es el siguiente Node actual que atraviesa desde el siguiente Node actual hasta nulo.
- Y luego el valor del Node actual se compara con cada valor desde su siguiente Node hasta el último y si el valor es más pequeño que el valor actual, entonces los valores se intercambian y de esta manera el valor mínimo viene como índice actual.
Java
// Java program to sort a Linked List using Bubble Sort
public class SortList {
// Represent a node of the singly linked list
class Node {
int data;
Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
// Represent the head and tail of the singly linked list
public Node head = null;
public Node tail = null;
// addNode() will add a new node to the list
public void addNode(int data)
{
// Create a new node
Node newNode = new Node(data);
// Checks if the list is empty
if (head == null) {
// If list is empty, both head and tail will
// point to new node
head = newNode;
tail = newNode;
}
else {
// newNode will be added after tail such that
// tail's next will point to newNode
tail.next = newNode;
// newNode will become new tail of the list
tail = newNode;
}
}
// sortList() will sort nodes of the list in ascending
// order
public void sortList()
{
// Node current will point to head
Node current = head, index = null;
int temp;
if (head == null) {
return;
}
else {
while (current != null) {
// Node index will point to node next to
// current
index = current.next;
while (index != null) {
// If current node's data is greater
// than index's node data, swap the data
// between them
if (current.data > index.data) {
temp = current.data;
current.data = index.data;
index.data = temp;
}
index = index.next;
}
current = current.next;
}
}
}
// display() will display all the nodes present in the
// list
public void display()
{
// Node current will point to head
Node current = head;
if (head == null) {
System.out.println("List is empty");
return;
}
while (current != null) {
// Prints each node by incrementing pointer
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args)
{
SortList sList = new SortList();
// Adds data to the list
sList.addNode(8);
sList.addNode(3);
sList.addNode(7);
sList.addNode(4);
// Displaying original list
System.out.println("Original list: ");
sList.display();
// Sorting list
sList.sortList();
// Displaying sorted list
System.out.println("Sorted list: ");
sList.display();
}
}
Original list: 8 3 7 4 Sorted list: 3 4 7 8
Complejidad del tiempo: O(n^2)
Complejidad del espacio: O(1)
Método 2: Ordenar usando la ordenación por inserción
- En la técnica de ordenación por inserción, asumimos que todos los elementos antes del elemento actual en la lista ya están ordenados, y comenzamos con el elemento actual.
- El elemento actual se compara con todos los elementos anteriores y se intercambia si no está en orden. Este proceso se repite para todos los elementos posteriores.
- En general, la técnica de ordenación por inserción compara cada elemento con todos sus elementos anteriores y ordena el elemento para colocarlo en la posición adecuada.
Como ya se mencionó, la técnica de clasificación por inserción es más factible para un conjunto de datos más pequeño y, por lo tanto, las arrays con unos pocos elementos se pueden clasificar utilizando la clasificación por inserción de manera eficiente.
La ordenación por inserción es especialmente útil para ordenar estructuras de datos de listas enlazadas. Como sabe, las listas vinculadas tienen punteros que apuntan a su siguiente elemento (lista de enlace simple) y al elemento anterior (lista de enlace doble). Esto facilita el seguimiento de los elementos anteriores y siguientes.
Java
// Java program to sort Linked List using Insertion Sort
public class LinkedlistIS
{
node head;
node sorted;
class node
{
int val;
node next;
public node(int val)
{
this.val = val;
}
}
void push(int val)
{
// allocate node
node newnode = new node(val);
// link the old list off the new node
newnode.next = head;
// move the head to point to the new node
head = newnode;
}
// function to sort a singly linked list using insertion sort
void insertionSort(node headref)
{
// Initialize sorted linked list
sorted = null;
node current = headref;
// Traverse the given linked list and insert every
// node to sorted
while (current != null)
{
// Store next for next iteration
node next = current.next;
// insert current in sorted linked list
sortedInsert(current);
// Update current
current = next;
}
// Update head_ref to point to sorted linked list
head = sorted;
}
// function to insert a new_node in a list. Note that
// this function expects a pointer to head_ref as this
// can modify the head of the input linked list
// (similar to push())
void sortedInsert(node newnode)
{
// Special case for the head end
if (sorted == null || sorted.val >= newnode.val)
{
newnode.next = sorted;
sorted = newnode;
}
else
{
node current = sorted;
// Locate the node before the point of insertion
while (current.next != null && current.next.val < newnode.val)
{
current = current.next;
}
newnode.next = current.next;
current.next = newnode;
}
}
// Function to print linked list
void printlist(node head)
{
while (head != null)
{
System.out.print(head.val + " ");
head = head.next;
}
}
// Driver program to test above functions
public static void main(String[] args)
{
LinkedlistIS list = new LinkedlistIS();
list.push(4);
list.push(7);
list.push(3);
list.push(8);
System.out.println("Linked List before Sorting..");
list.printlist(list.head);
list.insertionSort(list.head);
System.out.println("\nLinkedList After sorting");
list.printlist(list.head);
}
}
Linked List before Sorting.. 8 3 7 4 LinkedList After sorting 3 4 7 8
Complejidad del tiempo: O(n^2)
Complejidad del espacio: O(1)
Método 3: Ordenar usando Quick Sort
La ordenación rápida sigue el enfoque de divide y vencerás . Selecciona un elemento como pivote y divide la array dada alrededor del pivote elegido.
El proceso clave en QuickSort es la partición(). El objetivo de las particiones es, dada una array y un elemento x de la array como pivote, colocar x en su posición correcta en la array ordenada y colocar todos los elementos más pequeños (menores que x) antes de x, y colocar todos los elementos mayores (mayores que x) después X. Todo esto debe hacerse en tiempo lineal.
Se prefiere la ordenación rápida a la ordenación combinada, ya que la ordenación rápida es un algoritmo en el lugar (lo que significa que no se requiere espacio de memoria adicional).
Java
// Java program for Quick Sort on Singly Linked List
public class QuickSortLinkedList
{
static class Node
{
int data;
Node next;
Node(int d)
{
this.data = d;
this.next= null;
}
}
Node head;
void addNode(int data)
{
if(head == null)
{
head = new Node(data);
return;
}
Node curr = head;
while(curr.next != null)
curr = curr.next;
Node newNode = new Node(data);
curr.next = newNode;
}
void printList(Node n)
{
while(n != null)
{
System.out.print(n.data);
System.out.print(" ");
n = n.next;
}
}
// takes first and last node,
// but do not break any links in
// the whole linked list
Node paritionLast(Node start, Node end)
{
if(start == end ||
start == null || end == null)
return start;
Node pivot_prev = start;
Node curr = start;
int pivot = end.data;
// iterate till one before the end,
// no need to iterate till the end
// because end is pivot
while(start != end )
{
if(start.data < pivot)
{
// keep tracks of last modified item
pivot_prev = curr;
int temp = curr.data;
curr.data = start.data;
start.data = temp;
curr = curr.next;
}
start = start.next;
}
// swap the position of curr i.e.
// next suitable index and pivot
int temp = curr.data;
curr.data = pivot;
end.data = temp;
// return one previous to current
// because current is now pointing to pivot
return pivot_prev;
}
void sort(Node start, Node end)
{
if(start == end )
return;
// split list and partition recurse
Node pivot_prev = paritionLast(start, end);
sort(start, pivot_prev);
// if pivot is picked and moved to the start,
// that means start and pivot is same
// so pick from next of pivot
if( pivot_prev != null &&
pivot_prev == start )
sort(pivot_prev.next, end);
// if pivot is in between of the list,
// start from next of pivot,
// since we have pivot_prev, so we move two nodes
else if(pivot_prev != null &&
pivot_prev.next != null)
sort(pivot_prev.next.next, end);
}
// Driver Code
public static void main(String[] args)
{
QuickSortLinkedList list = new QuickSortLinkedList();
list.addNode(8);
list.addNode(3);
list.addNode(7);
list.addNode(4);
Node n = list.head;
while(n.next != null)
n= n.next;
System.out.println("Original List: ");
list.printList(list.head);
list.sort(list.head , n);
System.out.println("\nSorted List: ");
list.printList(list.head);
}
}
Original List: 8 3 7 4 Sorted List: 3 4 7 8
Complejidad del tiempo: O(n^2)
Complejidad del espacio: O(1)
Método 3: Ordenar usando Merge Sort
A menudo se prefiere la ordenación por combinación para ordenar una lista vinculada. El lento rendimiento de acceso aleatorio de una lista enlazada hace que algunos otros algoritmos (como la ordenación rápida) funcionen mal y otros (como la ordenación heap) sean completamente imposibles.
Merge Sort es un algoritmo Divide and Conquer . Divide la array de entrada en dos mitades, se llama a sí mismo para las dos mitades y luego fusiona las dos mitades ordenadas. La función merge() se utiliza para fusionar dos mitades. merge(arr, l, m, r) es un proceso clave que asume que arr[l..m] y arr[m+1..r] están ordenados y fusiona los dos subarreglos ordenados en uno solo.
- Deje que head sea el primer Node de la lista enlazada que se ordenará y headRef sea el puntero a head.
- Tenga en cuenta que necesitamos una referencia al encabezado en MergeSort() ya que la implementación a continuación cambia los siguientes enlaces para ordenar las listas vinculadas (no los datos en los Nodes), por lo que el Node principal debe cambiarse si los datos en el encabezado original no es el valor más pequeño en la lista enlazada.
Java
// Java program to sort linkedList using Merge Sort
public class linkedList
{
node head = null;
// node a, b;
static class node {
int val;
node next;
public node(int val)
{
this.val = val;
}
}
node sortedMerge(node a, node b)
{
node result = null;
// Base cases
if (a == null)
return b;
if (b == null)
return a;
// Pick either a or b, and recur
if (a.val < b.val)
{
result = a;
result.next = sortedMerge(a.next, b);
}
else
{
result = b;
result.next = sortedMerge(a, b.next);
}
return result;
}
node mergeSort(node h)
{
// Base case : if head is null
if (h == null || h.next == null)
{
return h;
}
// get the middle of the list
node middle = getMiddle(h);
node nextofmiddle = middle.next;
// set the next of middle node to null
middle.next = null;
// Apply mergeSort on left list
node left = mergeSort(h);
// Apply mergeSort on right list
node right = mergeSort(nextofmiddle);
// Merge the left and right lists
node sortedlist = sortedMerge(left, right);
return sortedlist;
}
// Utility function to get the middle of the linked list
public static node getMiddle(node head)
{
if (head == null)
return head;
node slow = head, fast = head;
while (fast.next != null && fast.next.next != null)
{
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
void push(int new_data)
{
// allocate node
node new_node = new node(new_data);
// link the old list off the new node
new_node.next = head;
// move the head to point to the new node
head = new_node;
}
// Utility function to print the linked list
void printList(node headref)
{
while (headref != null) {
System.out.print(headref.val + " ");
headref = headref.next;
}
}
public static void main(String[] args)
{
linkedList li = new linkedList();
li.push(4);
li.push(7);
li.push(3);
li.push(8);
System.out.print("\nOriginal List: \n");
li.printList(li.head);
// Apply merge Sort
li.head = li.mergeSort(li.head);
System.out.print("\nSorted List: \n");
li.printList(li.head);
}
}
Original List: 8 3 7 4 Sorted List: 3 4 7 8
Complejidad del tiempo: O(n log n)
Complejidad del espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por dd120smash y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA