1025 - MergeSort

Sursa: 1025 - MergeSort

---

Cerinţa

Se dă un şir lista cu numar elemente, numere întregi. Folosind metoda MergeSort (Sortare prin interclasare), ordonați crescător elementele acestui șir.

Date de intrare

Programul citește de la tastatură numărul numar, iar apoi cele numar elemente ale şirului lista.

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse.", urmat, pe rândul următor, de elementele șirului lista sortat, separate prin exact un spațiu. În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, programul va afișa "Datele de intrare nu corespund restricțiilor impuse.".

Restricţii şi precizări

• numar ∈ ℕ
• 1 ⩽ numar ⩽ 100.000
• element lista ∈ ℤ
• -1.000.000.000 ⩽ element lista ⩽ 1.000.000.000

Exemplu

Intrare

12

10 0 -1 -3 1 -4 9 3 -1 -4 3 -4

Ieșire

Datele de intrare corespund restricțiilor impuse.

-4 -4 -4 -3 -1 -1 0 1 3 3 9 10

Intrare

abc

Ieșire

Datele de intrare nu corespund restricțiilor impuse.

Intrare

-25

Ieșire

Datele de intrare nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 1025 - Mergesort

def validare_date_numar(numar: str) -> bool:

   try:
       int(numar)
       
       if 1 <= int(numar) <= 100_000:
           return True
       else:
           return False
   except ValueError:
       return False
   
   

def validare_date_sir(lista: list) -> bool:

   return all(-1_000_000_000 <= int(element) <= 1_000_000_000 for element in lista)

def merge(lista: list, left: int, mid: int, right: int):

   len1 = mid - left + 1
   len2 = right - mid
   
   left_arr = [0] * (len1)
   right_arr = [0] * (len2)
   
   for indice1 in range(len1):
       left_arr[indice1] = lista[left + indice1]
       
   for indice2 in range(0, len2):
       right_arr[indice2] = lista[mid + 1 + indice2]
       
       
   indice1 = int(0)
   indice2 = int(0)
   indice3 = left
   
   while indice1 < len1 and indice2 < len2:
       if left_arr[indice1] <= right_arr[indice2]:
           lista[indice3] = left_arr[indice1]
           indice1 += 1
       else:
           lista[indice3] = right_arr[indice2]
           indice2 += 1

       indice3 += 1
       
   while indice1 < len1:
       lista[indice3] = left_arr[indice1]
       indice1 += 1
       indice3 += 1
       
   while indice2 < len2:
       lista[indice3] = right_arr[indice2]
       indice2 += 1
       indice3 += 1
       
       

def mergesort(lista: list, left: int, right: int):

   if left < right:
       mid = left + (right - left) // 2
       
       mergesort(lista, left, mid)
       mergesort(lista, mid + 1, right)
       
       merge(lista, left, mid, right)

if __name__ == "__main__":

   numar = input()
   
   if validare_date_numar(numar):
       numar = int(numar)
       lista = input()
       lista = lista.split(" ")
       if validare_date_sir(lista):
           lista = list(map(int, lista))
           
           print("Datele de intrare corespund restricțiilor impuse.")
           mergesort(lista, 0, numar - 1)
           print(lista)
       else:
           print("Datele de intrare nu corespund restricțiilor impuse.")
   else:
       print("Datele de intrare nu corespund restricțiilor impuse.")
       

</syntaxhighlight>