# TP 7 3.7.1 Tri

# insertion #################################################################

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))


# selection #################################################################

def argmin(l, start=0):
	min = float('inf')
	for i in range(start, len(l)):
		v = l[i]
		if v < min:
			i_min = i
			min = v
	return i_min

def sort_select(l):
	l = l[:]
	result = []
	while l != []:
		result.append(l.pop(argmin(l)))
	return result

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

def sort_select_inplace(l):
	for i in range(len(l)):
		i_min = argmin(l, i)
		l[i_min], l[i] = l[i], l[i_min]

sort_select_inplace(l)
print(l)