#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon Nov 24 10:43:11 2025

@author: pjoulaud
"""
import timeit
import matplotlib.pyplot as plt
from listes_a_trier import liste10, liste50, liste100, liste500, liste1000

def tri_insertion(liste):
    j = 1
    while j<len(liste):
        i = j-1
        k = liste[j]
        while i>=0 and liste[i]>k:
            liste[i+1] = liste[i]
            # print(f"j: {j} - i : {i} - k : {k} - liste : {liste}")
            i = i-1
        liste[i+1] = k
        j = j+1
    return liste

def tri_selection(liste):
    i = 0
    while i<len(liste):
        j = i+1
        min = i
        while j<len(liste):
            if liste[j]<liste[min]:
                min = j
            # print(f"i : {i} - j : {j} - liste : {liste}")
            j = j+1
        if min != i :
            liste[i], liste[min] = liste[min], liste[i]
        i = i+1
    return liste

def tri_a_bulle(liste):
    for j in range(len(liste)-1):
        for i in range(len(liste)-1):
            if liste[i] > liste[i+1]:
                liste[i], liste[i+1] = liste[i+1], liste[i]
            # print(f"i : {i} - j : {j} - liste : {liste}")
    return liste

def fusion(l1:list, l2:list)->list:
    l3 = []
    while len(l1)>0 and len(l2)>0:
        if l1[0]<l2[0]:
            x = l1.pop(0)
            l3.append(x)
        else :
            x = l2.pop(0)
            l3.append(x)
    if len(l1)>0:
        l3 = l3 + l1
    if len(l2)>0:
        l3 = l3 + l2
    return l3

def tri_fusion(l:list)->list:
    if len(l)==1:
        return l
    else :
        i_milieu = len(l)//2
        l1 = l[:i_milieu]
        l2 = l[i_milieu:]
        l1bis = tri_fusion(l1)
        l2bis = tri_fusion(l2)
        return fusion(l1bis, l2bis)

def tri_fusion2(l:list)->list:
    if len(l)==1:
        return l
    else :
        return fusion(tri_fusion2(l[:len(l)//2]), tri_fusion2(l[len(l)//2:]))

l = [27, 10, 12, 8, 11]
print("tri insertion : ", tri_insertion((l)))
l = [27, 10, 12, 8, 11]
print("tri selection : ", tri_selection((l)))
l = [27, 10, 12, 8, 11]
print("tri à bulle : ", tri_a_bulle((l)))

# x = [10,50,100,1000]
x = []
y1, y2, y3, y4 = [], [], [], []
# for elem in [liste10, liste50, liste100, liste1000]:
for i in range(1,10):
    x.append(i*1000)
    print(i)
    l = i*liste1000
    y1.append(timeit.timeit(f"tri_insertion({l})", number = 1, globals=globals()))
    y2.append(timeit.timeit(f"tri_selection({l})", number = 1, globals=globals()))
    y3.append(timeit.timeit(f"tri_a_bulle({l})", number = 1, globals=globals()))
    y4.append(timeit.timeit(f"tri_fusion2({l})", number = 1, globals=globals()))

fig = plt.figure()
ax = fig.add_subplot(2, 1, 1)
line1 = ax.plot(x, y1, color='blue', label='insertion')
line2 = ax.plot(x, y2, color='red', label='selection')
line3 = ax.plot(x, y3, color='green', label='a_bulle')
line4 = ax.plot(x, y4, color='pink', label='fusion')
plt.legend(loc='upper right')
fig.show()