1845 - OrdonareF Rec

Cerinţa

Scrieţi definiția completă a subprogramului recursiv ordonare care are 2 parametri: a, prin care primeşte un tablou unidimensional cu maximum 1000 de numere naturale mai mici decât 1.000.000.000 și n, numărul efectiv de elemente ale tabloului. Subprogramul ordonează crescător elementele tabloului a, fără a returna valori.

Date de intrare

Se va introduce de la tastatură 2 numere naturale care vor fi transmise ca perimetrii

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse." În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse.".

Restricţii şi precizări

0 < n <= 1000 numele subprogramului cerut este ordonare parametrii sunt, în această ordine: a, n elementele tabloului a sunt indexate de la zero se recomandă realizarea unei soluții recursive

Exemplu

Dacă n=6 și a=(63,273,9,83,93,123), după apelul subprogramului tabloul a devine (9,63,83,93,123,273).

Rezolvare

def ordonare(a, n):
   if n <= 1:
       return
   # Divizarea listei in doua jumatati
   m = n // 2
   left = a[:m]
   right = a[m:]
   # Sortarea celor doua jumatati
   ordonare(left, len(left))
   ordonare(right, len(right))
   # Combinarea celor doua jumatati ordonate
   i = j = k = 0
   while i < len(left) and j < len(right):
       if left[i] < right[j]:
           a[k] = left[i]
           i += 1
       else:
           a[k] = right[j]
           j += 1
       k += 1
   while i < len(left):
       a[k] = left[i]
       i += 1
       k += 1
   while j < len(right):
       a[k] = right[j]
       j += 1
       k += 1
# Citirea datelor de intrare
n = int(input())
a = []
for i in range(n):
   a.append(int(input()))
# Verificarea datelor de intrare
if n <= 0 or n > 1000:
   print("Datele de intrare nu corespund restricțiilor impuse.")
else:
   # Apelul functiei de ordonare
   ordonare(a, n)    
   # Afisarea tabloului ordonat
   print("Datele de intrare corespund restricțiilor impuse.")
   print(a)
La rularea programului, în cazul în care datele introduse sunt corecte, se va afișa mesajul "Datele de intrare 
corespund restricțiilor impuse." și tabloul ordonat, astfel:
6
63
273
9
83
93
123
Datele de intrare corespund restricțiilor impuse.
[9, 63, 83, 93, 123, 273]