viff
changeset 877:f12a36276d56
Described the complexity of the bitonic sort.
author | Martin Geisler <mg@daimi.au.dk> |
---|---|
date | Fri, 08 Aug 2008 10:23:14 +0200 |
parents | 3d13185afed2 |
children | f39882ce0e89 |
files | apps/sort.py |
diffstat | 1 files changed, 21 insertions(+), 0 deletions(-) [+] |
line diff
1.1 --- a/apps/sort.py Fri Aug 08 10:18:10 2008 +0200 1.2 +++ b/apps/sort.py Fri Aug 08 10:23:14 2008 +0200 1.3 @@ -17,6 +17,27 @@ 1.4 # You should have received a copy of the GNU Lesser General Public 1.5 # License along with VIFF. If not, see <http://www.gnu.org/licenses/>. 1.6 1.7 +# This example demonstrates how a secure sorting algorithm can be 1.8 +# implemented using VIFF. The algorithm used is bitonic sort which was 1.9 +# chosen in order to maximize the amount of work (comparisons) done in 1.10 +# parallel. Bitonic sort uses 1/2 * log n * (log n + 1) comparator 1.11 +# stages and each stage consists of n/2 parallel comparisons. The 1.12 +# total number of comparisons is thus in O(n log^2 n). 1.13 +# 1.14 +# This is larger than the lower bound of O(n log n) for comparison 1.15 +# based sorting algorithms, achieved by mergesort and other well known 1.16 +# algorithms. The problem with mergesort is its merging step: to merge 1.17 +# two sorted arrays of length n/2 one needs up to n comparisons, and 1.18 +# what is worse, the comparisons must be made one after another. The 1.19 +# mergesort does one merge with lists of size n/2, two merges with 1.20 +# lists of size n/4, and so on. This gives a total chain of 1.21 +# comparisons of length n + n/2 + n/4 + ... + 1 = 2n - 1, which is 1.22 +# more than the O(log^2 n) stages needed by the Bitonic Sort. 1.23 +# 1.24 +# See this page for more analysis and a Java implementation: 1.25 +# 1.26 +# http://iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm 1.27 + 1.28 # Give a player configuration file as a command line argument or run 1.29 # the example with '--help' for help with the command line options. 1.30