quicksort in python

1def partition(array, begin, end):
2    pivot_idx = begin
3    for i in xrange(begin+1, end+1):
4        if array[i] <= array[begin]:
5            pivot_idx += 1
6            array[i], array[pivot_idx] = array[pivot_idx], array[i]
7    array[pivot_idx], array[begin] = array[begin], array[pivot_idx]
8    return pivot_idx
9
10def quick_sort_recursion(array, begin, end):
11    if begin >= end:
12        return
13    pivot_idx = partition(array, begin, end)
14    quick_sort_recursion(array, begin, pivot_idx-1)
15    quick_sort_recursion(array, pivot_idx+1, end)
16
17def quick_sort(array, begin=0, end=None):
18    if end is None:
19        end = len(array) - 1
20    
21    return quick_sort_recursion(array, begin, end)

1#this function is for getting correct position of pivot
2def pivot_place(list1,first,last):
3    pivot = list1[first]
4    left = first + 1
5    right = last
6
7    while True :
8
9        while left <= right and  list1[left] <= pivot :
10            left += 1
11        while left<=right and list1[right] >= pivot:
12            right -= 1
13
14        if right < left :
15            break
16        else:
17            list1[left],list1[right] = list1[right],list1[left]
18    list1[first],list1[right] = list1[right],list1[first]
19
20    return right
21def quicksort(list1,first,last):
22    if first < last :
23        p = pivot_place(list1,first,last)
24        quicksort(list1,first,p-1)
25        quicksort(list1,p+1,last)
26n = int(input("How many elements you want : "))
27list1 = [int(input("Enter elements : ")) for x in range(n)]
28quicksort(list1,0,n - 1)
29print(list1)
30

1def partition(arr, low, high):
2    i = (low-1)         
3    pivot = arr[high]   
4 
5	for j in range(low, high):
6        if arr[j] <= pivot:
7 
8            i = i+1
9            arr[i], arr[j] = arr[j], arr[i]
10 
11    arr[i+1], arr[high] = arr[high], arr[i+1]
12    return (i+1)
13 
14def quickSort(arr, low, high):
15    if len(arr) == 1:
16        return arr
17    if low < high:
18        pi = partition(arr, low, high)
19 
20		quickSort(arr, low, pi-1)
21        quickSort(arr, pi+1, high)
22 
23arr = [10, 7, 8, 9, 1, 5]
24n = len(arr)
25quickSort(arr, 0, n-1)
26print("Sorted array is:")
27for i in range(n):
28    print("%d" % arr[i]),

1array = [29,99,27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44]
2
3quick_sort(array, 0, len(array) - 1)
4print(array)
5

1def quicksort(arr):
2    if len(arr) <= 1:
3        return arr
4    pivot = arr[len(arr) // 2]
5    left = [x for x in arr if x < pivot]
6    middle = [x for x in arr if x == pivot]
7    right = [x for x in arr if x > pivot]
8    return quicksort(left) + middle + quicksort(right)
9
10print(quicksort([3,6,8,10,1,2,1]))
11# Prints "[1, 1, 2, 3, 6, 8, 10]"
12

1[12, 19, 21, 27, 28, 29, 31, 41, 44, 44, 58, 66, 76, 78, 83, 87, 88, 97, 99]
2