# -*- coding: utf-8 -*-
"""
Created on Tue Dec  8 22:31:20 2015

@author: dconduche
"""

import numpy as np


def tri_insertion(L):
    for i in range(1, len(L)):
        j = i
        v = L[i]
        while (j > 0) and (L[j-1] > v):
            L[j] = L[j-1]
            j = j-1
        L[j] = v


def quicksort(L):
    if len(L) <= 1:
        return L
    else:
        pivot = L[0]
        plus_grand = []
        plus_petit = []
        for x in L[1:]:
            if x >= pivot:
                plus_grand.append(x)
            else:
                plus_petit.append(x)
        return quicksort(plus_petit) + [pivot] + quicksort(plus_grand)


def quicksort_al(L):
    """Quicksort avec pivot aléatoire"""
    if len(L) <= 1:
        return L
    else:
        k = np.random.randint(len(L))
        pivot = L.pop(k)
        plus_grand = []
        plus_petit = []
        for x in L[1:]:
            if x >= pivot:
                plus_grand.append(x)
            else:
                plus_petit.append(x)
        return quicksort_al(plus_petit) + [pivot] + quicksort_al(plus_grand)


def fusion(L1, L2):
    """fusionne deux listes triées"""
    if L1 == []:
        return L2
    if L2 == []:
        return L1
    #Désormais, les deux listes sont non vides.
    if L1[0] < L2[0]:
        return [L1[0]] + fusion(L1[1:], L2)
    else:
        return [L2[0]] + fusion(L1, L2[1:])


def tri_fusion(L):
    if len(L) <= 1:
        return L
    m = len(L)//2
    return fusion(tri_fusion(L[:m]), tri_fusion(L[m:]))