Various sorting algorithms
The applet below illustrates several sorting algorithms. What is sorted is arrays of numbers. A member of an array is represented by two coordinates: horizontal (index into the array) and vertical (the magnitude of that member). Graphically the members may be represented by small circles or by lines of the corresponding length.
It's not difficult to obtain information about and a programming advice, even the source code, for a specific algorithm, see the references below. A search on the web brings up a multitude of online sources. Some source code is being distributed by the Sun, Inc., the makers of Java. However, the main problem with an algorithm demonstration is in making it interactive. I can say that, on my part, the real challenge in writing the applet was in getting the One step button. The way I do that is running the algorithms in what's called a thread in Java parlance. A thread is a thread of execution, if this helps you better understand what is it about. A single applet or an application may run multiple (execution) threads simultaneously. In my implementation of the applet the drawing part runs in one thread, the algorithms in another. After an algorithm executes one step, it notifies the drawing thread about the fact and suspends itself. The drawing step then draws the new state of the sorting process and then asks the algorithm to resume.
This appears to be a reasonable approach that also allows for algorithm animation with a minimum effort. However the applet had a trouble running in Netscape browsers. The One step button works fine, while the animation had a tendency to hang and needed repeated prompting (pressing the Run button.) The Netscape even issues a warning (that could be seen in the Java console) to the effect that suspending a thread may cause the browser to misbehave. The applet however runs fine in the Internet Explorer v 5.0.
To overcome that problem I have slowed the algorithms artificially; and at this point the applet seems to run in both Netscape 4.6 and Internet Explorer 5.0. However, it still appears to do some violence to Nescape 6.0. The algorithms do run. However the display flickers rhythmically and unpleasantly.
The various algorithms behave differently in different situations. To allow for experimentation and algorithm comparison, the initial array could be created with random data, or strictly increasing data, or in some other standard ways. The same array could be used with different algorithms - just check the Same array button.
Please note: due to an idiosyncrasy of implementation, the array to be sorted is not shown until one of the "action" buttons (Run or One step) has been pressed.)
| What if applet does not run? |
The algorithms have been adapted from https://www.cs.bell-labs.com/cm/cs/pearls/SortAnim.java
References
- J. Bentley, Programming Pearls, Addison-Wesley, 2000
- A. Levitin, Introduction to The Design & Analysis of Algorithms, Addison-Wesley, 2003
- R. Sedgewick, Bundle of Algorithms in C++, Addison-Wesley, 2001, 3rd edition
|Activities| |Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny
71544263