1024 - QuikSort
Sursa: 1024 - QuickSort
Cerinţa
Se dă un şir lista cu numar elemente, numere întregi. Folosind metoda QuickSort (Sortare Rapidă), 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 ⩽ numar ⩽ 100.000
- element lista ∈ ℤ
- -1.000.000.000 ⩽ element lista ⩽ 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
- Intrare
- abc
- Ieșire
- Datele de intrare nu corespund restricțiilor impuse.
- Intrare
- -25
- Ieșire
- Datele de intrare nu corespund restricțiilor impuse.
Rezolvare
Rezolvare ver. 1
<syntaxhighlight lang="python" line>
- 1024 - Quicksort
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 partition(lista: list, low: int, high: int):
pivot = lista[high]
indice1 = low - 1
for indice2 in range(low, high):
if lista[indice2] <= pivot:
indice1 += 1
lista[indice1], lista[indice2] = lista[indice2], lista[indice1]
lista[indice1 + 1], lista[high] = lista[high], lista[indice1 + 1]
return indice1 + 1
def quicksort(lista: list, low: int, high: int):
if low < high:
poz = partition(lista, low, high)
quicksort(lista, low, poz - 1)
quicksort(lista, poz + 1, high)
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.")
quicksort(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>