1024-QuikSort

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>