lambdaway :: quicksort5

5 | list | login |load

| |

_img http://lambdaway.free.fr/lambdawalks/data/diviser_regner.jpg

_h1 [[quicksort3]] | [[quicksort4]] | quicksort5

_p Divide & conquer.

_h2 python

_p Code fourni par un concurrent libre de Chat-GPT dont j'ai oublié le nom.

{pre
def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot_index = len(arr) // 2
    smaller_part = [x for x in arr[0:pivot_index] if x < pivot_index]
    bigger_part  = [x for x in arr[pivot_index:]  if x > pivot_index]
    return quicksort(smaller_part) + 
           [pivot_index] + 
           quicksort(bigger_part)
}

_p Il se trouve que je ne comprend pas le mode de fonctionnement de :
_ul {code [x for x in arr[0:pivot_index] if x < pivot_index]}
_ul de la concaténation {code quicksort(smaller_part) + [pivot_index] + quicksort(bigger_part)}

_p Je ne sais donc pas le traduire en lambdatalk.

_h2 scheme

_p J'ai trouvé sur Stackoverflow un code que je comprend mieux :

{prewrap
(defun qsort (L)
   (cond
   ((null L) nil)
   (t (append
      (qsort (list< (car L) (cdr L)))
      (cons (car L) nil)
      (qsort (list>= (car L) (cdr L)))))))

(defun list< (a b)
    (cond
    (( or (null a) (null b)) nil)
    (( < a (car b)) (list< a (cdr b)))
    (t (cons (car b) (list< a (cdr b))))))

(defun list>= (a b)
    (cond
    (( or ( null a)(null b)) nil)
    (( >= a (car b)) (list>= a (cdr b)))
    (t (cons (car b) (list>= a (cdr b))))))   
}

_p ... et que je peux traduire en lambdatalk.

_h2 lambdatalk
{require lib_list}

_p Le noyau de lambdatalk comprend les primitives de tableau mais ne comprend pas celles de liste, que j'ai choisi d'externaliser dans une librairie, [[lib_list]]

{prewrap
{L.lib}
}

_p Noter que la fonction {code L.concat} concatène deux listes et non un nombre quelconque comme la primitive {code append} de Scheme. Voici le code lambdatalk traduit du code Scheme.

{pre
'{def qsort

{def qsort.sub          // combine list< & list> en une seule fonction
  {lambda {:op :a :b}
   {if {or {L.nil? :a} {L.nil? :b}}
    then nil
    else {if {:op :a {L.first :b}}
          then {qsort.sub :op :a {L.rest :b}}
          else {L.cons {L.first :b}
                       {qsort.sub :op :a {L.rest :b}}}}}}}

{lambda {:l}
  {if {L.nil? :l}
   then nil
   else {L.concat
            {qsort {qsort.sub <  {L.first :l} {L.rest :l}}}
        {L.concat 
            {L.cons {L.first :l} nil}
            {qsort {qsort.sub >= {L.first :l} {L.rest :l}}}}}}}}
-> {def qsort

{def qsort.sub
  {lambda {:op :a :b}
   {if {or {L.nil? :a} {L.nil? :b}}
   then nil
   else {if {:op :a {L.first :b}}
   then {qsort.sub :op :a {L.rest :b}}
   else {L.cons {L.first :b}
                {qsort.sub :op :a {L.rest :b}}}}}}}

{lambda {:l}
  {if {L.nil? :l}
   then nil
   else {L.concat
         {qsort {qsort.sub <  {L.first :l} {L.rest :l}}}
        {L.concat {L.cons {L.first :l} nil}
         {qsort {qsort.sub >= {L.first :l} {L.rest :l}}}}}}}}

'{L.disp {qsort {L.new 3 2 5 6 8 4 5 3 7 6 5 4}}}
-> {L.disp {qsort {L.new 3 2 5 6 8 4 5 3 7 6 5 4}}}
}

_p Test d'une liste de 400 nombres aléatoires de 0 à 1000.

{prewrap 
'{def L
 {L.new 
  {S.map {lambda {:i} {floor {* 1000 {random}}}}
         {S.serie 1 400}}}}  
-> {def L
 {L.new 
  {S.map {lambda {:i} {floor {* 1000 {random}}}}
         {S.serie 1 400}}}}

input: 
'{L.disp {L}}
-> {L.disp {L}}

output: 
'{L.disp {qsort {L}}} 
-> {L.disp {qsort {L}}}

}

_p {i alain marty 2023/04/24}

{style 
pre { box-shadow:0 0 8px #000; padding:5px; }
}