Larisa.Chiș at 15:38, 7 January 2023

2023-01-07T15:38:03Z

← Older revision		Revision as of 15:38, 7 January 2023
Line 25:		Line 25:

	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	~~‘’’~~
	def QuickSort(arr):		def QuickSort(arr):

Line 60:		Line 60:
	print("Original Array: ",array_to_be_sorted)		print("Original Array: ",array_to_be_sorted)
	print("Sorted Array: ",QuickSort(array_to_be_sorted))		print("Sorted Array: ",QuickSort(array_to_be_sorted))
	~~‘’’~~
	</syntaxhighlight>		</syntaxhighlight>

Larisa.Chiș: Pagină nouă: == Cerința == Se dă un șir cu n 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 n, iar apoi cele n elemente ale șirului. == Date de ieșire == Programul va afișa pe ecran elementele șirului sortat, separate prin exact un spațiu == Restricții si precizări == 1 ≤ n ≤ 100.000 elementele șirului vor fi cuprinse între -1.000.000...

2023-01-07T15:37:20Z

Pagină nouă: == Cerința == Se dă un șir cu n 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 n, iar apoi cele n elemente ale șirului. == Date de ieșire == Programul va afișa pe ecran elementele șirului sortat, separate prin exact un spațiu == Restricții si precizări == 1 ≤ n ≤ 100.000 elementele șirului vor fi cuprinse între -1.000.000...

New page

== Cerința ==
Se dă un șir cu n 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 n, iar apoi cele n elemente ale șirului.

== Date de ieșire ==
Programul va afișa pe ecran elementele șirului sortat, separate prin exact un spațiu

== Restricții si precizări ==
1 ≤ n ≤ 100.000
elementele șirului vor fi cuprinse între -1.000.000.000 și 1.000.000.000

== Exemplu ==
Intrare

12
10 0 -1 -3 1 -4 9 3 -1 -4 3 -4

Ieșire

-4 -4 -4 -3 -1 -1 0 1 3 3 9 10

== Rezolvare ==

<syntaxhighlight lang="python" line>
‘’’
def QuickSort(arr):

elements = len(arr)

#Base case
if elements < 2:
return arr

current_position = 0 #Position of the partitioning element

for i in range(1, elements): #Partitioning loop
if arr[i] <= arr[0]:
current_position += 1
temp = arr[i]
arr[i] = arr[current_position]
arr[current_position] = temp

temp = arr[0]
arr[0] = arr[current_position]
arr[current_position] = temp #Brings pivot to it's appropriate position

left = QuickSort(arr[0:current_position]) #Sorts the elements to the left of pivot
right = QuickSort(arr[current_position+1:elements]) #sorts the elements to the right of pivot

arr = left + [arr[current_position]] + right #Merging everything together

return arr

array_to_be_sorted = input('Introduceti o lista de numere, separate prin spatiu:')
array_to_be_sorted = array_to_be_sorted.split()
print("Original Array: ",array_to_be_sorted)
print("Sorted Array: ",QuickSort(array_to_be_sorted))
‘’’
</syntaxhighlight>

1024-QuikSort - Revision history

Larisa.Chiș at 15:38, 7 January 2023