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

#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)