Bare usandsynligt flette Sorter , QuickSort er en opdel og hersk algoritme . Den vælger et element som et pivot og opdeler det givne array omkring det valgte pivot.

Der er mange forskellige versioner af quickSort, der vælger pivot på forskellige måder.

1. Vælg altid det første element som en pivot
2. Vælg altid det sidste element som en pivot
3. Vælg et tilfældigt element som pivot
4. Vælg median som omdrejningspunkt

Her vil vi vælge det sidste element som et pivot. Nøgleprocessen i quickSort er partition(). Mål for partitioner er, givet et array og et element 'x' af array som en pivot, at sætte x i dens korrekte position i et sorteret array og sætte alle mindre elementer (mindre end x) før x, og sætte alle større elementer (større end x) efter x. Alt dette skal gøres i lineær tid.

Python Rekursiv QuickSort fungere

// low -->Startindeks, // høj --> Slutindeks quickSort(arr[], lav, høj) { // Indtil startindeks er mindre end slutindeks, hvis (lav // pi er partitioneringsindeks, // arr[p] er nu på det rigtige sted pi = partition(arr, lav, høj); // Før pi quickSort(arr, lav, pi - 1)   
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)>  
  
  
  
  
 
     
 
     
 
   
 
  Produktion   
 
  
Unsorted Array [1, 7, 4, 1, 10, 9, -2] Sorted Array in Ascending Order: [-2, 1, 1, 4, 7, 9, 10] 
  
    Tidskompleksitet:     Worst case tidskompleksitet er O(N   2   ) og den gennemsnitlige sagstidskompleksitet er O(N log N)   
    Hjælpeplads:     O(1)  
  
    Python Quicksort ved hjælp af         listeforståelse       
  
 Quicksort ved hjælp af listeforståelse er en rekursiv algoritme til sortering af en række elementer. Det fungerer ved at vælge et pivot-element og opdele arrayet omkring pivoten, således at alle elementer, der er mindre end pivoten, flyttes til venstre, og alle elementer, der er større end pivoten, flyttes til højre. Derefter anvender den den samme proces rekursivt til venstre og højre underarrays, indtil hele arrayet er sorteret.  
  
    Algoritme:     
  
 1.Hvis input-arrayet har længden 0 eller 1, returneres arrayet, da det allerede er sorteret.   
 2.Vælg det første element i arrayet som pivotelement.   
 3.Opret to tomme lister, venstre og højre.   
 4.For hvert element i arrayet undtagen pivoten:   
 en. Hvis elementet er mindre end pivoten, skal du tilføje det til venstre liste.   
 b. Hvis elementet er større end eller lig med pivoten, skal du tilføje det til den højre liste.   
 5. Kald rekursivt quicksort på venstre og højre lister.   
 6. Sammensæt den sorterede venstre liste, pivotelementet og den sorterede højre liste.   
 7. Returner den sammenkædede liste.  
  
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(venstre) + [pivot] + quicksort(højre) # Eksempel på brug arr = [1, 7, 4, 1, 10, 9, -2] sorted_arr = quicksort(arr) print('Sorteret array i stigende rækkefølge:') print(sorted_arr)>  
  
  
  
  
 
     
 
   
 
     
 
   
 
  Produktion   
 
  
Sorted Array in Ascending Order: [-2, 1, 1, 4, 7, 9, 10] 
  
 Tidskompleksitet er O(n log n)  
  
 Algoritmens rumkompleksitet er O(n)