Sortier-Algorithmen
Mit dem java-Archiv sortDemo.jar in
diesem Verzeichnis können Sie
die Arbeitsweise von Sortieralgorithmen nachvollziehen; siehe auch die
Lehre zu Algorithmen (IAD).
Die Java-Quellen — ursprünglich von James Gosling und Jason Harrison und
modifiziert von A. Weinert —
stehen ggf. zur Verfügung.
Alle Quellen sind im Vergleich mit dem reinen Applet-Original von 1995
(Gosling) schon 2005 sehr stark modifiziert worden. Sie liefen als Applet und
Applikation. Inzwischen sind Applets (durch Oracle ab 2015) so tot, dass
2017 die Applet-Implementierung aufgegeben wurde.
Zwar wurden noch 2014 die seit einigen Jahren von SUN/Oracle am Laufen
gehinderten Applets gemäß Oracle's aktuellen Sicherheitsanforderungen
ertüchtigt. 2015 machte Google wohl seine Drohung wahr, Applets etc. mit
seinen Browsern gar nicht mehr laufen zu lassen. Außerdem wurden die
Bedingungen für Applets, aber auch für Web-Start, ständig geändert bzw.
verschärft. Ergo, wie gesagt, Aufgabe dieses Ansatzes.
Start als Anwendung:
java[w][.exe] -jar sortDemo.jar QuickSort
bzw. mit
java -jar <whereItWasDownloadedTo>sortDemo.jar [nameOfAlgorithm]
laufen, mit: BidirectionalBubbleSort, FastQSort, QuickSort, ShellSort, BubbleSort,
QubbleSort, CombSort11, HeapSort, RadixSort, EQSort, InsertionSort,
SelectionSort, ExtraStorageMergeSort, MergeSort, ShakerSort.
Vorbereitung:
javac -d .\build de\meva_lab\sortDemo\*.java
jar cfm .\build\sortDemo.jar .\de\meva_lab\sortDemo\SortApplet.mf -C build de\meva_lab\sortDemo\
Sie können eigene Sortieralgorithmen als Erweiterung von
de.meva_lab.sortDemos.SortApp.SortAlgorithm schreiben, indem Sie die Methode
void sort(int[]) implementieren.
Das Folgende ist weitgehend James Goslings Originalbeschreibung von 1996.
The following is mostly James Gosling's original 1996 Applet
documentation.
We all know that Quicksort is one of the fastest algorithms for sorting.
It's not often, however, that we get a chance to see exactly
how fast Quicksort really is. The following Applets chart the progress
of several common sorting algorithms while sorting an array of data using
in-place algorithms. This means that the algorithms do not allocate
additional storage to hold temporary results: they sort the data in place.
(This is inspired by the algorithm animation work at Brown University and the
video Sorting out Sorting by Ronald Baecker from the University
of Toronto circa 1970.)
Some of these sorts are very stupid or very slow and should not be used
in code. The use of Bubblesort is deprecated.
In-Place Mergesort is yet another abomination. Mergesort is supposed to
run in O(n log n), but the implementation here runs in O(n * n). This is
because a temporary scratch array is not used. As with most of the
examples here, In-Place Mergesort sorts the elements in the array without
using additional storage (other than the stack used for the recursive calls,
and temporary variables). Jack Snoeyink has provided me with a the
Double Storage Mergesort algorithm sort implementation that uses a scratch
array.
Here James Gosling placed all demos as Applets, which will not work any more.
What's missing ...
- Three way merge.
- Quicksort with duplicated pivots.
- Random Swap sort.
- Bubblesort with early termination.
- Quicksort that sorts the shorter list first.
- Quicksort that sorts lists of size < 30 with Insertion sort.
- Quicksort using Van Emden's exchange procedure for
partitioning.
- Variants of Mergesort, including the "correct" method
as well as galloping.
- Samplesort.
If you'd like to code any of those algorithms, please do and send me
the code.
Metrics to be added (done by A. Weinert, counting just "steps"):
- Counting of element comparisons and element swaps.
- Counting of loop comparisons.
- Counting of recursive calls.
One of my favourite references to sorting routines is "Sorting" by
William A. Martin, in ACM Computing Surveys, Volume 3, Number 4, December
1971, pages 147-174. The abstract reads:
The bibliography appearing at the end of this article lists 37
sorting algorithms and 100 books and papers on sorting published in the
last 20 years. The ideas presented here have been abstracted from this body
of work, and the best algorithms known are given as examples. As the
algorithms are explained, references to related algorithms and mathematical
or experimental analyses are given. Suggestions are then made for choosing
the algorithm best suited to a given situation.
Disclaimer: If you use this page as part of your teaching, please let me
know. I tend to refer students who ask too many questions back to their
instructor. Requests for translations of the Java sources to other
programming languages will be denied. This page was created in a fit of
"thesis avoidance" in the summer of 1996.
James Gosling
Originally created by
- James Gosling, SUN (1995, 1996) and modified by
- Albrecht Weinert, FH BO, weinert-automation
(2005, 2019)
Revision: $Revision : 12 $ ($Date: 2022-05-14 21:52:01 +0200 (Sa, 14 Mai 2022) $)