import random
import time
import numpy as np

def partition(A,p,r):
    x = A[r-1] #the pivot element
    i = p - 1
    for j in range(r-p+1):
        if A[j] <= x: #the elements should be less or equal to the pivot
            i = i + 1
            A[i],A[j] = A[j], A[i] #swap the pivots to the right positions of the left part
    A[j+1],A[r] = A[r], A[j+1]
    return i +1

  def quicksort(A,p,r):
    if p < r:
        q = A[r-1]
        partition(A,p,r)
        quicksort(A, p, q-1) #resursively quicksort the left or right part of previous pivots
        quicksort(A, q+1, r)

random.seed(123)
lst1 = [random.random() for a in range(100000)]
quicksort(lst1, 0, 99)