Vizualizare sursă pentru „1476 – FSortare”

==Enunţ==
Se consideră o listă liniară simplu înlănțuită, alocată dinamic, în care elementele sunt de tipul declarat mai jos:

   struct nod{
     int info;
     nod *urm;
   };

în care câmpul info memorează un număr întreg, iar câmpul urm memorează adresa următorului element al listei.

==Cerința==
Să se scrie o funcție C++ cu următorul prototip:

  void sortareCrescator(nod *&prim)

care sortează crescător elementele listei al cărei prim element are adresa memorată în prim.

==Restricții și precizări==
*numele funcției va fi sortareCrescator
*lista va conține cel puțin 3 elemente
*rezolvarea se va face in python

==Exemplu==
Dacă lista este formată din valorile (5, 3, 9, 4, 2, 12), după apelul funcţiei ea va conţine elementele (2, 3, 4, 5, 9, 12).

==Rezolvare==
<syntaxhighlight lang="python" line>
#1476 FSortare
class Node:
    def __init__(self, info):
        self.info = info
        self.next = None

def create_linked_list(values):
    head = None
    tail = None
    for value in values:
        new_node = Node(value)
        if head is None:
            head = new_node
            tail = new_node
        else:
            tail.next = new_node
            tail = new_node
    return head

def sortareCrescator(prim):
    # Funcție pentru inserarea unui nod într-o listă sortată
    def insert_sorted(head, new_node):
        if head is None or head.info >= new_node.info:
            new_node.next = head
            return new_node

        current = head
        while current.next is not None and current.next.info < new_node.info:
            current = current.next
        
        new_node.next = current.next
        current.next = new_node
        return head
    
    # Inițializăm lista sortată ca fiind lista vidă
    sorted_list = None
    current = prim
    
    # Parcurgem lista inițială și inserăm fiecare nod în lista sortată
    while current is not None:
        sorted_list = insert_sorted(sorted_list, Node(current.info))
        current = current.next
    
    # Copiem lista sortată înapoi în lista inițială
    current = prim
    sorted_current = sorted_list
    while sorted_current is not None:
        current.info = sorted_current.info
        current = current.next
        sorted_current = sorted_current.next

# Testăm funcția
def print_list(head):
    current = head
    while current is not None:
        print(current.info, end=" ")
        current = current.next
    print()

# Cream lista de test folosind funcția create_linked_list
values = [5, 3, 9, 4, 2, 12]
l = create_linked_list(values)

print("Lista initiala:")
print_list(l)

# Sortam lista
sortareCrescator(l)

print("Lista sortata:")
print_list(l)
</syntaxhighlight>