Some sorts

 

ulis, 29-11-2004. Juste pour le plaisir de tester un nouvel algorithme.

(nan, pas assez sage : pas d'image)


    Le tri de la bulle, le classique des classiques et le pire des pires.
    On compare la bulle du bas avec les bulles du dessus jusqu'à trouver une plus grosse.
    On échange alors les deux bulles et on continue à comparer.
    Arrivé en haut, on a la plus petite bulle.
    Au tour suivant, on recommence avec la bulle du bas mais on s'arrête un cran plus bas.
    On finit par avoir les grosses bulles en bas et les petites bulles en haut.

-

  proc bulle1 {l} \
  {
    set m [llength $l]
    while {$m > 0} \
    {
      set stop 1
      for {set i 0} {$i < $m} {incr i} \
      {
        set i1 [lindex $l $i]
        set i2 [lindex $l [expr {$i + 1}]]
        if {$i1 < $i2} \
        {
          set stop 0
          lset l $i $i2
          lset l [expr {$i + 1}] $i1
        }
      }
      if {$stop} { break } \
      else { incr m -1 }
    }
    return $l
  }

    Un tri tout droit sorti de mon imagination (mais il doit bien exister quelque part).
    C'est encore un tri à bulle, mais au lieu de partir du bas on part du haut.
    Au tour suivant on descend d'un cran.
    Un peu plus efficace.

-

  proc bulle2 {l} \
  {
    set m [llength $l]
    incr m -1
    for {set s $m} {$s >= 0} {incr s -1} \
    {
      for {set i $s} {$i <= $m} {incr i} \
      {
        set i1 [lindex $l $i]
        set i2 [lindex $l [expr {$i + 1}]]
        if {$i1 < $i2} \
        {
          lset l $i $i2
          lset l [expr {$i + 1}] $i1
        } \
        else { break }
      }
    }
    return $l
  }

    Le tri par insertion.
    On choisit le plus gros et on le met devant.
    Puis on choisit le plus gros qui reste et on le met juste après.
    ...

-

  proc insert {l} \
  {
    set m [llength $l]
    for {set n1 0} {$n1 < $m - 1} {incr n1} \
    {
      set p $n1
      set i [lindex $l $p]
      set i1 $i
      for {set n2 [expr {$p + 1}]} {$n2 < $m} {incr n2} \
      {
        set i2 [lindex $l $n2]
        if {$i2 > $i1} { set p $n2; set i1 $i2 }
      }
      lset l $p $i
      lset l $n1 $i1
    }
    return $l
  }

    Le tri fusion. Compliqué mais performant.
    On fusionne les items deux par deux.
    Puis on fusionne les listes deux par deux.
    Jusqu'à ce qu'il n'y en ait plus qu'une seule (et ce sera celle-là).

-

  proc fusion {l} \
  {
    proc _f {l1 l2} \
    {
      set m1 [llength $l1]
      set m2 [llength $l2]
      set n1 0
      set n2 0
      set l [list]
      while {$n1 + $n2 < $m1 + $m2} \
      {
        if {$n1 > $m1} \
        {
          set l [concat $l [lrange $l2 $n2 end]]
          set n2 $m2
        } \
        elseif {$n2 > $m2} \
        {
          set l [concat $l [lrange $l1 $n1 end]]
          set n1 $m1
        } \
        else \
        {
          set i1 [lindex $l1 $n1]
          set i2 [lindex $l2 $n2]
          if {$i1 < $i2} \
          {
            lappend l $i2
            incr n2
          } \
          else \
          {
            lappend l $i1
            incr n1
          }
        }
      }
      return $l
    }
    while {[set n [llength $l]] > 1} \
    {
      set _l [list]
      set r [list]
      if {$n % 2 == 1} \
      {
        set r [lindex $l end]
        set l [lrange $l 0 end-1]
      }
      foreach {l1 l2} $l \
      { lappend _l [_f $l1 $l2] }
      set l $_l
      if {$n % 2 == 1} { lappend l $r }
    }
    return [lindex $l 0]
  }

    QuickSort, le meilleur des meilleurs.
    Simple et efficace.
    On choisit un pivot. On met à gauche les inférieurs, à droite les supérieurs.
    Puis on rassemble le tout. On trie d'abord les inférieurs et les supérieurs.
    Au moyen de QuickSort.

-

  proc quick {l} \
  {
    if {[set m [llength $l]] > 1} \
    {
      set p [lindex $l 0]
      set inf [list]
      set sup [list]
      foreach i [lrange $l 1 end] \
      {
        if {$i < $p} { lappend inf $i } \
        else { lappend sup $i }
      }
      set l [concat [quick $sup] $p [quick $inf]]
    }
    return $l
  }

Performances comparées

    for {set i 0} {$i < 100} {incr i} \
    { lappend l [expr rand()] }
    puts [time { bulle1 $l } 100]
    puts [time { bulle2 $l } 100]
    puts [time { insert $l } 100]
    puts [time { fusion $l } 100]
    puts [time { quick $l } 100]
  ->
  7647 microseconds per iteration
  4942 microseconds per iteration
  3662 microseconds per iteration
  1816 microseconds per iteration
  901 microseconds per iteration

Voir aussi


Discussion

ulis Les procédures n'ont pas été beaucoup testées (listes vides, valeurs en double...).

--


Catégorie Exemple