print("SameAverage:") print(same_average([6,25,29,10,6,5,8,0,20,19]))

import operator
import random

def isSorted(op,ls):
    for i in range(len(ls)-1):
        res= op(ls[i],ls[i+1])
        if not res:
            break
    return res

def insertsort(seq):
    x=1
    while x < len(seq):
        key= seq[x]
        k=x-1
        while k>=0 and seq[k]>key:
            seq[k+1]= seq[k]
            k= k-1
        seq[k+1]=key
        x += 1
    return seq    
    
def test_a3():
    for i in range(10):
        xs = insertsort(random.sample(range(100),10))
        print(xs,isSorted(operator.le,xs))


def min_diff(xs):
    xs.sort()
    tp= (xs[1],xs[0],(xs[1]-xs[0]))
    for i in range(1,len(xs)-1):
        if xs[i+1]-xs[i] < tp[2]:
            tp= (xs[i],xs[i+1],(xs[i+1]-xs[i]))
    return tp[:-1]
        
        
def same_average(xs):
    av= sum(xs)//len(xs)
    xs.sort()
    res=[]
    for i in range(len(xs)):
        for j in range(i,len(xs)):
            if (xs[i]+xs[j])//2==av:
                res.append((xs[i],xs[j]))
            elif (xs[i]+xs[j])//2>av:
                break
    return res

    
def quicksort(A):
    X=[]
    res=[]
    c=0
    for i in A:
        X.append((i,c))
        c+=1
    li= quick(X,0,((len(X))-1))
    for i in li:
        res.append(i[0])
    return res
    
def quick(X,low,high):
    if low<high:
        m=partition1(X,low,high)
        quick(X,low,m-1)
        quick(X,m+1,high)
    return X
        
def partition1(X,low,high):
    pval=(X[low])[0]
    pindx=(X[low])[1]
    i=low
    for j in range(low+1,high+1):
            if (((X[j])[0])<pval):
                i=i+1
                X[i],X[j]=X[j],X[i]
            elif (((X[j])[0])==pval) and (((X[j])[1])<pindx):
                i=i+1
                X[i],X[j]=X[j],X[i]
    X[i],X[low]=X[low],X[i]
    return i



print("A3:")
test_a3()
print("min_diff:")
print(min_diff([3,10,3,9,5,1,2,7,6,8]))
print("SameAverage:")
print(same_average([6,25,29,10,6,5,8,0,20,19]))
print("quicksort:")
print(quicksort([6,25,29,10,6,5,8,0,20,19]))