home *** CD-ROM | disk | FTP | other *** search
/ Amiga ISO Collection / AmigaUtilCD2.iso / Programming / Misc / CLISP-1.LHA / CLISP960530-sr.lha / src / sort.d < prev    next >
Encoding:
Text File  |  1996-04-15  |  4.2 KB  |  94 lines
  1. # n log(n) - Sortierroutine für CLISP
  2. # Bruno Haible 9.6.1992
  3.  
  4. # Ziel: Eine feste Anzahl n von Elementen zu sortieren,
  5. # mit maximalem Zeitaufwand von O(n log(n)),
  6. # und dies, ohne allzu aufwendige Datenstrukturen aufzubauen.
  7.  
  8. # Von außen ist einzustellen:
  9. # Identifier SORTID :
  10. #   Identifier, der die Inkarnation dieser Package identifiziert
  11. # Typ SORT_ELEMENT :
  12. #   Typ der Elemente, die zu sortieren sind.
  13. # Typ SORT_KEY :
  14. #   Typ des Key, nach dem sortiert wird.
  15. # Funktion SORT_KEYOF, mit
  16. #   local SORT_KEY SORT_KEYOF (SORT_ELEMENT element);
  17. #   liefert den Sortier-Key eines Elements.
  18. # Funktion SORT_COMPARE, mit
  19. #   local signean SORT_COMPARE (SORT_KEY key1, SORT_KEY key2);
  20. #   liefert >0 falls key1>key2, <0 falls key1<key2, 0 falls key1=key2.
  21. # Funktion SORT_LESS, mit
  22. #   local boolean SORT_LESS (SORT_KEY key1, SORT_KEY key2);
  23. #   liefert TRUE falls key1<key2, FALSE falls key1>=key2.
  24.  
  25. #ifndef SORT
  26.   # Eine Art "SORT-Package"
  27.   #define SORT(incarnation,identifier)  CONCAT4(sort_,incarnation,_,identifier)
  28. #endif
  29.  
  30. # Quelle: Samuel P. Harbison, Guy L. Steele: C - A Reference Manual, S. 61
  31.  
  32. # Feststellen, ob element1 < element2 gilt:
  33.   #define less(element1,element2)  \
  34.     SORT_LESS(SORT_KEYOF(element1),SORT_KEYOF(element2))
  35.  
  36. # sort(v,n); sortiert den Array v[0]..v[n-1] in aufsteigende Reihenfolge.
  37.   local void SORT(SORTID,sort) (SORT_ELEMENT* v, uintL n);
  38.   local void SORT(SORTID,sort) (v,n)
  39.     var reg7 SORT_ELEMENT* v;
  40.     var reg6 uintL n;
  41.     { var reg3 SORT_ELEMENT* w = &v[-1];
  42.       # w[1]..w[n] ist dasselbe wie v[0]..v[n-1] .
  43.       # Man faßt die Zahlen 1,...,n so zu einem balancierten Binärbaum
  44.       # zusammen, daß k die Söhne 2*k und 2*k+1 habe.
  45.       # Ein Teilstück w[r]..w[s] heißt sortiert, wenn für alle
  46.       # k mit r <= k <= s gilt:
  47.       #   Falls 2*k <= s, gilt w[k] >= w[2*k], und
  48.       #   falls 2*k+1 <= s, gilt w[k] >= w[2*k+1],
  49.       # d.h. wenn jedes Element einen Wert >= dem Wert seiner Söhne hat.
  50.       # Teilaufgabe:
  51.       #   Sei 0<r<=s und w[r+1]..w[s] bereits sortiert.
  52.       #   Sortiere w[r]..w[s].
  53.       #   Zeitaufwand: max. O(log(s)).
  54.         #define adjust(r,s)  \
  55.           { var reg2 uintL i = r;                                                       \
  56.             loop # w[i] ist im Teilbaum unterhalb von i unterzubringen                  \
  57.               { var reg1 uintL j = 2*i; # ein Sohn von i                                \
  58.                 if (j > s) break; # 2*i und 2*i+1 nicht mehr vorhanden -> fertig        \
  59.                 if ((j < s) && less(w[j],w[j+1])) { j++; } # evtl. j = 2*i+1, der andere Sohn von i \
  60.                 # j ist der Sohn von i mit dem größeren Wert.                           \
  61.                 if (less(w[i],w[j])) # Falls w[i] < w[j],                               \
  62.                   { swap(reg4 SORT_ELEMENT, w[i], w[j]); } # w[i] und w[j] vertauschen  \
  63.                 # w[i] ist nun der größere der drei Werte w[i],w[2*i],w[2*i+1].         \
  64.                 # Jetzt haben wir aber w[j] verkleinert, so daß ein                     \
  65.                 # tail-rekursives adjust(j,s) nötig wird:                               \
  66.                 i = j;                                                                  \
  67.           }   }
  68.       if (n<=1) return; # nichts zu tun?
  69.       # Wegen 2*(floor(n/2)+1) > n ist w[floor(n/2)+1]..w[n] bereits sortiert.
  70.       { var reg5 uintL r;
  71.         for (r = floor(n,2); r>0; r--)
  72.           { # Hier ist w[r+1]..w[n] sortiert.
  73.             adjust(r,n);
  74.             # Hier ist w[r]..w[n] sortiert.
  75.       }   }
  76.       # Nun ist w[1]..w[n] ein sortierter Baum.
  77.       # Jeweils das höchste Element w[1] entnehmen und ans Ende setzen:
  78.       { var reg5 uintL s;
  79.         for (s = n-1; s>0; s--)
  80.           { # Hier ist w[1]..w[s+1] ein sortierter Baum, und
  81.             # w[s+2]..w[n] die höchsten Elemente, aufsteigend sortiert.
  82.             swap(reg1 SORT_ELEMENT, v[0], v[s]); # w[1] und w[s+1] vertauschen
  83.             # Hier ist w[2]..w[s] ein sortierter Baum, und
  84.             # w[s+1]..w[n] die höchsten Elemente, aufsteigend sortiert.
  85.             adjust(1,s); # w[1] in den Baum hineinsortieren
  86.             # Hier ist w[1]..w[s] ein sortierter Baum, und
  87.             # w[s+1]..w[n] die höchsten Elemente, aufsteigend sortiert.
  88.       }   }
  89.     }
  90.  
  91. #undef adjust
  92. #undef less
  93.  
  94.