Bonjour à tous,

Je me penche en ce moment sur les différentes méthodes de tri (tout comme guigui en son temps).
J'ai trouvé sur le wiki, un tri très performant, le tri de Batcher :
http://en.wikipedia.org/wiki/Batcher_odd-even_mergesort
J'ai donc décidé de le tester ainsi :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#!/usr/bin/env python
# -*- coding: cp1252 -*-
 
from __future__ import division
 
def oddeven_merge_sort(n,x):
    oddeven_merge_sort_range(x, 0, n-1)
    return L
 
def oddeven_merge_sort_range(x, lo, hi):
    """ sort the part of x with indices between lo and hi.
     Note: endpoints (lo and hi) are included.
    """
    if (hi - lo) >= 1:
    # if there is more than one element, split the input
    # down the middle and first sort the first and second
    # half, followed by merging them.
        mid = lo + ((hi - lo) // 2)
        oddeven_merge_sort_range(x, lo, mid)
        oddeven_merge_sort_range(x, mid + 1, hi)
        oddeven_merge(x, lo, hi, 1)
 
def oddeven_merge(x, lo, hi, r):
    step = r * 2
    if step < hi - lo:
        oddeven_merge(x, lo, hi, step)
        oddeven_merge(x, lo + r, hi, step)
        for i in range(lo + r, hi - r, step):
            compare_and_swap(x, i, i + r)
    else:
        compare_and_swap(x, lo, lo + r)
 
def compare_and_swap(x, a, b):
    if x[a] > x[b]:
        x[a], x[b] = x[b], x[a]
 
L=[103,51,31,1,44,42,39,48,52,26,38,53,4,57,3,45,20,27,25,30,15,37,12,46,\
13,47,6,54,17,18,2,24,23,22,21,19,29,56,10,5,7,58,59,33,1037,34,28,14,235,\
11,43,16, 55,32,9,8,60,36,35,41,49]
n=len(L)
L=oddeven_merge_sort(n,L)
print L

Et hop :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Traceback (most recent call last):
  File "C:/Python26/tri.py", line 41, in <module>
    L=oddeven_merge_sort(n,L)
  File "C:/Python26/tri.py", line 7, in oddeven_merge_sort
    oddeven_merge_sort_range(x, 0, n-1)
  File "C:/Python26/tri.py", line 20, in oddeven_merge_sort_range
    oddeven_merge_sort_range(x, mid + 1, hi)
  File "C:/Python26/tri.py", line 20, in oddeven_merge_sort_range
    oddeven_merge_sort_range(x, mid + 1, hi)
  File "C:/Python26/tri.py", line 20, in oddeven_merge_sort_range
    oddeven_merge_sort_range(x, mid + 1, hi)
  File "C:/Python26/tri.py", line 21, in oddeven_merge_sort_range
    oddeven_merge(x, lo, hi, 1)
  File "C:/Python26/tri.py", line 27, in oddeven_merge
    oddeven_merge(x, lo + r, hi, step)
  File "C:/Python26/tri.py", line 27, in oddeven_merge
    oddeven_merge(x, lo + r, hi, step)
  File "C:/Python26/tri.py", line 31, in oddeven_merge
    compare_and_swap(x, lo, lo + r)
  File "C:/Python26/tri.py", line 34, in compare_and_swap
    if x[a] > x[b]:
IndexError: list index out of range


Donc, j'ai réfléchi et j'ai trouvé 2 biais pour contourner (et pas résoudre) le problème.
1. Soit je modifie la procédure Swap_and_exchange ainsi :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
def compare_and_swap(x, a, b):
    if x[a] > x[b]:
        try:
            x[a], x[b] = x[b], x[a]
        except:
            pass
2. Soit c'est la procédure oddeven_merge(x, lo, hi, r) que je modifie ainsi :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
def oddeven_merge(x, lo, hi, r):
    step = r * 2
    if step < hi - lo:
        oddeven_merge(x, lo, hi, step)
        oddeven_merge(x, lo + r, hi, step)
        for i in range(lo + r, hi - r, step):
            if hi-r<n:
                compare_and_swap(x, i, i + r)
    else:
        if lo+r<n:
            compare_and_swap(x, lo, lo + r)
Dans les 2 cas ça fonctionne...
Mais, je ne suis pas satisfait parce que je voudrais corriger le code pour que les calculs ne génèrent pas de "list index out of range" : là je ne fais que contourner le problème.
J'ai constaté que le step était parfois trop grand (ici >61), alors qu'il ne devrait pas dépasser 32, c'est l'écart maximum 2**(k-1) tel que 2**k >=n, n étant la taille de la liste.
J'ai essayé d'agir là-dessus sans succès...

Quelqu'un va bien avoir une idée de la cause exacte, de mon côté je continue à chercher...
Merci d'avance à la bonne âme qui m'apportera la lumière...
Qu'elle soit bénie, elle et sa descendance jusqu'à la 20e génération

Cordialement,

@+