Tri de Batcher : code erroné, "corrections" non satisfaisantes

Version imprimable

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:

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:

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

8O

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:

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:

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...:ccool:
Qu'elle soit bénie, elle et sa descendance jusqu'à la 20e génération :P

Cordialement,

@+

11/07/2011, 17h34
mont29

Tu aurais dû lire le texte autour du code, yoshik ;)

Citation:

The following is an implementation of odd-even mergesort algorithm in Python. The input is a list x of length a power of 2. The output is a list sorted in ascending order.

:mouarf:

Ta liste L fait 61 éléments, rajoute-z-en trois (à 0, par exemple), pour en avoir 64 (2^6), et ça marche très bien*!

PS*: Tes modifications “cassent” l’algo, qui ne retourne plus une liste correctement triée*!
11/07/2011, 18h08
yoshik

Salut,

Merci, Merci...
Arf c'est vrai, je n'ai pas pris garde au texte :aie: power of 2...
M... alors !
C'est pour ça que le step monte à 64 quelquefois.
Mes modifs cassent l'Algo ?
Pas vu non plus : va falloir que je change mes lunettes !!! :mouarf:

D'où ma question subsidiaire (sur laquelle je vais me pencher, aussi d'ailleurs) :

comment modifier le code pour qu'il fonctionne même pour des tailles différentes de 2^k ?
Quelqu'un a une idée ?

Ça ne doit pas être simple : je vais devoir tout "démonter" pour pénétrer dans les arcanes de l'algo...

Merci encore, oeil-de-lynx !!!

@+

Ben, je te conseille pas de modifier l’algo en lui-même, même si c’est possible (j’ai pas (envie d’) essayé(er)), ça va t’alourdir un max le code*!

Rajoute plutôt le nombre nécessaire d’éléments “spéciaux” à la liste, et vire-les à la fin. Dans cet exemple, j’ai choisi None, qui est toujours comparé comme inférieur à tout nombre, ça donne (pas besoin de modifier autre chose que la première fonction)*:
Code:

1 2 3 4 5 6 7 8 def oddeven_merge_sort(n,x): p = int(math.log(n, 2))+1 pad = 2**p - n x += [None]*pad print n, p, pad oddeven_merge_sort_range(x, 0, n - 1 + pad) x = x[pad:n + pad] return x

11/07/2011, 19h44
yoshik

Ave !

Bin, c'est la même idée que je venais d'avoir, sauf que j'ignorais le coup du None...

Merci encore.

@+

[EDIT]
Je propose p = int(math.ceil(math.log(n, 2))) au lieu de p = int(math.log(n, 2))+1...
En effet p = int(math.log(n, 2))+1 avec n=64 donne 7 alors qu'on devrait garder 6...
12/07/2011, 01h46
mont29

Citation:

Envoyé par yoshik

Je propose p = int(math.ceil(math.log(n, 2))) au lieu de p = int(math.log(n, 2))+1...
En effet p = int(math.log(n, 2))+1 avec n=64 donne 7 alors qu'on devrait garder 6...

Ah bah oui, tiens, j’avais pas vu cette subtilité*! :oops: :mrgreen: