1846 - OrdonareSecvF REC

Cerinţa

Scrieţi definiția completă a subprogramului recursiv ordonare care are 4 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 și doi indici st dr. Subprogramul ordonează crescător elementele tabloului a cu indici între st și dr, inclusiv aceștia,fără a modifica celelalte elemente ale tabloului.

Date de intrare

Se va introduce de la tastatură un număr natural care va fi transmis ca perimetru

Date de ieșire

Dacă datele de intrare corespund restrictiilor impuse se va afișa mesajul "Datele de intrare corespund restricțiilor" și pe un rând nou se afișează ceea ce se cere. Altfel, dacă datele de intrare nu corespund cerinței se va afișa mesajul: "Datele de intrare nu corespund cerinței".

Restricţii şi precizări

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

Exemplu

Exemplu 1

Intrare:
Introduceti numarul de elemente: 6
Introduceti cele 6 numere separate prin spatiu: 63 273 9 83 93 123
Introduceti indexul stanga: 1
Introduceti indexul dreapta: 3; Iesire:

[63, 9, 83, 273, 93, 123]

Exemplu 2

Intrare:
Introduceti numarul de elemente: 1001; Iesire:
Datele de intrare nu corespund cerinței.

Important

Soluţia propusă va conţine doar definiţia subprogramului cerut. Prezenţa în soluţie a altor instrucţiuni poate duce erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei.

Rezolvare

<syntaxhighlight lang="python" line="1"> def validare_numar(numar):

   if not numar.isdigit():
       return False
   n = int(numar)
   if n < 1 or n > 1000:
       return False
   return True

def validare_index(index, n):

   if not index.isdigit():
       return False
   i = int(index)
   if i < 0 or i >= n:
       return False
   return True

def ordonare(a, n, st, dr):

   if st < dr:
       pivot = a[dr]
       i = st - 1
       for j in range(st, dr):
           if a[j] < pivot:
               i += 1
               a[i], a[j] = a[j], a[i]
       i += 1
       a[i], a[dr] = a[dr], a[i]
       ordonare(a, n, st, i - 1)
       ordonare(a, n, i + 1, dr)

numar_elemente = input("Introduceti numarul de elemente: ") if not validare_numar(numar_elemente):

   print("Datele de intrare nu corespund cerinței.")

else:

   n = int(numar_elemente)
   a = input("Introduceti cele " + str(n) + " numere separate prin spatiu: ").split()
   if len(a) != n or not all(map(str.isdigit, a)):
       print("Datele de intrare nu corespund cerinței.")
   else:
       a = [int(x) for x in a]
       st = input("Introduceti indexul stanga: ")
       if not validare_index(st, n):
           print("Datele de intrare nu corespund cerinței.")
       else:
           st = int(st)
           dr = input("Introduceti indexul dreapta: ")
           if not validare_index(dr, n):
               print("Datele de intrare nu corespund cerinței.")
           else:
               dr = int(dr)
               ordonare(a, n, st, dr)
               print(a)

</syntaxhighlight>

Explicații

În funcția validare_input, se validează datele de intrare. Se verifică dacă numărul de elemente n este un număr natural mai mic sau egal cu 1000, iar indicele stanga st și cel dreapta dr sunt numere naturale, st mai mic decât dr și n mai mare decât dr.

Funcția ordonare este implementată recursiv, astfel încât să divizeze tabloul în două subtablouri, să le sorteze individual și apoi să le combine într-un tablou sortat. Dacă subtabloul are un singur element sau niciun element, atunci subtabloul este deja sortat. Altfel, se calculează mijlocul subtabloului, se sortează subtabloul stâng și subtaboul drept și apoi se combină cele două subtablouri sortate.

În funcția main, se citesc datele de intrare și se validează folosind funcția validare_input. Dacă datele de intrare sunt valide, atunci se completează tabloul și se apelează funcția ordonare pentru a sorta elementele între indicii stanga și dreapta. În final, se afișează tabloul sortat.