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

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, st, dr 0≤st≤dr<n elementele tabloului a sunt indexate de la zero se recomandă realizarea unei soluții recursive

Exemplu

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

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

Funcția de validare Pentru a valida datele de intrare vom verifica dacă valorile sunt numere naturale mai mici decât 1.000.000.000 și dacă valorile indiciilor st și dr sunt în intervalul [0, n), unde n este lungimea tabloului a.

def validare(n: int, st: int, dr: int) -> bool:
   if not (0 < n <= 1000):
       return False
   if not (0 <= st <= dr < n):
       return False
   return True

Funcția de rezolvare Pentru a ordona crescător elementele tabloului a cu indici între st și dr, inclusiv aceștia, vom folosi o implementare a algoritmului quicksort.

def ordonare(a: List[int], n: int, st: int, dr: int) -> None:
   if st < dr:
       pivot = partition(a, st, dr)
       ordonare(a, n, st, pivot - 1)
       ordonare(a, n, pivot + 1, dr)

def partition(a: List[int], st: int, dr: int) -> int:
   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]
   a[i + 1], a[dr] = a[dr], a[i + 1]
   return i + 1

Funcția partition este implementarea unei etape a algoritmului quicksort, care selectează un element pivot și împarte tabloul în două subtablouri, astfel încât elementele mai mici decât pivot sunt înaintea sa, iar cele mai mari sunt după. Funcția întoarce indicele poziției pivot după ce tabloul a fost partitionat.

Funcția ordonare este implementarea recursivă a algoritmului quicksort pentru a ordona crescător elementele tabloului a cu indici între st și dr, inclusiv aceștia. Pe baza valorii pivotului returnate de partition, subtabloul din stânga pivotului și cel din dreapta pivotului sunt ordonate recursiv cu apeluri recursive la ordonare.

Funcția main Funcția main va citi datele de intrare, le va valida și, în cazul în care acestea sunt corecte, va apela funcția ordonare pentru a ordona elementele tabloului a. Dacă datele de intrare nu corespund restricțiilor impuse, va afișa un mesaj corespunzător.

def main() -> None:
   n = int(input())
   a = list(map(int, input().split()))
   st, dr = map(int, input().split())

   if not validare(n, st, dr):
       print("Datele de intrare nu corespund restricțiilor impuse.")
       return

   ordonare(a, n, st, dr)
   print("Datele de intrare co