## TP10 -- Algorithmes de tri



## Exercise 10.2 -- Nombres au hasard

## question 1) b)

import random as rd

# La fonction qui suit marche quelles que soient
# les positions relatives de a et b
def nombreAleatoireEntre(a, b):
	ratio = rd.random()
	x = a + ratio*(b-a)
	return x

## question 2) b)

def listeAuHasard(a, b, N):
    resultat = []
    for _ in range(N):
        x = nombreAleatoireEntre(a, b)
        resultat.append(x)
    return resultat



## Exercise 10.3 -- Tri par sélection

## question 1) b)

def iMin(L, i):
   	n = len(L)
    record = L[i]
    indiceRecord = i
    for j in range(i+1, n):
        x = L[j]
        if x < record:
            record = x
            indiceRecord = j
    return indiceRecord

## question 3) a)

def trieParSelection(L):
    n = len(L)
    for i in range(n):
        iMinimal = iMin(L, i)
        L[i], L[iMinimal] = L[iMinimal], L[i]

## question 3) b)

# Il faut d'abord exécuter dans la console :
N = 10**2
L1 = listeAuHasard(-1000, 1000, N)
trieParSelection(L1)
L1

# Puis :
N = 10**4
L1 = listeAuHasard(-1000, 1000, N)
trieParSelection(L1)
L1



## Exercise 10.5 -- Tri par insertion, version récursive \glm {naïve}

## question 1) b)

def insereDansListeTriee(Lt, x):
	Lt.append(x)
	n = len(Lt)
	j = n-1
	while j-1 >= 0:
		if L[j] < L[j-1]:
			 L[j], L[j-1] = L[j-1], L[j]
			 j = j-1
		else:
			return

## question 2) b)

def copieTrieeInsertionRec(L):
	if L == []:
		return []
	newL = L[:-1]
	Lt = copieTrieeInsertionRec(Lt)
	x = L[-1]
	insereDansListeTriee(Lt, x)
	return Lt



## Exercise 10.6 -- Tri par insertion, version récursive sans copie

## question 1) b)

def triInsertionRec_aux(L, k):
	if k == 0:
		return:
	else:
		triInsertionRec_aux(L, k-1)
		i = k
		while i > 0:
			if L[i] >= L[i-1]:
				return
			else:
				L[i], L[i-1] = L[i-1], L[i]
				i = i-1

## question 2) b)

def triInsertionRec(L):
	n = len(L)
	triInsertionRec_aux(L, n)



## Exercise 10.7 -- Tri par insertion, version itérative sans copie

## question 2) b)

def triInsertionIter(L):
	n = len(L)
	for k in range(n):
		for i in range(k):
			if L[k-i] < L[k-i-1]:
				L[k-i], L[k-i-1] = L[k-i-1], L[k-i]



## Exercise 10.8 -- Chronométrage des algorithmes prédédents

## question 1) b)

# Le temps de calcul d'une fonction dont la complexité est quadratique
# est multiplié par 4 quand la taille des données est doublée.

## question 3) b)

import random as rd
def nombreAleatoireEntre(a, b):
	return a + rd.random()*(b-a)
	
def listeAuHasard(a, b, N):
	return [nombreAleatoireEntre(a, b) for n in range(N)]

import time
def testChrono(f, n):
	debut1 = time.time()
	liste1 = listeAuHasard(0, 1, n)
	f(liste1)
	fin1 = time.time()
	t1 = fin1 - debut1
	
	debut2 = time.time()
	liste2 = listeAuHasard(0, 1, 2*n)
	f(liste2)
	fin2 = time.time()
	t2 = fin2 - debut2
	
	return (t1, t2)



## Exercise 10.9 -- Tri fusion (\emph {merge sort} en anglais)

## question 1) b)

def scission(L):
    n = len(L)
    L1 = []
    L2 = []
    for i in range(n):
        x = L[i]
        if i%2 == 0:
            L1.append(x)
        else:
            L2.append(x)
    return (L1, L2)
	
# Voici une autre solution utilisant le slicing :
def scission(L):
	n = len(L)
    indiceMilieu = n//2
    L1 = L[:indiceMilieu]
    L2 = L[indiceMilieu:]
	return (L1, L2)

## question 2) b)

def fusion(Lt1, Lt2):
    n1 = len(Lt1)
    n2 = len(Lt2)
    i1, i2 = 0, 0
    L = []
    while i1 < n1 or i2 < n2:
        if i1 >= n1:
            L.append(Lt2[i2])
            i2 = i2+1
        elif i2 >= n2:
            L.append(Lt1[i1])
            i1 = i1+1
        else:
            x1 = Lt1[i1]
            x2 = Lt2[i2]
            if x1 <= x2:
            	L.append(x1)
             	i1 = i1+1
            else:
             	L.append(x2)
             	i2 = i2+1
    return L

## question 3) b)

def triFusion(L):
	if len(L) <= 1:
		return L[:]
	else:
		L1, L2 = scission(L)
		Lt1 = triFusion(L1)
		Lt2 = triFusion(L2)
		return fusion(Lt1, Lt2)



## Exercise 10.10 -- Tri rapide (\emph {quicksort} en anglais)

## question 1) b)

def triRapide(L):
	n = len(L)
	if n <= 1:
		return L[:]
	pivot = L[n//2]
	L_gauche, L_milieu, L_droite = [], [], []
	for x in L:
		if x < pivot:
			L_gauche.append(x)
		elif x > pivot:
			L_droite.append(x)
		else:
			L_milieu.append(x)
	return triRapide(L_gauche) + L_milieu + triRapide(L_droite)



## Exercise 10.11 -- Tri rapide en place

## question 1) b)

import random as rd
def scissionEnPlace(L, iMin, iMax):
	iPivot = rd.randrange(iMin, iMax)
	pivot = L[iPivot]
	i = iMin
	j = iMax-1
	while i <= j:
		if L[i] <= pivot:
			i = i+1
		else:
			L[i], L[j] = L[j], L[i]
			j = j-1
	return i-1

## question 2) b)

def effectueTriRapide_aux(L, iMin, iMax):
	if iMin >= iMax-1:
		return
	else:
		iMilieu = scissionEnPlace(L, iMin, iMax)
		effectueTriRapide_aux(L, iMin, iMilieu)
		effectueTriRapide_aux(L, iMilieu, iMax)
		
def effectueTriRapide(L):
	n = len(L)
	effectueTriRapide_aux(L, 0, n)



## Exercise 10.12 -- Tri par comptage

## question 1) b)

def comptage(L, M):
	n = len(L)
	resultat = [0]*M
	for x in L:
		resultat[x] = resultat[x] + 1
	return resultat

## question 2) b)

def triComptage(L, M):
	comptageDesElements = comptage(L, M)
	Ltriee = []
	for i in range(M):
		Ltriee = Ltriee + [i]*comptageDesElements[i]
	return Ltriee



## Exercise 10.13 -- Le tri à bulles (\emph {bubble sort})

## question 4) b)

def effectueTriABulles(L):
	n = len(L)
	iMax = n
	while iMax >= 0:
		for i in range(iMax-1):
			if L[i] > L[i+1]:
				L[i], L[i+1] = L[i+1], L[i]
		iMax = iMax-1



## Exercise 10.14 -- Un tri absolument stupide

## question 1) b)

def estTriee(L):
	n = len(L)
	for i in range(n-1):
		if L[i] > L[i+1]:
			return False
	return True

## question 3) b)

def triStupide(L):
	N = 0
	while not estTriee(L):
		rd.shuffle(L)
	return N