"""
This code sort a list using quick sort with similar elements.
"""
# L=input('Please insert list seperated with sapces: ')
# L=L.split()
# L=[int(L[i]) for i in range(len(L))]
# p=0
# r=len(L)-1]
import random as rand # my python version is different
def partition2(L,p,r):
    x=L[r]
    i1=p-1
    i2=p-1
    PP=False
    for j in range(p,r):
        if L[j]==x:
            i2+=1
            (L[j],L[i2])=(L[i2],L[j])
            PP=True
        elif L[j]<x:
            if PP:
                i1+=1
                i2+=1
                (L[j],L[i1])=(L[i1],L[j])
                (L[i2],L[j])=(L[j],L[i2])
            else:
                i1+=1
                i2+=1
                (L[j],L[i1])=(L[i1],L[j])
    i2+=1
    i1+=1
    (L[r],L[i2])=(L[i2],L[r])
    return (i1,i2)
def randPartition2(L,p,r):
    n=rand.randint(p,r) # my python version includes r while giving random numbers
                          # so no need for +1
    (L[n],L[r])=(L[r],L[n])
    return partition2(L,p,r)
# L=[5,6,5,5,1,3,5,2,1,7,9,5,15,100,5, 2,17,5,56]
# print(randPartition2(L,0,len(L)-1))
# print(L)
def randQuickSort2(L):
    def recrandQuickSort2(L,p,r):
        if p<r:
            (q1,q2)=randPartition2(L,p,r)
            recrandQuickSort2(L,p,q1-1)
            recrandQuickSort2(L,q2+1,r)
    recrandQuickSort2(L,0,len(L)-1)
    return L
# # print(L)
print(randQuickSort2([])) #A sorted: []
print(randQuickSort2([1])) #A2=[1]
print(randQuickSort2([0,1,2,0,1,2,0,1,2,1])) #[0, 0, 0, 1, 1, 1, 1, 2, 2, 2]
print(randQuickSort2([5,6,5,5,1,3,5,2,1,7,9,5,15,100,5, 2,17,5,56]))
                #[1, 1, 2, 2, 3, 5, 5, 5, 5, 5, 5, 5, 6, 7,9, 15, 17, 56, 100]