#! /usr/bin/env python3

# TD7 p.86
# 2.8 tris

# 2.8.1 dichotomie ##########################################################

# tri par insertion, version naive

def place(l, v):
	"""find the place in a sorted list"""
	if l == []:
		return 0
	for i in range(len(l)):
		if l[i] > v:
			return i
	return len(l)
	
def sort_insert(l):
	result = []
	for v in l:
		i = place(result, v)
		result.insert(i, v)
	return result


l = [4, 3, 7, 2, 7, 1, 0, 0]
print(l)
print(sort_insert(l))



# tri par insertion, version dichotomique

def place(l, v):
	"""find the place in a sorted list"""
	b, e = 0, len(l) # plage dans laquelle on cherche, e exclue
	while b != e:
		print(v, b, e)
		c = (b+e) // 2
		if l[c] < v:
			b = c+1
		else:
			e = c
	return b

l = [4, 3, 7, 2, 7, 1, 0, 0]
print(l)
print(sort_insert(l))