Ordene la lista doblemente enlazada dada usando la ordenación de burbuja .
Ejemplos:
Input : 5 4 3 2 1 Output : 1 2 3 4 5 Input : 2 1 3 5 4 Output :1 2 3 4 5
Explicación
Como hacemos en la ordenación de burbujas, aquí también verificamos los elementos de dos Nodes adyacentes si están en orden ascendente o no, si no, intercambiamos el elemento. Hacemos esto hasta que cada elemento obtenga su posición original.
En el primer paso, el elemento más grande obtiene su posición original y en el segundo paso, el segundo elemento más grande obtiene su posición original y en el tercer paso, el tercer elemento más grande obtiene su posición original y así sucesivamente.
Y finalmente toda la lista se ordena.
Nota: Si la lista ya está ordenada, solo hará una pasada.
C++
// CPP program to sort a doubly linked list using
// bubble sort
#include <iostream>
using namespace std;
// structure of a node
struct Node {
int data;
Node* prev;
Node* next;
};
/* Function to insert a node at the beginning of a linked list */
void insertAtTheBegin(struct Node **start_ref, int data)
{
struct Node *ptr1 = new Node;
ptr1->data = data;
ptr1->next = *start_ref;
if (*start_ref != NULL)
(*start_ref)->prev = ptr1;
*start_ref = ptr1;
}
/* Function to print nodes in a given linked list */
void printList(struct Node *start)
{
struct Node *temp = start;
cout << endl;
while (temp!=NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
}
/* Bubble sort the given linked list */
void bubbleSort(struct Node *start)
{
int swapped, i;
struct Node *ptr1;
struct Node *lptr = NULL;
/* Checking for empty list */
if (start == NULL)
return;
do
{
swapped = 0;
ptr1 = start;
while (ptr1->next != lptr)
{
if (ptr1->data > ptr1->next->data)
{
swap(ptr1->data, ptr1->next->data);
swapped = 1;
}
ptr1 = ptr1->next;
}
lptr = ptr1;
}
while (swapped);
}
int main()
{
int arr[] = {12, 56, 2, 11, 1, 90};
int list_size, i;
/* start with empty linked list */
struct Node *start = NULL;
/* Create linked list from the array arr[].
Created linked list will be 1->11->2->56->12 */
for (i = 0; i< 6; i++)
insertAtTheBegin(&start, arr[i]);
/* print list before sorting */
printf("\n Linked list before sorting ");
printList(start);
/* sort the linked list */
bubbleSort(start);
/* print list after sorting */
printf("\n Linked list after sorting ");
printList(start);
return 0;
}
Java
// Java program to sort a doubly linked list using
// bubble sort
class GFG
{
// structure of a node
static class Node
{
int data;
Node prev;
Node next;
};
// Function to insert a node at the beginning of a linked list
static Node insertAtTheBegin( Node start_ref, int data)
{
Node ptr1 = new Node();
ptr1.data = data;
ptr1.next = start_ref;
if (start_ref != null)
(start_ref).prev = ptr1;
start_ref = ptr1;
return start_ref;
}
// Function to print nodes in a given linked list
static void printList( Node start)
{
Node temp = start;
System.out.println();
while (temp != null)
{
System.out.print( temp.data + " ");
temp = temp.next;
}
}
// Bubble sort the given linked list
static Node bubbleSort( Node start)
{
int swapped, i;
Node ptr1;
Node lptr = null;
// Checking for empty list
if (start == null)
return null;
do
{
swapped = 0;
ptr1 = start;
while (ptr1.next != lptr)
{
if (ptr1.data > ptr1.next.data)
{
int t = ptr1.data;
ptr1.data = ptr1.next.data;
ptr1.next.data = t;
swapped = 1;
}
ptr1 = ptr1.next;
}
lptr = ptr1;
}
while (swapped != 0);
return start;
}
// Driver code
public static void main(String args[])
{
int arr[] = {12, 56, 2, 11, 1, 90};
int list_size, i;
// start with empty linked list
Node start = null;
// Create linked list from the array arr[].
//Created linked list will be 1->11->2->56->12
for (i = 0; i < 6; i++)
start=insertAtTheBegin(start, arr[i]);
// print list before sorting
System.out.printf("\n Linked list before sorting ");
printList(start);
// sort the linked list
start = bubbleSort(start);
// print list after sorting
System.out.printf("\n Linked list after sorting ");
printList(start);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to sort a doubly linked list using
# bubble sort
# structure of a node
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
''' Function to insert a node at the beginning of a linked list '''
def insertAtTheBegin(start_ref, data):
ptr1 = Node(data)
ptr1.data = data;
ptr1.next = start_ref;
if (start_ref != None):
(start_ref).prev = ptr1;
start_ref = ptr1;
return start_ref
''' Function to print nodes in a given linked list '''
def printList(start):
temp = start;
print()
while (temp != None):
print(temp.data, end = ' ')
temp = temp.next;
''' Bubble sort the given linked list '''
def bubbleSort(start):
swapped = 0
lptr = None;
''' Checking for empty list '''
if (start == None):
return;
while True:
swapped = 0;
ptr1 = start;
while (ptr1.next != lptr):
if (ptr1.data > ptr1.next.data):
ptr1.data, ptr1.next.data = ptr1.next.data, ptr1.data
swapped = 1;
ptr1 = ptr1.next;
lptr = ptr1;
if swapped == 0:
break
# Driver code
if __name__=='__main__':
arr = [12, 56, 2, 11, 1, 90]
''' start with empty linked list '''
start = None;
''' Create linked list from the array arr[].
Created linked list will be 1.11.2.56.12 '''
for i in range(6):
start = insertAtTheBegin(start, arr[i]);
''' print list before sorting '''
print("Linked list before sorting ", end = '');
printList(start);
''' sort the linked list '''
bubbleSort(start);
''' print list after sorting '''
print("\nLinked list after sorting ", end = '');
printList(start);
# This code is contributed by rutvik_56
C#
// C# program to sort a doubly linked list using
// bubble sort
using System;
class GFG
{
// structure of a node
public class Node
{
public int data;
public Node prev;
public Node next;
};
// Function to insert a node at the beginning of a linked list
static Node insertAtTheBegin( Node start_ref, int data)
{
Node ptr1 = new Node();
ptr1.data = data;
ptr1.next = start_ref;
if (start_ref != null)
(start_ref).prev = ptr1;
start_ref = ptr1;
return start_ref;
}
// Function to print nodes in a given linked list
static void printList( Node start)
{
Node temp = start;
Console.WriteLine();
while (temp != null)
{
Console.Write( temp.data + " ");
temp = temp.next;
}
}
// Bubble sort the given linked list
static Node bubbleSort( Node start)
{
int swapped;
Node ptr1;
Node lptr = null;
// Checking for empty list
if (start == null)
return null;
do
{
swapped = 0;
ptr1 = start;
while (ptr1.next != lptr)
{
if (ptr1.data > ptr1.next.data)
{
int t = ptr1.data;
ptr1.data = ptr1.next.data;
ptr1.next.data = t;
swapped = 1;
}
ptr1 = ptr1.next;
}
lptr = ptr1;
}
while (swapped != 0);
return start;
}
// Driver code
public static void Main(String []args)
{
int []arr = {12, 56, 2, 11, 1, 90};
int i;
// start with empty linked list
Node start = null;
// Create linked list from the array arr[].
//Created linked list will be 1->11->2->56->12
for (i = 0; i < 6; i++)
start=insertAtTheBegin(start, arr[i]);
// print list before sorting
Console.Write("\n Linked list before sorting ");
printList(start);
// sort the linked list
start = bubbleSort(start);
// print list after sorting
Console.Write("\n Linked list after sorting ");
printList(start);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to sort a doubly linked list using
// bubble sort
// structure of a node
class Node {
constructor() {
this.data = 0;
this.next = null;
this.prev = null;
}
}
// Function to insert a node at the beginning of a linked list
function insertAtTheBegin(start_ref, data) {
var ptr1 = new Node();
ptr1.data = data;
ptr1.next = start_ref;
if (start_ref != null) start_ref.prev = ptr1;
start_ref = ptr1;
return start_ref;
}
// Function to print nodes in a given linked list
function printList(start) {
var temp = start;
document.write("<br>");
while (temp != null) {
document.write(temp.data + " ");
temp = temp.next;
}
}
// Bubble sort the given linked list
function bubbleSort(start) {
var swapped;
var ptr1;
var lptr = null;
// Checking for empty list
if (start == null) return null;
do {
swapped = 0;
ptr1 = start;
while (ptr1.next != lptr) {
if (ptr1.data > ptr1.next.data) {
var t = ptr1.data;
ptr1.data = ptr1.next.data;
ptr1.next.data = t;
swapped = 1;
}
ptr1 = ptr1.next;
}
lptr = ptr1;
} while (swapped != 0);
return start;
}
// Driver code
var arr = [12, 56, 2, 11, 1, 90];
var i;
// start with empty linked list
var start = null;
// Create linked list from the array arr[].
//Created linked list will be 1->11->2->56->12
for (i = 0; i < 6; i++) start = insertAtTheBegin(start, arr[i]);
// print list before sorting
document.write("Linked list before sorting ");
printList(start);
// sort the linked list
start = bubbleSort(start);
// print list after sorting
document.write("<br> Linked list after sorting ");
printList(start);
// This code is contributed by rdtank.
</script>
Producción:
Linked list before sorting 90 1 11 2 56 12 Linked list after sorting 1 2 11 12 56 90
Complejidad de Tiempo : O(n 2 )
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por Premdeep Toppo y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA