recursivo - quicksort python

Quicksort con Python

Question

Soy totalmente nuevo en Python y estoy tratando de implementar quicksort en él. ¿Podría alguien ayudarme a completar mi código?

No sé cómo concatenar las tres matrices e imprimirlas.

def sort(array=[12,4,5,6,7,3,1,15]):
less = []
equal = []
greater = []
if len(array) > 1:
pivot = array[0]
for x in array:
if x < pivot:
less.append(x)
if x == pivot:
equal.append(x)
if x > pivot:
greater.append(x)
sort(less)
sort(pivot)
sort(greater)

Answer 1

Quicksort con Python

En la vida real, siempre debemos usar el tipo incorporado provisto por Python. Sin embargo, entender el algoritmo de quicksort es instructivo.

Mi objetivo aquí es desglosar el tema de modo que el lector lo pueda entender y reproducir fácilmente sin tener que regresar a los materiales de referencia.

El algoritmo de quicksort es esencialmente el siguiente:

1. Seleccione un punto de datos de pivote.
2. Mueva todos los puntos de datos por debajo de (debajo) el pivote a una posición debajo del pivote: mueva los que estén por encima o por encima (arriba) del pivote a una posición superior.
3. Aplicar el algoritmo a las áreas arriba y debajo del pivote

Si los datos se distribuyen aleatoriamente, seleccionar el primer punto de datos como pivote equivale a una selección aleatoria.

Ejemplo legible:

Primero, veamos un ejemplo legible que usa comentarios y nombres de variables para apuntar a valores intermedios:

def quicksort(xs):
"""Given indexable and slicable iterable, return a sorted list"""
if xs: # if given list (or tuple) with one ordered item or more:
pivot = xs[0]
# below will be less than:
below = [i for i in xs[1:] if i < pivot]
# above will be greater than or equal to:
above = [i for i in xs[1:] if i >= pivot]
return quicksort(below) + [pivot] + quicksort(above)
else:
return xs # empty list

Para replantear el algoritmo y el código que se muestran aquí, movemos los valores por encima del pivote a la derecha y los valores por debajo del pivote a la izquierda, y luego pasamos esas particiones a la misma función para clasificarlas más.

Golfed:

Esto se puede jugar golf a 88 caracteres:

q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])

Para ver cómo llegamos allí, primero tome nuestro ejemplo legible, elimine los comentarios y las cadenas de documentos, y encuentre el pivote en su lugar:

def quicksort(xs):
if xs:
below = [i for i in xs[1:] if i < xs[0]]
above = [i for i in xs[1:] if i >= xs[0]]
return quicksort(below) + [xs[0]] + quicksort(above)
else:
return xs

Ahora encuentra abajo y arriba, en el lugar:

def quicksort(xs):
if xs:
return (quicksort([i for i in xs[1:] if i < xs[0]] )
+ [xs[0]]
+ quicksort([i for i in xs[1:] if i >= xs[0]]))
else:
return xs

Ahora, sabiendo eso and devuelve el elemento anterior si es falso, de lo contrario, si es verdadero, evalúa y devuelve el siguiente elemento, tenemos:

def quicksort(xs):
return xs and (quicksort([i for i in xs[1:] if i < xs[0]] )
+ [xs[0]]
+ quicksort([i for i in xs[1:] if i >= xs[0]]))

Dado que lambdas devuelve una sola epresión, y hemos simplificado a una sola expresión (a pesar de que cada vez es más ilegible), ahora podemos usar una lambda:

quicksort = lambda xs: (quicksort([i for i in xs[1:] if i < xs[0]] )
+ [xs[0]]
+ quicksort([i for i in xs[1:] if i >= xs[0]]))

Y para reducir nuestro ejemplo, acorte la función y los nombres de las variables a una letra, y elimine los espacios en blanco que no se requieren.

q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])

Tenga en cuenta que este lambda, como la mayoría de los códigos de golf, es un estilo bastante malo.

Quicksort en el lugar, usando el esquema de Partición de Hoare

La implementación anterior crea muchas listas adicionales innecesarias. Si podemos hacer esto en el lugar, evitaremos desperdiciar espacio.

La implementación a continuación usa el esquema de particiones de Hoare, sobre el cual puede leer más sobre wikipedia (pero aparentemente hemos eliminado hasta 4 cálculos redundantes por llamada de partition() usando la semántica while-loop en lugar de do-while y moviendo los pasos de estrechamiento a el final del ciclo while externo).

def quicksort(a_list):
"""Hoare partition scheme, see https://en.wikipedia.org/wiki/Quicksort"""
def _quicksort(a_list, low, high):
# must run partition on sections with 2 elements or more
if low < high:
p = partition(a_list, low, high)
_quicksort(a_list, low, p)
_quicksort(a_list, p+1, high)
def partition(a_list, low, high):
pivot = a_list[low]
while True:
while a_list[low] < pivot:
low += 1
while a_list[high] > pivot:
high -= 1
if low >= high:
return high
a_list[low], a_list[high] = a_list[high], a_list[low]
low += 1
high -= 1
_quicksort(a_list, 0, len(a_list)-1)
return a_list

No estoy seguro si lo probé lo suficiente:

def main():
assert quicksort([1]) == [1]
assert quicksort([1,2]) == [1,2]
assert quicksort([1,2,3]) == [1,2,3]
assert quicksort([1,2,3,4]) == [1,2,3,4]
assert quicksort([2,1,3,4]) == [1,2,3,4]
assert quicksort([1,3,2,4]) == [1,2,3,4]
assert quicksort([1,2,4,3]) == [1,2,3,4]
assert quicksort([2,1,1,1]) == [1,1,1,2]
assert quicksort([1,2,1,1]) == [1,1,1,2]
assert quicksort([1,1,2,1]) == [1,1,1,2]
assert quicksort([1,1,1,2]) == [1,1,1,2]

Conclusión

Este algoritmo se enseña con frecuencia en cursos de informática y se solicita entrevistas de trabajo. Nos ayuda a pensar en la recursión y divide y vencerás.

Quicksort no es muy práctico en Python ya que nuestro algoritmo de timsort incorporado es bastante eficiente, y tenemos límites de recursión. Esperaríamos ordenar las listas in situ con list.sort o crear nuevas listas sorted con sorted ; ambas tienen una key y reverse argumento reverse .

Answer 2

1. Primero declaramos que el primer valor en la matriz es el valor_pivote y también establecemos las marcas izquierda y derecha
2. Creamos el primer ciclo while, este while loop está ahí para decirle al proceso de partición que se ejecute nuevamente si no cumple con la condición necesaria
3. luego aplicamos el proceso de partición
4. después de que se hayan ejecutado ambos procesos de partición, verificamos si cumple la condición adecuada. Si lo hace, lo marcamos como hecho, si no cambiamos los valores de la izquierda y la derecha y lo aplicamos de nuevo
5. Una vez hecho esto, cambie los valores de la izquierda y la derecha y devuelva el punto de división

¡Adjunto el código a continuación! Este quicksort es una gran herramienta de aprendizaje debido a la ubicación del valor de pivote . Como está en un lugar constante, puedes caminar varias veces y realmente entender cómo funciona todo. En la práctica, es mejor aleatorizar el pivote para evitar el tiempo de ejecución O (N ^ 2).

def quicksort10(alist):
quicksort_helper10(alist, 0, len(alist)-1)
def quicksort_helper10(alist, first, last):
""" """
if first < last:
split_point = partition10(alist, first, last)
quicksort_helper10(alist, first, split_point - 1)
quicksort_helper10(alist, split_point + 1, last)
def partition10(alist, first, last):
done = False
pivot_value = alist[first]
leftmark = first + 1
rightmark = last
while not done:
while leftmark <= rightmark and alist[leftmark] <= pivot_value:
leftmark = leftmark + 1
while leftmark <= rightmark and alist[rightmark] >= pivot_value:
rightmark = rightmark - 1
if leftmark > rightmark:
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp
temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp
return rightmark

Answer 3

Aquí hay una implementación fácil:

def quicksort(array):
if len(array) < 2:
return array
else:
pivot= array[0]
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([10, 5, 2, 3]))

Answer 4

Clasificación rápida sin memoria adicional (en su lugar)

Uso:

array = [97, 200, 100, 101, 211, 107]
quicksort(array)
# array -> [97, 100, 101, 107, 200, 211]

def partition(array, begin, end):
pivot = begin
for i in xrange(begin+1, end+1):
if array[i] <= array[begin]:
pivot += 1
array[i], array[pivot] = array[pivot], array[i]
array[pivot], array[begin] = array[begin], array[pivot]
return pivot
def quicksort(array, begin=0, end=None):
if end is None:
end = len(array) - 1
def _quicksort(array, begin, end):
if begin >= end:
return
pivot = partition(array, begin, end)
_quicksort(array, begin, pivot-1)
_quicksort(array, pivot+1, end)
return _quicksort(array, begin, end)

Answer 5

Creo que ambas respuestas aquí funcionan bien para la lista proporcionada (que responde a la pregunta original), pero se romperían si se pasa una matriz que contiene valores no únicos. Entonces, para completar, solo señalaría el pequeño error en cada uno y explicaré cómo solucionarlos.

Por ejemplo, tratando de ordenar la siguiente matriz [12,4,5,6,7,3,1,15,1] (Tenga en cuenta que 1 aparece dos veces) con el algoritmo de ... en algún momento terminará con menos matriz vacía y la matriz igual con un par de valores (1,1) que no se pueden separar en la siguiente iteración y len ()> 1 ... por lo tanto, terminará con un ciclo infinito

Puede solucionarlo devolviendo el conjunto si hay menos vacío o mejor al no ordenar en su matriz igual, como en la respuesta

def sort(array=[12,4,5,6,7,3,1,15]):
less = []
equal = []
greater = []
if len(array) > 1:
pivot = array[0]
for x in array:
if x < pivot:
less.append(x)
if x == pivot:
equal.append(x)
if x > pivot:
greater.append(x)
# Don''t forget to return something!
return sort(less)+ equal +sort(greater) # Just use the + operator to join lists
# Note that you want equal ^^^^^ not pivot
else: # You need to hande the part at the end of the recursion - when you only have one element in your array, just return the array.
return array

La solución más elegante también se rompe, pero por una causa diferente, falta la cláusula return en la línea de recursión, lo que ocasionará que en algún momento devuelva None e intente agregarlo a una lista ....

Para solucionarlo solo agrega un retorno a esa línea

def qsort(arr):
if len(arr) <= 1:
return arr
else:
return qsort([x for x in arr[1:] if x<arr[0]]) + [arr[0]] + qsort([x for x in arr[1:] if x>=arr[0]])

Answer 6

Ejemplo completo con variables impresas en el paso de la partición:

def partition(data, p, right):
print("/n==> Enter partition: p={}, right={}".format(p, right))
pivot = data[right]
print("pivot = data[{}] = {}".format(right, pivot))
i = p - 1 # this is a dangerous line
for j in range(p, right):
print("j: {}".format(j))
if data[j] <= pivot:
i = i + 1
print("new i: {}".format(i))
print("swap: {} <-> {}".format(data[i], data[j]))
data[i], data[j] = data[j], data[i]
print("swap2: {} <-> {}".format(data[i + 1], data[right]))
data[i + 1], data[right] = data[right], data[i + 1]
return i + 1
def quick_sort(data, left, right):
if left < right:
pivot = partition(data, left, right)
quick_sort(data, left, pivot - 1)
quick_sort(data, pivot + 1, right)
data = [2, 8, 7, 1, 3, 5, 6, 4]
print("Input array: {}".format(data))
quick_sort(data, 0, len(data) - 1)
print("Output array: {}".format(data))

Answer 7

El algoritmo tiene 4 pasos simples:

1. Divida la matriz en 3 partes diferentes: izquierda, pivote y derecha, donde el pivote tendrá solo un elemento. Vamos a elegir este elemento pivote como el primer elemento de matriz
2. Añada elementos a la parte respectiva comparándolos con el elemento pivote. (explicación en comentarios)
3. Repita este algoritmo hasta que todos los elementos de la matriz hayan sido ordenados
4. Finalmente, unir las partes izquierda + pivote + derecha

Código para el algoritmo en python:

def my_sort(A):
p=A[0] #determine pivot element.
left=[] #create left array
right=[] #create right array
for i in range(1,len(A)):
#if cur elem is less than pivot, add elem in left array
if A[i]< p:
left.append(A[i])
#the recurssion will occur only if the left array is atleast half the size of original array
if len(left)>1 and len(left)>=len(A)//2:
left=my_sort(left) #recursive call
elif A[i]>p:
right.append(A[i]) #if elem is greater than pivot, append it to right array
if len(right)>1 and len(right)>=len(A)//2: # recurssion will occur only if length of right array is atleast the size of original array
right=my_sort(right)
A=left+[p]+right #append all three part of the array into one and return it
return A
my_sort([12,4,5,6,7,3,1,15])

Continúa con este algoritmo recursivamente con las partes izquierda y derecha.

Answer 8

Esta es una versión del quicksort que usa el esquema de partición Hoare y con menos swaps y variables locales

def quicksort(array):
qsort(array, 0, len(array)-1)
def qsort(A, lo, hi):
if lo < hi:
p = partition(A, lo, hi)
qsort(A, lo, p)
qsort(A, p + 1, hi)
def partition(A, lo, hi):
pivot = A[lo]
i, j = lo-1, hi+1
while True:
i += 1
j -= 1
while(A[i] < pivot): i+= 1
while(A[j] > pivot ): j-= 1
if i >= j:
return j
A[i], A[j] = A[j], A[i]
test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
print quicksort(test)

Answer 9

Hay otra versión concisa y hermosa

def qsort(arr):
if len(arr) <= 1:
return arr
else:
return qsort([x for x in arr[1:] if x<arr[0]]) + [arr[0]] + qsort([x for x in arr[1:] if x>=arr[0]])
# this comment is just to improve readability due to horizontal scroll!!!

Permítanme explicar los códigos anteriores para más detalles

1. elige el primer elemento de la matriz arr[0] como pivote

   [arr[0]]

2. qsort esos elementos de matriz que son menos que pivote con List Comprehension

   qsort([x for x in arr[1:] if x<arr[0]])

3. qsort aquellos elementos de matriz que son más grandes que pivote con List Comprehension

   qsort([x for x in arr[1:] if x>=arr[0]])

Answer 10

O si prefiere una línea que también ilustre el equivalente de Python de varags C / C ++, expresiones lambda y expresiones if:

qsort = lambda x=None, *xs: [] if x is None else qsort(*[a for a in xs if a<x]) + [x] + qsort(*[a for a in xs if a>=x])

Answer 11

Otra implementación de quicksort:

# A = Array
# s = start index
# e = end index
# p = pivot index
# g = greater than pivot boundary index
def swap(A,i1,i2):
A[i1], A[i2] = A[i2], A[i1]
def partition(A,g,p):
# O(n) - just one for loop that visits each element once
for j in range(g,p):
if A[j] <= A[p]:
swap(A,j,g)
g += 1
swap(A,p,g)
return g
def _quicksort(A,s,e):
# Base case - we are sorting an array of size 1
if s >= e:
return
# Partition current array
p = partition(A,s,e)
_quicksort(A,s,p-1) # Left side of pivot
_quicksort(A,p+1,e) # Right side of pivot
# Wrapper function for the recursive one
def quicksort(A):
_quicksort(A,0,len(A)-1)
A = [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,-1]
print(A)
quicksort(A)
print(A)

Answer 12

Si busco "implementación de python quicksort" en Google, esta pregunta es el primer resultado que aparecerá. Entiendo que la pregunta inicial fue "ayudar a corregir el código", pero ya hay muchas respuestas que no tienen en cuenta esa solicitud: la segunda más votada en la actualidad, el horrendo juego de one-liner con el hilarante comentario "Estás despedido" y, en general , muchas implementaciones que no están en su lugar (es decir, usan memoria extra proporcional al tamaño de la lista de entrada). Esta respuesta proporciona una solución en el lugar pero es para python 2.x Por lo tanto, a continuación sigue mi interpretación de la solución in situ de Rosetta Code, que también funcionará bien para python 3 :

import random
def qsort(l, fst, lst):
if fst >= lst: return
i, j = fst, lst
pivot = l[random.randint(fst, lst)]
while i <= j:
while l[i] < pivot: i += 1
while l[j] > pivot: j -= 1
if i <= j:
l[i], l[j] = l[j], l[i]
i, j = i + 1, j - 1
qsort(l, fst, j)
qsort(l, i, lst)

Y si está dispuesto a renunciar a la propiedad en el lugar, a continuación hay otra versión que ilustra mejor las ideas básicas detrás del servicio rápido. Además de la legibilidad, su otra ventaja es que es estable (los elementos iguales aparecen en la lista ordenada en el mismo orden que solían tener en la lista desordenada). Esta propiedad de estabilidad no se cumple con la implementación in situ menos hambrienta de memoria presentada anteriormente.

def qsort(l):
if not l: return l # empty sequence case
pivot = l[random.choice(range(0, len(l)))]
head = qsort([elem for elem in l if elem < pivot])
tail = qsort([elem for elem in l if elem > pivot])
return head + [elem for elem in l if elem == pivot] + tail

Answer 13

Una implementación in situ "verdadera" [Algoritmos 8.9, 8.11 del Libro de Diseño y Aplicaciones de Algoritmos de Michael T. Goodrich y Roberto Tamassia]:

from random import randint
def partition (A, a, b):
p = randint(a,b)
# or mid point
# p = (a + b) / 2
piv = A[p]
# swap the pivot with the end of the array
A[p] = A[b]
A[b] = piv
i = a # left index (right movement ->)
j = b - 1 # right index (left movement <-)
while i <= j:
# move right if smaller/eq than/to piv
while A[i] <= piv and i <= j:
i += 1
# move left if greater/eq than/to piv
while A[j] >= piv and j >= i:
j -= 1
# indices stopped moving:
if i < j:
# swap
t = A[i]
A[i] = A[j]
A[j] = t
# place pivot back in the right place
# all values < pivot are to its left and
# all values > pivot are to its right
A[b] = A[i]
A[i] = piv
return i
def IpQuickSort (A, a, b):
while a < b:
p = partition(A, a, b) # p is pivot''s location
#sort the smaller partition
if p - a < b - p:
IpQuickSort(A,a,p-1)
a = p + 1 # partition less than p is sorted
else:
IpQuickSort(A,p+1,b)
b = p - 1 # partition greater than p is sorted
def main():
A = [12,3,5,4,7,3,1,3]
print A
IpQuickSort(A,0,len(A)-1)
print A
if __name__ == "__main__": main()

Answer 14

Ya hay muchas respuestas a esto, pero creo que este enfoque es la implementación más limpia:

def quicksort(arr):
""" Quicksort a list
:type arr: list
:param arr: List to sort
:returns: list -- Sorted list
"""
if not arr:
return []
pivots = [x for x in arr if x == arr[0]]
lesser = quicksort([x for x in arr if x < arr[0]])
greater = quicksort([x for x in arr if x > arr[0]])
return lesser + pivots + greater

Por supuesto, puede omitir el almacenamiento de todo en variables y devolverlas de inmediato así:

def quicksort(arr):
""" Quicksort a list
:type arr: list
:param arr: List to sort
:returns: list -- Sorted list
"""
if not arr:
return []
return quicksort([x for x in arr if x < arr[0]]) /
+ [x for x in arr if x == arr[0]] /
+ quicksort([x for x in arr if x > arr[0]])

Answer 15

enfoque de programación funcional

smaller = lambda xs, y: filter(lambda x: x <= y, xs)
larger = lambda xs, y: filter(lambda x: x > y, xs)
qsort = lambda xs: qsort(smaller(xs[1:],xs[0])) + [xs[0]] + qsort(larger(xs[1:],xs[0])) if xs != [] else []
print qsort([3,1,4,2,5]) == [1,2,3,4,5]

Answer 16

enfoque funcional:

def qsort(list):
if len(list) < 2:
return list
pivot = list.pop()
left = filter(lambda x: x <= pivot, list)
right = filter(lambda x: x > pivot, list)
return qsort(left) + [pivot] + qsort(right)

Answer 17

tipo inlace

def qsort(a, b=0, e=None):
# partitioning
def part(a, start, end):
p = start
for i in xrange(start+1, end):
if a[i] < a[p]:
a[i], a[p+1] = a[p+1], a[i]
a[p+1], a[p] = a[p], a[p+1]
p += 1
return p
if e is None:
e = len(a)
if e-b <= 1: return
p = part(a, b, e)
qsort(a, b, p)
qsort(a, p+1, e)

sin recursión:

deq = collections.deque()
deq.append((b, e))
while len(deq):
el = deq.pop()
if el[1] - el[0] > 1:
p = part(a, el[0], el[1])
deq.append((el[0], p))
deq.append((p+1, el[1]))

Answer 18

Partición : divida una matriz por un pivote para que los elementos más pequeños se muevan hacia la izquierda y los elementos más grandes se muevan hacia la derecha o viceversa. Un pivote puede ser un elemento aleatorio de una matriz. Para hacer este algoritmo, necesitamos saber qué es el índice inicial y final de una matriz y dónde se encuentra un pivote. Luego configure dos punteros auxiliares L, R.

Entonces, tenemos un usuario de matriz [..., begin, ..., end, ...]

La posición de inicio de los punteros L y R
[..., comenzar, siguiente, ..., fin, ...]
R L

mientras que L <fin
1. Si un usuario [pivote]> usuario [L], mueva R por uno e intercambie usuario [R] con usuario [L]
2. mueve L por uno

Después, al intercambiar usuario [R] con usuario [pivote]

Clasificación rápida : utilice el algoritmo de partición hasta que cada parte siguiente de la división por un pivote tenga un índice de inicio mayor o igual que el índice final.

def qsort(user, begin, end):
if begin >= end:
return
# partition
# pivot = begin
L = begin+1
R = begin
while L < end:
if user[begin] > user[L]:
R+=1
user[R], user[L] = user[L], user[R]
L+= 1
user[R], user[begin] = user[begin], user[R]
qsort(user, 0, R)
qsort(user, R+1, end)
tests = [
{''sample'':[1],''answer'':[1]},
{''sample'':[3,9],''answer'':[3,9]},
{''sample'':[1,8,1],''answer'':[1,1,8]},
{''sample'':[7,5,5,1],''answer'':[1,5,5,7]},
{''sample'':[4,10,5,9,3],''answer'':[3,4,5,9,10]},
{''sample'':[6,6,3,8,7,7],''answer'':[3,6,6,7,7,8]},
{''sample'':[3,6,7,2,4,5,4],''answer'':[2,3,4,4,5,6,7]},
{''sample'':[1,5,6,1,9,0,7,4],''answer'':[0,1,1,4,5,6,7,9]},
{''sample'':[0,9,5,2,2,5,8,3,8],''answer'':[0,2,2,3,5,5,8,8,9]},
{''sample'':[2,5,3,3,2,0,9,0,0,7],''answer'':[0,0,0,2,2,3,3,5,7,9]}
]
for test in tests:
sample = test[''sample''][:]
answer = test[''answer'']
qsort(sample,0,len(sample))
print(sample == answer)

Answer 19

Para la Versión Python 3.x : un estilo funcional que usa un módulo de operator , principalmente para mejorar la legibilidad.

from operator import ge as greater, lt as lesser
def qsort(L):
if len(L) <= 1: return L
pivot = L[0]
sublist = lambda op: [*filter(lambda num: op(num, pivot), L[1:])]
return qsort(sublist(lesser))+ [pivot] + qsort(sublist(greater))

y se prueba como

print (qsort([3,1,4,2,5]) == [1,2,3,4,5])

Answer 20

I will do quicksort using numpy library. I think it is really usefull library. They already implemented the quick sort method but you can implment also your custom method.

import numpy
array = [3,4,8,1,2,13,28,11,99,76] #The array what we want to sort
indexes = numpy.argsort( array , None, ''quicksort'', None)
index_list = list(indexes)
temp_array = []
for index in index_list:
temp_array.append( array[index])
array = temp_array
print array #it will show sorted array

Answer 21

Instead of taking three different arrays for less equal greater and then concatenating all try the traditional concept(partitioning method):

http://pythonplanet.blogspot.in/2015/08/quick-sort-using-traditional-partition.html

this is without using any inbuilt function.

partitioning function -

def partitn(alist, left, right):
i=left
j=right
mid=(left+right)/2
pivot=alist[mid]
while i <= j:
while alist[i] < pivot:
i=i+1
while alist[j] > pivot:
j=j-1
if i <= j:
temp = alist[i]
alist[i] = alist[j]
alist[j] = temp
i = i + 1
j = j - 1

Answer 22

def Partition(A,p,q):
i=p
x=A[i]
for j in range(p+1,q+1):
if A[j]<=x:
i=i+1
tmp=A[j]
A[j]=A[i]
A[i]=tmp
l=A[p]
A[p]=A[i]
A[i]=l
return i
def quickSort(A,p,q):
if p<q:
r=Partition(A,p,q)
quickSort(A,p,r-1)
quickSort(A,r+1,q)
return A

Answer 23

def quick_sort(array):
return quick_sort([x for x in array[1:] if x < array[0]]) + [array[0]] /
+ quick_sort([x for x in array[1:] if x >= array[0]]) if array else []

Answer 24

def quick_sort(l):
if len(l) == 0:
return l
pivot = l[0]
pivots = [x for x in l if x == pivot]
smaller = quick_sort([x for x in l if x < pivot])
larger = quick_sort([x for x in l if x > pivot])
return smaller + pivots + larger

Answer 25

def quick_sort(list):
if len(list) ==0:
return []
return quick_sort(filter( lambda item: item < list[0],list)) + [v for v in list if v==list[0] ] + quick_sort( filter( lambda item: item > list[0], list))

Answer 26

def quick_sort(self, nums):
def helper(arr):
if len(arr) <= 1: return arr
#lwall is the index of the first element euqal to pivot
#rwall is the index of the first element greater than pivot
#so arr[lwall:rwall] is exactly the middle part equal to pivot after one round
lwall, rwall, pivot = 0, 0, 0
#choose rightmost as pivot
pivot = arr[-1]
for i, e in enumerate(arr):
if e < pivot:
#when element is less than pivot, shift the whole middle part to the right by 1
arr[i], arr[lwall] = arr[lwall], arr[i]
lwall += 1
arr[i], arr[rwall] = arr[rwall], arr[i]
rwall += 1
elif e == pivot:
#when element equals to pivot, middle part should increase by 1
arr[i], arr[rwall] = arr[rwall], arr[i]
rwall += 1
elif e > pivot: continue
return helper(arr[:lwall]) + arr[lwall:rwall] + helper(arr[rwall:])
return helper(nums)

Answer 27

def quicksort(items):
if not len(items) > 1:
return items
items, pivot = partition(items)
return quicksort(items[:pivot]) + [items[pivot]] + quicksort(items[pivot + 1:])
def partition(items):
i = 1
pivot = 0
for j in range(1, len(items)):
if items[j] <= items[pivot]:
items[i], items[j] = items[j], items[i]
i += 1
items[i - 1], items[pivot] = items[pivot], items[i - 1]
return items, i - 1

Answer 28

def sort(array=[12,4,5,6,7,3,1,15]):
less = []
equal = []
greater = []
if len(array) > 1:
pivot = array[0]
for x in array:
if x < pivot:
less.append(x)
if x == pivot:
equal.append(x)
if x > pivot:
greater.append(x)
# Don''t forget to return something!
return sort(less)+equal+sort(greater) # Just use the + operator to join lists
# Note that you want equal ^^^^^ not pivot
else: # You need to hande the part at the end of the recursion - when you only have one element in your array, just return the array.
return array