03) Quicksort

Quicksort ist ein schöner Sortieralgorithmus und ein gutes Beispiel für das Skripten mit JM°.

 

Mit guter Lesbarkeit sieht der Algorithmus wie folgt aus:

:qsort(List l) List
	If(l.len <= 1)
		_FUNC.return( l )
	p = l.first
	r = l.from(2)
a = _THIS.qsort( r.filter( _EACH <= p ) )
b = _THIS.qsort( r.filter( _EACH > p ) )
§ = a.add(p).concat(b)

 

Es ist aber auch möglich dies kürzer zu schreiben:

:qsort(l)
	( l.len <= 1 )
		§ = l
	p = l[1]
	r = l.from(2)
	§ = °qsort( r.filter( $$ <= p ) ).add(p).concat( °qsort( r.filter( $$ > p ) ) )

 

Die kürzeste Version könnte wie folgt aussehen:

:qsort(l)
	(l.len<=1).if.go(§=l)
	§=°qsort(l.from(2).filter($$<=l[1])).add(l[1]).concat(°qsort(l.from(2).filter($$>l[1])))

 

Zum Testen der Funktion kannst Du sie mit einer Beispiel-Liste aufrufen:

tl = [16, 23, 14, 7, 21, 20, 6, 1, 17, 13, 12, 9, 3, 19]
°qsort(tl.print).print