Simplemente improbable fusionar ordenar , QuickSort es un algoritmo divide y vencerás . Elige un elemento como pivote y divide la matriz dada alrededor del pivote seleccionado.

Hay muchas versiones diferentes de QuickSort que seleccionan el pivote de diferentes maneras.

1. Elija siempre el primer elemento como pivote
2. Elija siempre el último elemento como pivote
3. Elija un elemento aleatorio como pivote
4. Elija la mediana como pivote

Aquí elegiremos el último elemento como pivote. El proceso clave en QuickSort es la partición(). El objetivo de las particiones es, dada una matriz y un elemento 'x' de la matriz como pivote, colocar x en su posición correcta en una matriz ordenada y colocar todos los elementos más pequeños (menores que x) antes de x, y colocar todos los elementos mayores (mayores que x) después de x. Todo esto debe hacerse en tiempo lineal.

Pitón Ordenación rápida recursiva función

// low -->Índice inicial, // alto --> Índice final QuickSort(arr[], bajo, alto) { // Hasta que el índice inicial sea menor que el índice final if (low // pi es el índice de partición, // arr[p] es ahora en el lugar correcto pi = partición(arr, low, high); // Antes de pi quickSort(arr, low, pi - 1); // Después de pi quickSort(arr, pi + 1, high); 
Python3
    
 
     
  
 
 

 
    
 
     
     
    
 
 
 

sumador completo
 
 
 
 
 # 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)>
 
 
 
 
    
   
 
>
 
  Producción  
sitio web como coomeet
 
Unsorted Array [1, 7, 4, 1, 10, 9, -2] Sorted Array in Ascending Order: [-2, 1, 1, 4, 7, 9, 10]>
 
    Complejidad del tiempo:    La complejidad del tiempo en el peor de los casos es O(N)2) y la complejidad del tiempo de caso promedio es O (N log N)  
    Espacio Auxiliar:    O(1)
 
    Uso rápido de Python         comprensión de la lista      
 
Quicksort mediante comprensión de listas es un algoritmo recursivo para ordenar una serie de elementos. Funciona seleccionando un elemento pivote y dividiendo la matriz alrededor del pivote, de modo que todos los elementos menores que el pivote se muevan hacia su izquierda y todos los elementos mayores que el pivote se muevan hacia su derecha. Luego, aplica recursivamente el mismo proceso a los subarreglos izquierdo y derecho hasta que se ordena todo el arreglo.
 
    Algoritmo:    
 
1.Si la matriz de entrada tiene una longitud de 0 o 1, devuelva la matriz tal como ya está ordenada.  
2.Elija el primer elemento de la matriz como elemento pivote.  
3.Cree dos listas vacías, izquierda y derecha.  
4.Para cada elemento de la matriz excepto el pivote:  
a. Si el elemento es más pequeño que el pivote, agréguelo a la lista de la izquierda.  
b. Si el elemento es mayor o igual que el pivote, agréguelo a la lista de la derecha.  
5. Llame recursivamente a Quicksort en las listas izquierda y derecha.  
6.Concatene la lista ordenada por la izquierda, el elemento pivote y la lista ordenada por la derecha.  
7.Devuelve la lista concatenada.
 
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>= pivote] return quicksort(izquierda) + [pivote] + quicksort(derecha) # Ejemplo de uso arr = [1, 7, 4, 1, 10, 9, -2] sorted_arr = quicksort(arr) print('Sorted Array en orden ascendente:') print(sorted_arr)>
 
 
 
 
que es un monitor
    
 
>
 
    
 
>
 
  Producción  
 
Sorted Array in Ascending Order: [-2, 1, 1, 4, 7, 9, 10]>
 
La complejidad del tiempo es O (n log n)
 
La complejidad espacial del algoritmo es O (n)