Bogdan.Pop: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/1025/mergesort 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 core...

2023-02-20T17:07:02Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/1025/mergesort 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 core...

New page

Sursa: [https://www.pbinfo.ro/probleme/1025/mergesort 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 &les; '''numar''' &les; 100.000
* ''element lista'' ∈ ℤ
* -1.000.000.000 &les; ''element lista'' &les; 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
<br>
; Intrare
: abc
; Ieșire
: Datele de intrare nu corespund restricțiilor impuse.
<br>
; Intrare
: -25
; Ieșire
: Datele de intrare nu corespund restricțiilor impuse.
<br>
== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 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>

1025 - MergeSort - Revision history