tri par shell

Le tri Shell consiste à trier (par insertion) des sous-listes de la liste principale. Les sous-listes sont crées en prenant un élément tous les K éléments. On fait décroitre K jusqu'a K=1, c'est à dire qu'on trie la liste entière.

L = {A,L,G,O,R,I,T,H,M,E}

1ère passe : K=3. On construit 3 sous-listes en prenant 1 élément sur 3. on trie CHAQUE liste et on fait les changements correspondant dans la liste principale

L1 = {A, O, T, E} -> {A, E, O, T} = 1 insertion
L2 = {L, R, H} -> {H, L, R} = 1 insertion
L3 = {G, I, M} -> {I, G, M} = 1 insertion

L = {A,H,I,E,L,G,O,R,M,T}

2eme passe : K=2. On construit 2 sous-listes en prenant 1 élément sur 2.

L1= {A, I, L, O, M} -> {A, I, L, M, O} = 1 insertion
L2= {H, E, G, R, T} -> {E, G, H, R, T} = 2 insertions

L = {A,E,I,G,L,H,M,R,O,T}

3eme passe : K=1. On trie toute la liste

L = {A,E,G,H,I,L,M,O,R,T} = 3 insertions

*FINI*