Dada una lista enlazada, la tarea es ordenar la lista enlazada en orden ascendente usando la ordenación por selección.
Ejemplos:
Input : 1->4->2->2->3 Output : 1->2->2->3->4 Input : 5->4->3->2 Output : 2->3->4->5
Algoritmo de clasificación de selección : Iterar la lista dada N veces donde N es el número de elementos en la lista. En cada iteración del ordenamiento por selección, el elemento mínimo (considerando el orden ascendente) del subarreglo no ordenado se selecciona y se mueve al subarreglo ordenado.
Ejemplo :
list = 64 25 12 22 11 // Find the minimum element in list(0...4) // and place it at beginning 11 25 12 22 64 // Find the minimum element in list(1...4) // and place it at beginning of list(1...4) 11 12 25 22 64 // Find the minimum element in list(2...4) // and place it at beginning of list(2...4) 11 12 22 25 64 // Find the minimum element in list(3...4) // and place it at beginning of list(3...4) 11 12 22 25 64
El intercambio requerido se puede hacer de dos maneras:
- Intercambiando las partes de datos de los Nodes.
- Intercambiando los Nodes completos.
La segunda implementación generalmente se usa cuando los elementos de la lista son algún tipo de registros porque, en tal caso, el intercambio de datos se vuelve tedioso y costoso debido a la presencia de una gran cantidad de elementos de datos.
Método de implementación 1 : a continuación se muestra la implementación de la función de clasificación por selección para clasificar listas vinculadas intercambiando solo partes de datos de un Node.
C++
void selectionSort(node* head)
{
node* temp = head;
// Traverse the List
while (temp) {
node* min = temp;
node* r = temp->next;
// Traverse the unsorted sublist
while (r) {
if (min->data > r->data)
min = r;
r = r->next;
}
// Swap Data
int x = temp->data;
temp->data = min->data;
min->data = x;
temp = temp->next;
}
}
Java
void selectionSort(node head)
{
node temp = head;
// Traverse the List
while (temp) {
node min = temp;
node r = temp.next;
// Traverse the unsorted sublist
while (r) {
if (min.data > r.data)
min = r;
r = r.next;
}
// Swap Data
int x = temp.data;
temp.data = min.data;
min.data = x;
temp = temp.next;
}
}
// This code is contributed by shivanisinghss2110
C#
static void selectionSort(node head)
{
node temp = head;
// Traverse the List
while (temp) {
node min = temp;
node r = temp.next;
// Traverse the unsorted sublist
while (r) {
if (min.data > r.data)
min = r;
r = r.next;
}
// Swap Data
int x = temp.data;
temp.data = min.data;
min.data = x;
temp = temp.next;
}
}
// This code contributed by shivanisinghss2110
Javascript
<script>
function selectionSort(head)
{
var temp = head;
// Traverse the List
while (temp) {
var min = temp;
var r = temp.next;
// Traverse the unsorted sublist
while (r) {
if (min.data > r.data)
min = r;
r = r.next;
}
// Swap Data
var x = temp.data;
temp.data = min.data;
min.data = x;
temp = temp.next;
}
}
</script>
Python3
def selectionSort(head): temp = head # Traverse the List while (temp): minn = temp r = temp.next # Traverse the unsorted sublist while (r): if (minn.data > r.data): minn = r r = r.next # Swap Data x = temp.data temp.data = minn.data minn.data = x temp = temp.next # This code is contributed by shubhamsingh10
Método 2 : el intercambio de datos es sin duda más fácil de implementar y comprender, pero en algunos casos (como se mencionó anteriormente), no es deseable. Al realizar el intercambio de las siguientes partes de dos Nodes, se deben tener en cuenta cuatro casos:
- Los Nodes son adyacentes y el primer Node es el Node inicial.
- Los Nodes son adyacentes y el primer Node no es el Node inicial.
- Los Nodes no son adyacentes y el primer Node es el Node inicial.
- Los Nodes no son adyacentes y el primer Node no es el Node inicial.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Linked List Node
struct Node {
int data;
Node* next;
};
// Utility function to create a
// new Linked List Node
Node* newNode(int val)
{
Node* temp = new Node;
temp->data = val;
temp->next = NULL;
return temp;
}
// Function to sort a linked list using selection
// sort algorithm by swapping the next pointers
Node* selectionSort(Node* head)
{
Node *a, *b, *c, *d, *r;
a = b = head;
// While b is not the last node
while (b->next) {
c = d = b->next;
// While d is pointing to a valid node
while (d) {
if (b->data > d->data) {
// If d appears immediately after b
if (b->next == d) {
// Case 1: b is the head of the linked list
if (b == head) {
// Move d before b
b->next = d->next;
d->next = b;
// Swap b and d pointers
r = b;
b = d;
d = r;
c = d;
// Update the head
head = b;
// Skip to the next element
// as it is already in order
d = d->next;
}
// Case 2: b is not the head of the linked list
else {
// Move d before b
b->next = d->next;
d->next = b;
a->next = d;
// Swap b and d pointers
r = b;
b = d;
d = r;
c = d;
// Skip to the next element
// as it is already in order
d = d->next;
}
}
// If b and d have some non-zero
// number of nodes in between them
else {
// Case 3: b is the head of the linked list
if (b == head) {
// Swap b->next and d->next
r = b->next;
b->next = d->next;
d->next = r;
c->next = b;
// Swap b and d pointers
r = b;
b = d;
d = r;
c = d;
// Skip to the next element
// as it is already in order
d = d->next;
// Update the head
head = b;
}
// Case 4: b is not the head of the linked list
else {
// Swap b->next and d->next
r = b->next;
b->next = d->next;
d->next = r;
c->next = b;
a->next = d;
// Swap b and d pointers
r = b;
b = d;
d = r;
c = d;
// Skip to the next element
// as it is already in order
d = d->next;
}
}
}
else {
// Update c and skip to the next element
// as it is already in order
c = d;
d = d->next;
}
}
a = b;
b = b->next;
}
return head;
}
// Function to print the list
void printList(Node* head)
{
while (head) {
cout << head->data << " ";
head = head->next;
}
}
// Driver Code
int main()
{
Node* head = newNode(5);
head->next = newNode(4);
head->next->next = newNode(3);
head = selectionSort(head);
printList(head);
return 0;
}
Java
// Java implementation of the approach
class GFG {
// Linked List Node
static class Node {
int data;
Node next;
};
// Utility function to create a
// new Linked List Node
static Node newNode(int val)
{
Node temp = new Node();
temp.data = val;
temp.next = null;
return temp;
}
// Function to sort a linked list using selection
// sort algorithm by swapping the next pointers
static Node selectionSort(Node head)
{
Node a, b, c, d, r;
a = b = head;
// While b is not the last node
while (b.next != null) {
c = d = b.next;
// While d is pointing to a valid node
while (d != null) {
if (b.data > d.data) {
// If d appears immediately after b
if (b.next == d) {
// Case 1: b is the head of the linked list
if (b == head) {
// Move d before b
b.next = d.next;
d.next = b;
// Swap b and d pointers
r = b;
b = d;
d = r;
c = d;
// Update the head
head = b;
// Skip to the next element
// as it is already in order
d = d.next;
}
// Case 2: b is not the head of the linked list
else {
// Move d before b
b.next = d.next;
d.next = b;
a.next = d;
// Swap b and d pointers
r = b;
b = d;
d = r;
c = d;
// Skip to the next element
// as it is already in order
d = d.next;
}
}
// If b and d have some non-zero
// number of nodes in between them
else {
// Case 3: b is the head of the linked list
if (b == head) {
// Swap b.next and d.next
r = b.next;
b.next = d.next;
d.next = r;
c.next = b;
// Swap b and d pointers
r = b;
b = d;
d = r;
c = d;
// Skip to the next element
// as it is already in order
d = d.next;
// Update the head
head = b;
}
// Case 4: b is not the head of the linked list
else {
// Swap b.next and d.next
r = b.next;
b.next = d.next;
d.next = r;
c.next = b;
a.next = d;
// Swap b and d pointers
r = b;
b = d;
d = r;
c = d;
// Skip to the next element
// as it is already in order
d = d.next;
}
}
}
else {
// Update c and skip to the next element
// as it is already in order
c = d;
d = d.next;
}
}
a = b;
b = b.next;
}
return head;
}
// Function to print the list
static void printList(Node head)
{
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
}
// Driver Code
public static void main(String args[])
{
Node head = newNode(5);
head.next = newNode(4);
head.next.next = newNode(3);
head = selectionSort(head);
printList(head);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach # Linked List Node class Node: def __init__(self, val): self.data = val self.next = None # Function to sort a linked list # using selection sort algorithm # by swapping the next pointers def selectionSort(head): a = b = head # While b is not the last node while b.next: c = d = b.next # While d is pointing to a valid node while d: if b.data > d.data: # If d appears immediately after b if b.next == d: # Case 1: b is the head # of the linked list if b == head: # Move d before b b.next = d.next d.next = b # Swap b and d pointers b, d = d, b c = d # Update the head head = b # Skip to the next element # as it is already in order d = d.next # Case 2: b is not the head # of the linked list else: # Move d before b b.next = d.next d.next = b a.next = d # Swap b and d pointers b, d = d, b c = d # Skip to the next element # as it is already in order d = d.next # If b and d have some non-zero # number of nodes in between them else: # Case 3: b is the head # of the linked list if b == head: # Swap b.next and d.next r = b.next b.next = d.next d.next = r c.next = b # Swap b and d pointers b, d = d, b c = d # Skip to the next element # as it is already in order d = d.next # Update the head head = b # Case 4: b is not the head # of the linked list else: # Swap b.next and d.next r = b.next b.next = d.next d.next = r c.next = b a.next = d # Swap b and d pointers b, d = d, b c = d # Skip to the next element # as it is already in order d = d.next else: # Update c and skip to the next element # as it is already in order c = d d = d.next a = b b = b.next return head # Function to print the list def printList(head): while head: print(head.data, end = " ") head = head.next # Driver Code if __name__ == "__main__": head = Node(5) head.next = Node(4) head.next.next = Node(3) head = selectionSort(head) printList(head) # This code is contributed # by Rituraj Jain
C#
// C# implementation of the approach
using System;
class GFG {
// Linked List Node
public class Node {
public int data;
public Node next;
};
// Utility function to create a
// new Linked List Node
static Node newNode(int val)
{
Node temp = new Node();
temp.data = val;
temp.next = null;
return temp;
}
// Function to sort a linked list using selection
// sort algorithm by swapping the next pointers
static Node selectionSort(Node head)
{
Node a, b, c, d, r;
a = b = head;
// While b is not the last node
while (b.next != null) {
c = d = b.next;
// While d is pointing to a valid node
while (d != null) {
if (b.data > d.data) {
// If d appears immediately after b
if (b.next == d) {
// Case 1: b is the head of the linked list
if (b == head) {
// Move d before b
b.next = d.next;
d.next = b;
// Swap b and d pointers
r = b;
b = d;
d = r;
c = d;
// Update the head
head = b;
// Skip to the next element
// as it is already in order
d = d.next;
}
// Case 2: b is not the head of the linked list
else {
// Move d before b
b.next = d.next;
d.next = b;
a.next = d;
// Swap b and d pointers
r = b;
b = d;
d = r;
c = d;
// Skip to the next element
// as it is already in order
d = d.next;
}
}
// If b and d have some non-zero
// number of nodes in between them
else {
// Case 3: b is the head of the linked list
if (b == head) {
// Swap b.next and d.next
r = b.next;
b.next = d.next;
d.next = r;
c.next = b;
// Swap b and d pointers
r = b;
b = d;
d = r;
c = d;
// Skip to the next element
// as it is already in order
d = d.next;
// Update the head
head = b;
}
// Case 4: b is not the head of the linked list
else {
// Swap b.next and d.next
r = b.next;
b.next = d.next;
d.next = r;
c.next = b;
a.next = d;
// Swap b and d pointers
r = b;
b = d;
d = r;
c = d;
// Skip to the next element
// as it is already in order
d = d.next;
}
}
}
else {
// Update c and skip to the next element
// as it is already in order
c = d;
d = d.next;
}
}
a = b;
b = b.next;
}
return head;
}
// Function to print the list
static void printList(Node head)
{
while (head != null) {
Console.Write(head.data + " ");
head = head.next;
}
}
// Driver Code
public static void Main(String[] arg)
{
Node head = newNode(5);
head.next = newNode(4);
head.next.next = newNode(3);
head = selectionSort(head);
printList(head);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
// Structure of a node of linked list
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// Utility function to create a
// new Linked List Node
function newNode( val)
{
var temp = new Node();
temp.data = val;
temp.next = null;
return temp;
}
// Function to sort a linked list using selection
// sort algorithm by swapping the next pointers
function selectionSort( head)
{
var a, b, c, d, r;
a = b = head;
// While b is not the last node
while (b.next != null) {
c = d = b.next;
// While d is pointing to a valid node
while (d != null) {
if (b.data > d.data) {
// If d appears immediately after b
if (b.next == d) {
// Case 1: b is the head of the linked list
if (b == head) {
// Move d before b
b.next = d.next;
d.next = b;
// Swap b and d pointers
r = b;
b = d;
d = r;
c = d;
// Update the head
head = b;
// Skip to the next element
// as it is already in order
d = d.next;
}
// Case 2: b is not the head of the linked list
else {
// Move d before b
b.next = d.next;
d.next = b;
a.next = d;
// Swap b and d pointers
r = b;
b = d;
d = r;
c = d;
// Skip to the next element
// as it is already in order
d = d.next;
}
}
// If b and d have some non-zero
// number of nodes in between them
else {
// Case 3: b is the head of the linked list
if (b == head) {
// Swap b.next and d.next
r = b.next;
b.next = d.next;
d.next = r;
c.next = b;
// Swap b and d pointers
r = b;
b = d;
d = r;
c = d;
// Skip to the next element
// as it is already in order
d = d.next;
// Update the head
head = b;
}
// Case 4: b is not the head of the linked list
else {
// Swap b.next and d.next
r = b.next;
b.next = d.next;
d.next = r;
c.next = b;
a.next = d;
// Swap b and d pointers
r = b;
b = d;
d = r;
c = d;
// Skip to the next element
// as it is already in order
d = d.next;
}
}
}
else {
// Update c and skip to the next element
// as it is already in order
c = d;
d = d.next;
}
}
a = b;
b = b.next;
}
return head;
}
// Function to print the list
function printList( head)
{
while (head != null) {
document.write(head.data + " ");
head = head.next;
}
}
// Driver Code
var head = newNode(5);
head.next = newNode(4);
head.next.next = newNode(3);
head = selectionSort(head);
printList(head);
// This code is contributed by jana_sayantan.
</script>
Producción:
3 4 5
Publicación traducida automáticamente
Artículo escrito por RachitKumarTewari y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA