Oppolzer - Informatik / Blog

Für die Bereitstellung der Artikel dieses Blogs war es nötig, die Artikel
sowie die Links auf der Blog-Hauptseite nach Zeitangaben zu sortieren. Die
statischen HTML-Seiten werden mit einem REXX-Skript erstellt.

Es geht also darum, einen REXX-Stem zu sortieren, idealerweise mit dem
allseits bekannten Quicksort-Verfahren. Das Problem ist, dass Quicksort
rekursive Funktionsaufrufe benutzt.

Eine an die von der Wikipedia-Seite zu Quicksort abgeleitete Formulierung
für REXX sieht wie folgt aus:


/************************************************/
/*                                              */
/*   Sortieren der art-Stems nach dem           */
/*   Datum bzw. Filenamen                       */
/*                                              */
/*   Quicksort in REXX                          */
/*                                              */
/************************************************/

sort:

   daten. = ""
   daten.0 = art.0

   do i = 1 to daten.0
      daten.i = artf.i" $ "i
   end

   /* call quicksort 1, daten.0 */

   call quicksort_nonrec

   do i = 1 to daten.0
      say daten.i
   end

   return



/***********************************************/
/*                                             */
/*   quicksort                                 */
/*                                             */
/***********************************************/

quicksort: procedure expose daten.

   parse arg links, rechts

   say "quicksort startet mit "links","rechts

   if links < rechts then do
      teiler = teile(links, rechts)
      call quicksort links, teiler - 1
      call quicksort teiler + 1, rechts
   end

   return


dazu folgende Bemerkungen:

a) der Quicksort-Aufruf in der Funktion sort ist auskommentiert, weil sich
   schnell herausgestellt hat, dass das so nicht funktioniert (die Anzahl
   der rekursiven Aufrufebenen war bei meiner REXX-Implementierung - OS/2 V3.0 -
   auf ca. 45 Ebenen begrenzt ... das reicht bei weitem nicht aus)

b) die Funktion sort zeigt auf, wie eine ganze Reihe von Stems wie z.B. der
   Stem artf sortiert werden kann; sie werden einfach gar nicht sortiert,
   sondern es wird einfach eine Key-Tabelle aufgebaut (hier: Daten), und in
   dieser steht der Schlüsselbegriff für die Sortierung (hier: artf) und
   der ursprüngliche Index. Diese beiden werden sortiert, so dass man nachher
   den Zugriff auf die Tabellen anhand des ursprünglichen Index vornehmen kann
   (indirekter Zugriff über den umsortierten Index)

c) die eigentliche Arbeit der Vertauschung usw. geschieht in der Funktion
   teile; sie kommt ebenfalls mehr oder weniger direkt von Wikipedia; hier
   die REXX-Formulierung:


/***********************************************/
/*                                             */
/*   teilen des Vektors fuer quicksort         */
/*                                             */
/***********************************************/

teile: procedure expose daten.

   parse arg li, re

   piv = daten.re

   /***************************************/
   /* starte mit j links vom pivotelement */
   /***************************************/

   i = li
   j = re - 1;

   do while i < j

      /*********************************************/
      /*   suche von links ein element,            */
      /*   welches groesser als das pivot          */
      /*   wiederhole solange daten[i] <= pivot    */
      /*   und i < rechts                          */
      /*********************************************/

      do while daten.i >= piv & i < re
         i = i + 1
      end

      /*********************************************/
      /*   suche von rechts ein element,           */
      /*   welches kleiner als das pivot           */
      /*   wiederhole solange daten[j] >= pivot    */
      /*   und j > links                           */
      /*********************************************/

      do while daten.j <= piv & j > li
         j = j - 1
      end;

      /*********************************************/
      /*   falls i < j dann                        */
      /*   tausche daten[i] mit daten[j]           */
      /*********************************************/

      if i < j then do

         daten_save = daten.i
         daten.i = daten.j
         daten.j = daten_save

      end

   end

   if daten.i < piv then do

      /*********************************************/
      /*   tausche daten[i] mit daten[rechts]      */
      /*********************************************/

      daten_save = daten.i
      daten.i = daten.re
      daten.re = daten_save

   end

   return i


Jetzt zum Problem mit den rekursiven Aufrufen. Die Lösung ist hier,
dass man die Rekursion durch Iteration ersetzt. Ich habe einen weiteren
Stem call_stack eingeführt, der im wesentlichen die Parameter für die
rekursiven Aufrufe enthält. Die in der Folge eines Aufrufs von quicksort
als nächstes durchzuführenden "rekursiven" Aufrufe auf den unteren Ebenen
werden in den call_stack eingetragen (quasi für später beauftragt). Die
Variable stack_pos steuert, wo man sich innerhalb des call_stacks gerade
befindet.

Die nicht-rekursive Variante von Quicksort sieht damit wie folgt aus:


/***********************************************/
/*                                             */
/*   quicksort nicht rekursiv                  */
/*                                             */
/***********************************************/

quicksort_nonrec: procedure expose daten.

   call_stack. = ""
   call_stack.1 = 1" "daten.0
   stackpos = 1

   do while stackpos > 0

      links = word(call_stack.stackpos, 1)
      rechts = word(call_stack.stackpos, 2)

      say "quicksort_nonrec ("stackpos") läuft mit "links","rechts

      if links < rechts then do

         teiler = teile(links, rechts)

         li_neu = teiler + 1
         re_neu = rechts
         call_stack.stackpos = li_neu" "re_neu

         stackpos = stackpos + 1

         li_neu = links
         re_neu = teiler - 1
         call_stack.stackpos = li_neu" "re_neu

      end
      else do
         stackpos = stackpos - 1
      end

   end

   return


Damit gab's dann kein Problem mehr; die Information, die vorher in
den call_stack abgelegt wurde (Problem schon bei 60 Elementen), liegt
jetzt im Stem call_stack, und da ist genügend Platz ... auch bei meinem
quasi historischen OS/2-System.