Larisa.Chiș at 16:00, 7 January 2023

2023-01-07T16:00:55Z

← Older revision		Revision as of 16:00, 7 January 2023
Line 1:		Line 1:
	== Cerința ==		== Cerința ==
	Se dă un șir cu n elemente, numere întregi. Folosind metoda MergeSort (Sortare prin interclasare), ordonați crescător elementele acestui șir.		Se dă un șir cu n elemente, numere întregi. Folosind metoda MergeSort (Sortare prin interclasare), ordonați crescător elementele acestui șir.

	== Date de intrare ==		== Date de intrare ==
	Programul citește de la tastatură numărul n, iar apoi cele n elemente ale șirului.		Programul citește de la tastatură numărul n, iar apoi cele n elemente ale șirului.

	== Date de ieșire ==		== Date de ieșire ==
	Programul va afișa pe ecran elementele șirului sortat, separate prin exact un spațiu.		Programul va afișa pe ecran elementele șirului sortat, separate prin exact un spațiu.

	== Restricții și precizări ==		== Restricții și precizări ==
	1 ≤ n ≤ 100.000		1 ≤ n ≤ 100.000
	elementele șirului vor fi cuprinse între -1.000.000.000 și 1.000.000.000		elementele șirului vor fi cuprinse între -1.000.000.000 și 1.000.000.000

	== Exemplu ==		== Exemplu ==

	Intrare		Intrare
Line 23:		Line 23:
	-4 -4 -4 -3 -1 -1 0 1 3 3 9 10		-4 -4 -4 -3 -1 -1 0 1 3 3 9 10

	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>

Larisa.Chiș: Pagină nouă: == Cerința == Se dă un șir cu n 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 n, iar apoi cele n elemente ale șirului. == Date de ieșire == Programul va afișa pe ecran elementele șirului sortat, separate prin exact un spațiu. == Restricții și precizări == 1 ≤ n ≤ 100.000 elementele șirului vor fi cuprin...

2023-01-07T15:59:31Z

Pagină nouă: == Cerința == Se dă un șir cu n 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 n, iar apoi cele n elemente ale șirului. == Date de ieșire == Programul va afișa pe ecran elementele șirului sortat, separate prin exact un spațiu. == Restricții și precizări == 1 ≤ n ≤ 100.000 elementele șirului vor fi cuprin...

New page

== Cerința ==
Se dă un șir cu n 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 n, iar apoi cele n elemente ale șirului.

== Date de ieșire ==
Programul va afișa pe ecran elementele șirului sortat, separate prin exact un spațiu.

== Restricții și precizări ==
1 ≤ n ≤ 100.000
elementele șirului vor fi cuprinse între -1.000.000.000 și 1.000.000.000

== Exemplu ==

Intrare

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

Ieșire

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

== Rezolvare ==
<syntaxhighlight lang="python" line>

def mergeSort(array):
if len(array) > 1:

# r is the point where the array is divided into two subarrays
r = len(array)//2
L = array[:r]
M = array[r:]

# Sort the two halves
mergeSort(L)
mergeSort(M)

i = j = k = 0

# Until we reach either end of either L or M, pick larger among
# elements L and M and place them in the correct position at A[p..r]
while i < len(L) and j < len(M):
if L[i] < M[j]:
array[k] = L[i]
i += 1
else:
array[k] = M[j]
j += 1
k += 1

# When we run out of elements in either L or M,
# pick up the remaining elements and put in A[p..r]
while i < len(L):
array[k] = L[i]
i += 1
k += 1

while j < len(M):
array[k] = M[j]
j += 1
k += 1

# Print the array
def printList(array):
for i in range(len(array)):
print(array[i], end=" ")
print()

# Driver program
if __name__ == '__main__':
array_to_be_sorted = input('Introduceti o lista de numere, separate prin spatiu:')
array_to_be_sorted = array_to_be_sorted.split()

mergeSort(array_to_be_sorted)

print("Sorted array is: ")
printList(array_to_be_sorted)

</syntaxhighlight>

1025-MergeSort - Revision history

Larisa.Chiș at 16:00, 7 January 2023