Sort de combinación poco probable , QuickSort es un algoritmo de divide y vencerás . Selecciona un elemento como pivote y divide la array dada alrededor del pivote elegido. Hay muchas versiones diferentes de quickSort que seleccionan el pivote de diferentes maneras.
- Elija siempre el primer elemento como pivote
- Elija siempre el último elemento como pivote
- Elija un elemento aleatorio como pivote
- Elija la mediana como un 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 array y un elemento ‘x’ de la array como pivote, colocar x en su posición correcta en una array 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.
Pseudocódigo: función QuickSort recursiva
// low --> Starting index,
// high --> Ending index
quickSort(arr[], low, high) {
// Till starting index is lesser than ending index
if (low < high) {
// pi is partitioning index,
// arr[p] is now at right place
pi = partition(arr, low, high);
// Before pi
quickSort(arr, low, pi - 1);
// After 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 def partition(l, r, nums): # Last element will be the pivot and the first element the pointer pivot, ptr = nums[r], l for i in range(l, r): if nums[i] <= pivot: # Swapping values smaller than the pivot to the front nums[i], nums[ptr] = nums[ptr], nums[i] ptr += 1 # Finally swapping the last element with the pointer indexed number nums[ptr], nums[r] = nums[r], nums[ptr] return ptr # With quicksort() function, we will be utilizing the above code to obtain the pointer # at which the left values are all smaller than the number at pointer index and vice versa # for the right values. def quicksort(l, r, nums): if len(nums) == 1: # Terminating Condition for recursion. VERY IMPORTANT! return nums if l < r: pi = partition(l, r, nums) quicksort(l, pi-1, nums) # Recursively sorting the left values quicksort(pi+1, r, nums) # Recursively sorting the right values return nums example = [4, 5, 1, 2, 3] result = [1, 2, 3, 4, 5] print(quicksort(0, len(example)-1, example)) example = [2, 5, 6, 1, 4, 6, 2, 4, 7, 8] result = [1, 2, 2, 4, 4, 5, 6, 6, 7, 8] # As you can see, it works for duplicates too print(quicksort(0, len(example)-1, example))
[1, 2, 3, 4, 5] [1, 2, 2, 4, 4, 5, 6, 6, 7, 8]
Complejidad del tiempo: la complejidad del tiempo del peor de los casos es O(N 2 ) y la complejidad del tiempo del caso promedio es O(N logN)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA