2700 - RadixSort - Revision history

Monica Dragos: /* Date de ieșire */

2023-05-04T20:43:53Z

Date de ieșire

← Older revision		Revision as of 20:43, 4 May 2023
Line 6:		Line 6:

	==Date de ieșire==		==Date de ieșire==
	Fișierul de ieșire radixsort.out va conține pe prima linie n numere naturale, anume șirul sortat~~. În~~ consolă se va scrie un mesaj de validare al input-ului("Input valid!" ~~sau~~ "Input invalid!" ~~după caz)~~.		Fișierul de ieșire radixsort.out va conține pe prima linie n numere naturale, anume șirul sortat, iar în consolă se va scrie un mesaj de validare al input-ului "Input valid!". În caz contrar, pe consolă se va afișa mesajul "Input invalid!".

	==Restricții și precizări==		==Restricții și precizări==

Cata at 06:22, 3 May 2023

2023-05-03T06:22:42Z

← Older revision		Revision as of 06:22, 3 May 2023
Line 6:		Line 6:

	==Date de ieșire==		==Date de ieșire==
	Fișierul de ieșire radixsort.out va conține pe prima linie n numere naturale, anume șirul sortat. În consolă se va scrie un mesaj de validare al input-ului.		Fișierul de ieșire radixsort.out va conține pe prima linie n numere naturale, anume șirul sortat. În consolă se va scrie un mesaj de validare al input-ului("Input valid!" sau "Input invalid!" după caz).

	==Restricții și precizări==		==Restricții și precizări==
Line 86:		Line 86:

	==Explicație==		==Explicație==
	Acest cod implementează algoritmul de sortare radix ~~(în baza unui număr întreg fixat)~~ pe ~~un set~~ de ~~numere~~ întregi ~~date prin fișierul "radixsort.in" și returnează numerele sortate prin fișierul "radixsort.out"~~.		Acest cod implementează algoritmul de sortare radix sort pe o listă de întregi.

	Funcția getMax ~~găsește valoarea maximă~~ din ~~lista de intrare~~.		Funcția `getMax(n, arr)` primește ca parametrii un număr întreg `n` și o listă de `n` întregi `arr`, și returnează cel mai mare element din listă.

	Funcția validateInput ~~verifică dacă lista~~ de ~~intrare are dimensiunea corectă~~ și dacă ~~toate~~ elementele ~~sunt în intervalul [-~~999999999~~, 999999999]~~.		Funcția `validateInput(n, arr)` primește ca parametrii un număr întreg `n` și o listă de `n` întregi `arr`, și returnează `True` dacă input-ul este valid (adică `n` este între 2 și 1000000 și toți elementele din listă au valori absolute mai mici decât 999999999) și `False` altfel.

	Funcția countingSort ~~sortează lista~~ de ~~intrare în funcție~~ de ~~un anumit~~ exp (baza ~~numărului fixat) utilizând sortarea prin numărare~~.		Funcția `countingSort(n, exp, arr, output)` primește ca parametrii un număr întreg `n`, un număr întreg `exp`, o listă de `n` întregi `arr` și o listă de `n` întregi `output`. Implementează algoritmul de sortare counting sort pentru o cifră specifică (dată de `exp`), în baza 32. Folosește un array `count` de dimensiune 32 pentru a număra de câte ori apare fiecare cifră și apoi reordonează lista `arr` în ordinea specificată de cifra respectivă.

	Funcția radixSort ~~utilizează celelalte funcții pentru a sorta lista~~ de ~~intrare~~ prin ~~sortarea radix~~.		Funcția `radixSort(n, arr)` primește ca parametrii un număr întreg `n` și o listă de `n` întregi `arr`. Implementează algoritmul de sortare radix sort, iterând prin fiecare cifră a numerelor și apelând funcția `countingSort` pentru fiecare cifră în parte, începând cu cifra cea mai puțin semnificativă.

	~~Codul deschide~~ fișierul "radixsort.in", ~~citește datele de intrare~~, ~~verifică dacă datele~~ de ~~intrare sunt valide~~, ~~sortează datele de intrare utilizând sortarea radix~~ și ~~scrie datele de ieșire sortate~~ în fișierul "radixsort.out".		Funcția `__main__` citește input-ul din fișierul "radixsort.in", validează input-ul folosind funcția `validateInput`, sortează lista de numere folosind `radixSort`, și afișează rezultatul în fișierul "radixsort.out".

Cata at 07:30, 28 April 2023

2023-04-28T07:30:22Z

← Older revision		Revision as of 07:30, 28 April 2023
Line 6:		Line 6:

	==Date de ieșire==		==Date de ieșire==
	Fișierul de ieșire radixsort.out va conține pe prima linie n numere naturale, anume șirul sortat.		Fișierul de ieșire radixsort.out va conține pe prima linie n numere naturale, anume șirul sortat. În consolă se va scrie un mesaj de validare al input-ului.

	==Restricții și precizări==		==Restricții și precizări==
Line 12:		Line 12:
	* numerele de pe a doua linie a fișierului de intrare vor avea maximum 9 cifre.		* numerele de pe a doua linie a fișierului de intrare vor avea maximum 9 cifre.
	==Exemplu==		==Exemplu==
	radixsort.in		; radixsort.in
			: 8
	8		: 170 20 45 75 90 802 24 2
	170 20 45 75 90 802 24 2		; radixsort.out
	radixsort.out		: 2 20 24 45 75 90 170 802
			; Ieșire consolă
	2 20 24 45 75 90 170 802		: Input valid

	==Rezolvare==		==Rezolvare==
	<syntaxhighlight lang="python">		<syntaxhighlight lang="python">
Line 76:		Line 75:
	print("Input invalid!")		print("Input invalid!")
	exit()		exit()
			else:
			print("Input valid!")

	radixSort(n, arr)		radixSort(n, arr)

Cata: Pagină nouă: ==Cerința== Fiind dat un șir cu n elemente, nu neapărat distincte, se cere sortarea crescătoare a acestuia folosind metoda Radix Sort. ==Date de intrare== Fișierul de intrare radixsort.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații. ==Date de ieșire== Fișierul de ieșire radixsort.out va conține pe prima linie n numere naturale, anume șirul sortat. ==Restricții și precizări== * 2 ⩽ n ⩽ 1.000.000; * num...

2023-04-20T15:26:15Z

Pagină nouă: ==Cerința== Fiind dat un șir cu n elemente, nu neapărat distincte, se cere sortarea crescătoare a acestuia folosind metoda Radix Sort. ==Date de intrare== Fișierul de intrare radixsort.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații. ==Date de ieșire== Fișierul de ieșire radixsort.out va conține pe prima linie n numere naturale, anume șirul sortat. ==Restricții și precizări== * 2 ⩽ n ⩽ 1.000.000; * num...

New page

==Cerința==
Fiind dat un șir cu n elemente, nu neapărat distincte, se cere sortarea crescătoare a acestuia folosind metoda Radix Sort.

==Date de intrare==
Fișierul de intrare radixsort.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

==Date de ieșire==
Fișierul de ieșire radixsort.out va conține pe prima linie n numere naturale, anume șirul sortat.

==Restricții și precizări==
* 2 &les; n &les; 1.000.000;
* numerele de pe a doua linie a fișierului de intrare vor avea maximum 9 cifre.
==Exemplu==
radixsort.in

8
170 20 45 75 90 802 24 2
radixsort.out

2 20 24 45 75 90 170 802

==Rezolvare==
<syntaxhighlight lang="python">
import math

def getMax(n, arr):
maxX = arr[0]
for i in range(1, n):
if arr[i] > maxX:
maxX = arr[i]
return maxX

def validateInput(n, arr):
if n < 2 or n > 1000000:
return False

for i in range(n):
if abs(arr[i]) > 999999999:
return False

return True

def countingSort(n, exp, arr, output):
count = [0] * 32

for i in range(n):
count[(arr[i]//exp)%32] += 1

for i in range(1, 32):
count[i] += count[i - 1]

for i in range(n - 1, -1, -1):
output[count[(arr[i]//exp)%32] - 1] = arr[i]
count[(arr[i]//exp)%32] -= 1

for i in range(n):
arr[i] = output[i]

def radixSort(n, arr):
m = getMax(n, arr)

output = [0] * n

exp = 1
while m // exp > 0:
countingSort(n, exp, arr, output)
exp *= 32

if __name__ == '__main__':
with open("radixsort.in", "r") as fin:
with open("radixsort.out", "w") as fout:
n = int(fin.readline())
arr = list(map(int, fin.readline().split()))

if not validateInput(n, arr):
print("Input invalid!")
exit()

radixSort(n, arr)

for i in range(n):
fout.write(str(arr[i]) + ' ')

</syntaxhighlight>

==Explicație==
Acest cod implementează algoritmul de sortare radix (în baza unui număr întreg fixat) pe un set de numere întregi date prin fișierul "radixsort.in" și returnează numerele sortate prin fișierul "radixsort.out".

Funcția getMax găsește valoarea maximă din lista de intrare.

Funcția validateInput verifică dacă lista de intrare are dimensiunea corectă și dacă toate elementele sunt în intervalul [-999999999, 999999999].

Funcția countingSort sortează lista de intrare în funcție de un anumit exp (baza numărului fixat) utilizând sortarea prin numărare.

Funcția radixSort utilizează celelalte funcții pentru a sorta lista de intrare prin sortarea radix.

Codul deschide fișierul "radixsort.in", citește datele de intrare, verifică dacă datele de intrare sunt valide, sortează datele de intrare utilizând sortarea radix și scrie datele de ieșire sortate în fișierul "radixsort.out".