Tik mažai tikėtina sujungti Rūšiuoti , QuickSort yra a skaldyk ir valdyk algoritmas . Jis pasirenka elementą kaip sukimosi tašką ir padalija nurodytą masyvą aplink pasirinktą sukimąsi.

Yra daug skirtingų „quickSort“ versijų, kurios parenkamos įvairiais būdais.

1. Visada pasirinkite pirmąjį elementą kaip sukimąsi
2. Visada pasirinkite paskutinį elementą kaip sukimąsi
3. Pasirinkite atsitiktinį elementą kaip sukimąsi
4. Pasirinkite medianą kaip sukimąsi

Čia mes pasirinksime paskutinį elementą kaip sukimąsi. Pagrindinis greitojo rūšiavimo procesas yra partition (). Skirsnių tikslas yra, jei masyve yra masyvo elementas „x“ kaip sukimosi taškas, įdėkite x į teisingą vietą surūšiuotame masyve ir visus mažesnius elementus (mažesnius nei x) sudėkite prieš x, o visus didesnius elementus (didesnius) nei x) po x. Visa tai turėtų būti daroma tiesiniu laiku.

Python Rekursyvus greitasis rūšiavimas funkcija

// low -->Pradinis indeksas, // aukštas --> Pabaigos indeksas quickSort(arr[], žemas, aukštas) { // Iki pradžios indeksas yra mažesnis nei pabaigos indeksas if (low // pi yra skaidymo indeksas, // arr[p] dabar yra teisingoje vietoje pi = partition(arr, low, high // Prieš pi quickSort(arr, low, pi - 1) // Po pi quickSort(arr, pi + 1, high } }>'>);   
Python3 
     
 
  
     
   
  
     
  
     
     
     
  
 
  
  
  
  
  # Python program for implementation of Quicksort Sort>   # This implementation utilizes pivot as the last element in the nums list>   # It has a pointer to keep track of the elements smaller than the pivot>   # At the very end of partition() function, the pointer is swapped with the pivot>   # to come up with a 'sorted' nums relative to the pivot>   # Function to find the partition position>   def>   partition(array, low, high):>   >  # choose the rightmost element as pivot>   >  pivot>  =>   array[high]>   >  # pointer for greater element>   >  i>  =>   low>  ->   1>   >  # traverse through all elements>   >  # compare each element with pivot>   >  for>   j>  in>   range>  (low, high):>   >  if>   array[j]  <>  =>   pivot:>   >  # If element smaller than pivot is found>   >  # swap it with the greater element pointed by i>   >  i>  =>   i>  +>   1>   >  # Swapping element at i with element at j>   >  (array[i], array[j])>  =>   (array[j], array[i])>   >  # Swap the pivot element with the greater element specified by i>   >  (array[i>  +>   1>  ], array[high])>  =>   (array[high], array[i>  +>   1>  ])>   >  # Return the position from where partition is done>   >  return>   i>  +>   1>   # function to perform quicksort>   def>   quickSort(array, low, high):>   >  if>   low   # Find pivot element such that  # element smaller than pivot are on the left  # element greater than pivot are on the right  pi = partition(array, low, high)  # Recursive call on the left of pivot  quickSort(array, low, pi - 1)  # Recursive call on the right of pivot  quickSort(array, pi + 1, high) data = [1, 7, 4, 1, 10, 9, -2] print('Unsorted Array') print(data) size = len(data) quickSort(data, 0, size - 1) print('Sorted Array in Ascending Order:') print(data)>  
  
  
  
  
 
     
 
     
 
   
 
  Išvestis   
 
  
Unsorted Array [1, 7, 4, 1, 10, 9, -2] Sorted Array in Ascending Order: [-2, 1, 1, 4, 7, 9, 10] 
  
    Laiko sudėtingumas:     Blogiausio atvejo laiko sudėtingumas yra O(N   2   ) ir vidutinis atvejo sudėtingumas yra O(N log N)   
    Pagalbinė erdvė:     O(1)  
  
    Python Quicksort naudojimas         sąrašo supratimas       
  
 Greitasis rūšiavimas naudojant sąrašo supratimą yra rekursinis elementų masyvo rūšiavimo algoritmas. Jis veikia pasirenkant sukimosi elementą ir padalijant masyvą aplink šerdesą taip, kad visi elementai, mažesni už sukimąsi, būtų perkeliami į kairę, o visi elementai, didesni už sukimąsi, būtų perkeliami į dešinę. Tada jis rekursyviai taiko tą patį procesą kairiajam ir dešiniajam antriniams masyvams, kol bus surūšiuotas visas masyvas.  
  
    Algoritmas:     
  
 1.Jei įvesties masyvo ilgis yra 0 arba 1, grąžinkite masyvą tokį, koks jis jau surūšiuotas.   
 2. Pasirinkite pirmąjį masyvo elementą kaip sukimo elementą.   
 3. Sukurkite du tuščius sąrašus – kairėje ir dešinėje.   
 4. Kiekvienam masyvo elementui, išskyrus sukimąsi:   
 a. Jei elementas yra mažesnis už suvestinę, pridėkite jį prie kairiojo sąrašo.   
 b. Jei elementas yra didesnis arba lygus sukamiesiems, pridėkite jį prie dešiniojo sąrašo.   
 5. Rekursyviai iškvieskite greitąjį rūšiavimą kairiajame ir dešiniajame sąrašuose.   
 6. Sujunkite surūšiuotą kairįjį sąrašą, sukimo elementą ir surūšiuotą dešinįjį sąrašą.   
 7. Grąžinkite sujungtą sąrašą.  
  
Python3 
     
 
  
     
   
  
     
  
     
     
     
  
 
  
  
  
  
  # Approach 2: Quicksort using list comprehension>   def>   quicksort(arr):>   >  if>   len>  (arr)  <>  =>   1>  :>   >  return>   arr>   >  else>  :>   >  pivot>  =>   arr[>  0>  ]>   >  left>  =>   [x>  for>   x>  in>   arr[>  1>  :]>  if>   x   right = [x for x in arr[1:] if x>= Pivot] return Quicksort(left) + [Pivot] + Quicksort(right) # Naudojimo pavyzdys arr = [1, 7, 4, 1, 10, 9, -2] sorted_arr = quicksort(arr) print('Sorted Array didėjimo tvarka:') print(sorted_arr)>  
  
  
  
  
 
     
 
   
 
     
 
   
 
  Išvestis   
 
  
Sorted Array in Ascending Order: [-2, 1, 1, 4, 7, 9, 10] 
  
 Laiko sudėtingumas yra O(n log n)  
  
 Algoritmo erdvės sudėtingumas yra O(n)