My sorting home page presents a number of original sorting algorithms (+ variants) in Java designed by Arne Maus. All algorithms are downloadable and their usage are regulated by the BSD license (basically that their original author must always be credited whenever used).
All code is accompanied by a pubished paper explaining its usage, performance and limitations. Disclaimer: Although all these algorithms are thoroughly tested, no guarantee is given that they work as intended in any application where they might be used.
Emneord:
Parallel programming,
Java,
Object Oriented programming,
Delaunay triangulation,
Sorting,
algorithms
Publikasjoner
-
Maus, Arne (2015). A full parallel Quicksort algorithm for multicore processors. NIKT: Norsk IKT-konferanse for forskning og utdanning.
ISSN 1892-0713.
-
Gjessing, Stein & Maus, Arne (2012). Teaching predicates and invariants on shared data structures in concurrent programming, In Edward F. Gehringer & Dick Brown (ed.),
SPLASH '12 Conference on Systems, Programming, and Applications: Software for Humanity, Proceedings of the 2012 workshop on Developing competency in parallelism: techniques for education and training.
ACM Publications.
ISBN 978-1-4503-1840-2.
Artikkel.
s 9
- 14
-
Maus, Arne (2011). A full parallel radix sorting algorithm for multicore processors, In
Norsk Informatikkonferanse NIK 2011.
Tapir Akademisk Forlag.
ISBN 978-82-519-2843-4.
paper 4.
s 37
- 48
Fulltekst i vitenarkiv.
-
Maus, Arne & Moen Drange, Jon (2010). All closest neighbors are proper Delaunay edges generalized, and its application to parallel algorithms, In Terje Fallmyr & Erik Hjelmås (ed.),
Norsk Informatikkonferanse.
Tapir Akademisk Forlag.
ISBN 978-82-519-2703-1.
Artikkel nr. 1.
s 1
- 12
Vis sammendrag
In this paper we first prove that for any set of points P in the plane,the closest neighbor b to any point p in P is a proper triangle edge bp in D(P), the Delaunay triangulation of P. We also generalize this result and prove that the j'th (second, third, ..) closest neighbors bj to p are also edges pbj in D(P) if they satisfy simple tests on distances from a point. Even though we can find many of the edges in D(P) in this way by looking at close neighbors, we give a three point example showing that not all edges in D(P) can be found in this way. For a random dataset we give results from test runs and a model that show that our method finds on the average 4 edges per point in D(P). Also, we prove that the Delaunay edges found in this way form a connected graph. We use these results to outline two parallel algorithms for finding D(P). Finally, we comment on using these theorems and solving the k'th closest neighbors problem.
-
Maus, Arne & Lingjærde, Ole Christian (2009). LASTING EFFECTS OF AUTOMATIC PLAGIARISM DETECTION IN AN INTRODUCTORY COURSE IN PROGRAMMING, In L Gómez Chova (ed.),
INTED2009 Proceedings CD.
The International Academy of Technology, Education and Development.
ISBN 978-84-612-7578-6.
i sessjonen:Emerging Technologies: Internet Based Technologies.
-
Maus, Arne (2008). IPS, sorting by transforming an array into its own sorting permutation with almost no space overhead, In Frode Sandnes Eika & Andreas Prinz (ed.),
Norsk informatikkonferanse NIK 2008.
Tapir Akademisk Forlag.
ISBN 978-82-519-2386-6.
artikkel.
s 63
- 74
Vis sammendrag
This paper presents two new algorithms for inline transforming an integer array ‘a’ into its own sorting permutation - that is: after performing either of these algorithms, a[i] is the index in the unsorted input array ‘a’ of its i’th largest element (i=0,1..n-1). The difference between the two IPS (Inline Permutation Substitution) algorithms is that the first and fastest generates an unstable permutation while the second generates the unique, stable, permutation array. The extra space needed in both algorithms is O(log n) – no extra array of length n is needed! The motivation for using these algorithms is given along with their pseudo code. To evaluate their efficiency, they are tested relative to sorting the same array with Quicksort on 4 different machines and for 14 different distributions of the numbers in the input array, with n=10, 50, 250.. 97M. This evaluation shows that both IPS algorithms are generally faster than Quicksort for values of n less than 107, but degenerates both in speed and demand for space for larger values. These are results with 32 bit integers (with 64 bits integers this limit would be proportionally higher, at least 1014 ). The two IPS algorithms do a recursive, most significant digit radix sort (left to right) on the input array while substituting the values of the sorted elements with their indexes.
-
Maus, Arne & Lingjærde, Ole Christian (2008). The application of a novel plagiarism detection system to an introductory course in programming: lessons learned, In I. Gómes Chova; D. Martí Belenguer & I. Candel Torres (ed.),
INTED2008 IProceedings.
The International Academy of Technology, Education and Development.
ISBN 978-84-612-0190-7.
artikkel 578.
-
Maus, Arne (2007). Buffered Adaptive Radix – a fast, stable sorting algorithm that trades speed for space at runtime when needed, In Frode Eika Sandnes (ed.),
Norsk informatikkonferanse NIK 2007.
Tapir Akademisk Forlag.
ISBN 978-82-519-2272-2.
Kap. 2.
s 19
- 30
-
Maus, Arne & Gjessing, Stein (2007). A Model for the Effect of Caching on Algorithmic Efficiency in Radix based Sorting, In Sergiu Dascalu & Petre Dini (ed.),
ICSEA 2007 (International Conference on Autonomic and Autonomous Systems).
IEEE.
ISBN 978-0-7695-2937-0.
33.
-
Maus, Arne (2006). Making a fast unstable sorting algorithm stable, In Chunming Rong & Arne Løkketangen (ed.),
NIK'2006 : Norsk informatikkonferanse.
Tapir Akademisk Forlag.
ISBN 82-519-2186-4.
Arikkel nr. 4.
s 41
- 52
-
Gjessing, Stein & Maus, Arne (2005). Discrete Event Simulation of a Large OBS Network, In Mo Jamshidi (ed.),
Proceedings 2005 IEEE International Conference on Systems, Man and Cybernetics.
IEEE.
Kapittel.
-
Maus, Arne (2005). Research and Curricula Developemnt of Norwegian Universities From the early years to the mid-1970s, In Janis Bubenko; John Impagliazzo & Arne Sølvberg (ed.),
History of Nordic Computing.
Springer.
ISBN 0-387-24167-1.
12.
s 137
- 154
-
Gjessing, Stein & Maus, Arne (2002). A Fairness Algorithm for High-speed Networks based on a Resilient Packet Ring Architecture, In Abdelkader El Kamel (ed.),
2002 IEEE International Conference on Systems, Man and Cybernetics.
IEEE.
ISBN 2-9512309-4-X.
CD proceeding.
Fulltekst i vitenarkiv.
Vis sammendrag
IEEE is currently standardizing a spatial reuse ring topology network called the Resilient Packet Ring (RPR, IEEE P802.17). The goal of the RPR development is to make a LAN/MAN standard, but also WANs are discussed. A ring network needs a fairness algorithm that regulates each stations access to the ring. The RPR fairness algorithm is currently being developed with mostly long distances between stations in mind. In this paper we discuss the feedback aspects of this algorithm and how it needs to be changed in order to give good performance if and when RPR is used for high-speed networks and LANs with shorter distances between stations. We discuss different architectural parameters including buffers sizes and distances between stations. We suggest the use of triggers instead of timers to meet the response requirements of high-speed networks. We have developed a discrete event simulator in the programming language Java. The proposed improvements are compared and evaluated using a ring network model that we have built using our simulator.
-
Maus, Arne (2002). ARL, a faster in-place, cache friendly sorting algorithm, In Norvald Stohl; Torbjørn Strøm; Terje Fallmyr; Sissel Haddjerroudit; Dag Langmyhr & Fredrik Manne (ed.),
Norsk Informatikkonferanse NIK'2002.
Høgskolen i Buskerud.
ISBN 82-91116-45-8.
Chapter.
s 85
- 95
-
Maus, Arne (1996). Vitenskap, informasjonsteknologi, og samfunnsmessige virkninger, I: Odd Wormnæs (red.),
Vitenskap - enhet og mangfold.
ad Notam/Gyldendal, Oslo.
ISBN 82-417-0682-0.
s 388
- 406
Vis sammendrag
Dette kapittelet handler om virkningene av data- og datanettteknologien. Vi skal søke å se på vitenskapens rolle, samfunnsmessige virkninger og etiske dilemma som reiser seg ved anvendelser av IT.
-
Maus, Arne (1995). Datavtalene og Arbeidsmilojøloven. IT og arbeidsplassene. Personvern og sikerheten i informasjonssamfunnet, I: Gisle Hannemyr; Arne Maus; Gerhard M Skagestein & Aud Sugar (red.),
BIT 1 A Brukersystemer.
ISBN 82-02-15361-1.
s 46
- 71
Vis sammendrag
To kapitler i lærebok for videregående skole i IT.
-
Maus, Arne (1984). Delanay Triangulation and the Convex Hull of n Points in expected linear Time. BIT Numerical Mathematics.
ISSN 0006-3835.
24(37), s 151- 163
Vis sammendrag
An algorith is presented which produces a Delaunay triangulation of n points in the Euclidean plane in expexted linear time. The expected execution time is acheived when the data are (not too far from) uniformly distributed. A modification of the algorithm discussed in the appendix, treats most of the non-uniform distributions. The basis of this algorithm is a geographical partitioning of the plan into boxes by the well-known Radix algorithm. This partiotioning is also used as a basis for a linear time algorithm for finding the convex hull of n points in the Euclidean plane.
-
Maus, Arne (1982). Technology and Employment, In Eystein Forrum (ed.),
Computerization of Working Life.
Ellis Horwood limited, Chirhester.
ISBN 0-85312-584-8.
s 61
- 84
Vis sammendrag
The question of wheather EDP has an impact on employment, is one of the most cotroversial issues concerning the social impact of technology.
-
Maus, Arne & Endresen, Jan (1979). Misuse of computer-generated results. Medical and Biological Engineering and Computing.
ISSN 0140-0118.
s 126- 129
Vis sammendrag
The number of statistical tests performed has increased by several orders of magnitude through the use of computers and read-made statistical packages. The vast majority of these tests neither physically can be, nor ever are, published. Only tests which show a strog statistical corrolation between some variables seems to be sorted out for publication. This practice, which can be found in applied sciences such as social and medical sciences, is investigated and shown in many cases to lesd to a considerable increase in the percentage of published false results. A new function to be perormed by statistical packages is then proposed to reduce theis percentage.
-
Maus, Arne (1975). On Access to Temporary Resources. BIT Numerical Mathematics.
ISSN 0006-3835.
15(1), s 72- 84
Vis sammendrag
The sharable resources of a multiprogramming system can be classified as either permanent or temporary, and their use can be classified as either exclusive or non-exclusive. While semaphores, as defined by Dijkstra syncronize access to permanent resources, this article proposes two new primitives for synchronize access to temporary resources. Theis usefullness is demonstrated by examining the problem of a number of 'readers' and 'writers' sharing a single file. Finally, a high-level language notation is proposed which synchronizes access to a declared, sharable resource of any of the categories classified above.
Se alle arbeider i Cristin
-
Maus, Arne & Gjessing, Stein (2014). Practical Parallel Programming – a B.S. course on how to design an efficient parallel algorithm..
EduPar14.
ISBN 978-1-4799-4117-9.
8 s.
-
Brunland, Anders; Hegna, Knut; Lingjærde, Ole Christian & Maus, Arne (2011). Rett på Java - 3.utg.
Universitetsforlaget.
ISBN 978-82-15-01852-2.
390 s.
-
Brunland, Anders; Hegna, Knut; Lingjærde, Ole Christian & Maus, Arne (2005). Rett på Java, 2 utg.
Universitetsforlaget.
ISBN 82-15-00781-3.
363 s.
-
Brunland, Anders; Hegna, Knut; Lingjærde, Ole Christian & Maus, Arne (2003). Rett på Java.
Universitetsforlaget.
ISBN 82-15-00257-9.
280 s.
-
Hannemyr, Gisle; Maus, Arne; Skagestein, Gerhard M & Sugar, Aud (red.) (1995). BIT 1 A Brukersystemer.
ISBN 82-02-15361-1.
Se alle arbeider i Cristin
-
Opdal, Lars-Erik; Maus, Arne & Stray, Viktoria (2016). Parallelle beregninger med MPI i delt og distribuert minne.
-
Maus, Arne (2002). PRP - Parallel Recursive Procedures, a low cost, easy to use alternative for some often ocurring classes of problems.
Vis sammendrag
Almost all work on parallelizing programs uses the abstraction of communicating parallel programs in the form of processes or parallel threads. This lecture presents an alternative abstraction - parallelizing a problem though the use of a recursive procedure (PRP). With this PRP concept the recursion tree is split among all participating machines (connected by a LAN or Web). The user involvement in this process is minimal by just putting in two different comments in the original recursive program. What restrictions that has to be put on the recursive procedure in PRP is presented along with a sketch of the implementation and examples on problems solved. This concept is demonstrated to scale very well up to 120 machines (max. tried so far) and for some interesting classes of problems. This is a report from an ongoing series of master thesis at the Dept. of Informatics, Univ. of Oslo, which now has produced a well working Java based platform for the PRP system.
-
Maus, Arne (2002). Two 'new' sorting algorithms - and the effect of multi level caching on performance.
Vis sammendrag
This presentation introduces two new, fast sorting algoritms: MSort and Psort, both having advantages (in-place re-ordering and generating the sorting permutation). Both are significantly faster then Quicksort. MSort is a modified Most Significant Radix algorithm. PSort is a fast way to generate the permutation p that defines the sorting order of a set of integer keys in an integer array ¿a¿- that is: a[p[i]] is the i¿th sorted element in ascending order. The motivation for using Psort is given along with its implementation in Java. This distribution based sorting algorithm, Psort, is compared to two comparison based algorithms, Heapsort and Quicksort, and two other distribution based algorithms, Bucket sort and Radix sort. The relative performance of the distribution sorting algorithms for arrays larger than a few thousand elements are assumed to be caused by how well they handle caching (both level 1 and level 2). The effect of caching is investigated, and based on these results, more cache friendly versions of Psort and Radix sort are presented and compared.
-
Maus, Arne (2000). Sorting by generating the sorting partition, and the effect of caching on sorting.
Vis sammendrag
This paper presents a fast way to generate the permutation p that defines the sorting order of a set of integer keys in an integer array 'a' - that is: a[p[i]] is the i'th sorted element in ascending order. The motivation for using Psort is given along with its implementation in Java. This distribution based sorting algorithm is compared to two comparison based algortthms, Heapsort and Quicksort, and two other distribution based algorithms, Bucket sort and Radix sort. The relative performance of the distribution sorting algorithms for arrays larger then a few thousand elements are assumed to be caused by how well they handle caching (both level 1 and 2). The effect of caching is invesitgated, and based on these results, more cache friendly versions of Psort and Radix sort are presented and compared.
-
Gjessing, Stein; Maus, Arne; Strøm, Torstein & Huse, Lars Paul (1999). Running the Synthetic Aperture Radar (SAR) Application on a switched SCI cluster.
Vis sammendrag
We describe how a real application, the Syntetic Aperture Radar (SAR) program, is parallelized and run on a cluster of PCs connected by SCI. We have a prototype SCI switch that uses the serial IEEE 1355 HIC technology in its switching fabric. The prototype switch can not keep up with the speed of the SCI interconnect, and we analyze and discuss how switch performance influence the execution time of our parallelized application.
-
Maus, Arne (1999). Klynger av PC-er, framtidas superdatamaskiner.
Vis sammendrag
Oversikt over potensielle hastighetsforbedringer og programvare for å å koble tett sammen et antall PCer
-
Maus, Arne (1999). Objektorientert systemutvikling.
Vis sammendrag
Grunnleggende innføring i begreper, metoder og anvendelser.
-
Maus, Arne; Strøm, Torstein; Gjessing, Stein & Huse, Lars Paul (1999). Final report on the testing of the SCI to HIC switch & Running the SAR (Synthetic Aperture Radar) application in a switched cluster of PCs.
Vis sammendrag
This combined delivery first describes testing of a HIC based SCI switch embedded in a cluster of PCs running standard micro benchmarks (ping-pong latency and throughput) of various data packet sizes and with various configurations of 2 and 3 switched SCI rings. The switch itself is made up of switching units that translates IEEE 1596 SCI packets to and from the serial IEEE 1355 HIC technology and is more thoroughly described in D4.1.1 and D 4.1.2 and the micro benchmarks has in more detail been reported in D4.1.4 and D4.1.5. The limitations of this prototype switch are then discussed. After these initial tests, a real industrial application, the SAR (Synthetic Aperture Radar) application was run through the switch connected as a 3-way switch, varying the number of nodes in each switched SCI rings. This deliverable concludes with a discussion of the viability of an industrial version of this switch.
-
Maus, Arne; Strøm, Torstein; Gjessing, Stein & Huse, Lars Paul (1999). Running the SAR Application on a Cluster of PCs Connected with SCI using a HIC based SCI switch.
Vis sammendrag
This paper describes a prototype SCI-switch and its behaviour in a real application. The switching fabric uses the IEEE 1355 HIC technology to switch SCI packets in a switch with up to seven SCI ports. In our lab we have tested a switch with up to three SCI ports. We report on the performance of a Synthetic Aperture Radar (SAR)-application when it is run on a number of dual processor PCs connected by SCI and using our HIC-based SCI switch.
-
Maus, Arne; Strøm, Torstein; Gjessing, Stein & Huse, Lars Paul (1999). Running the SAR-application on a cluster of PCs connected with SCI, using a HIC-based SCI-switch.
Vis sammendrag
This paper first describes testing of the HIC based SCI switch embedded in a cluster of PCs running standard micro benchmarks (ping-pong latency and throughput) of various data packet sizes and with various configurations of 2 and 3 switched SCI rings. The switch itself is made up of switching units that translates IEEE 1596 SCI packets to and from the serial IEEE 1355 HIC technology. The limitations of this prototype switch are then discussed. A real industrial application, the SAR (Synthetic Aperture Radar) application was run through the switch connected as a 3-way switch, varying the number of nodes in each switched SCI ring. This paper concludes with a discussion of the viability of an industrial version of this switch.
-
Strøm, Torstein; Halfen, Bjørn; Maus, Arne & Gjessing, Stein (1999). A HIC based SCI switch - implementation and performance.
Vis sammendrag
This paper describes a prototype switching unit that translates IEEE 1596 SCI packets to and from the serial IEEE 13555 HIC technology. The unit has one SCI interface and twelve HIC interfaces. Up to seven of these units can be placed back-to-back to make up an SCI switch. Hardware and system behaviour is described. Latency and throughput are presented for different configurations and different sizes of user data. Finally the potential of an industrial version of this prototype is evaluated.
-
Strøm, Torstein; Halfen, Bjørn; Maus, Arne & Gjessing, Stein (1999). Switched embedded workstation cluster exploiting the HIC based SCI switch.
Vis sammendrag
This report describes performance characteristics of an experimental HIC based SCI switch embedded in a cluster of PCs. Internally the switch translates IEEE 1596 SCI packets to and from the serial IEEE 1355 HIC technology. Architectually up to seven SCI rings can be connected to the switch, but due to limited resources, only a 2x2 and a 3x3 switch has been tested. This deliverable focuses on presenting a comprehensive set of low level latency and throughput figures for different configurations, and evaluating the state of this prototype switch and the potentials of an industrial version of this switch.
-
Strøm, Torstein; Halfen, Bjørn; Maus, Arne & Gjessing, Stein (1999). Working SCI switch based on HIC components.
Vis sammendrag
This paper describes a prototype switching unit that translates IEEE 1596 SCI packets to and from the serial IEEE 1355 HIC technology. The unit has one SCI interface and twelve HIC interfaces. Up to seven of these units can be placed back-to-back to make up an SCI switch. Hardware and system behaviour is described. Latency and throughput are presented for different configurations and different sizes of user data. Finally the potential of an industrial version of this prototype is evaluated.
-
Strøm, Torstein; Maus, Arne; Halfen, Bjørn & Gjessing, Stein (1999). A HIC Based SCI switch - implementation and performance.
Vis sammendrag
This paper describes a prototype switching unit that translates IEEE 1596 SCI packets to and from the serial IEEE 1355 HIC technology. The unit has one SCI interface and twelve HIC interfaces. Up to seven of these units can be placed back-to-back to make up an SCI switch. Hardware and system behaviour is described. Latency and throughput are presented for different configurations and different sizes of user data. Finally the potential of an industrial version of this prototype is evaluated.
-
Ryan, Stein Jørgen; Maus, Arne & Gjessing, Stein (1997). An operating system independent driver for an I/O based SCI interface.
-
Sjøberg, Dag; Jørgensen, Magne & Maus, Arne (1996). Evaluating Software Maintenance Technology.
-
Maus, Arne & Aas, Torfinn (1995). PRP - Parallel Recursive Procedures.
Vis sammendrag
It is believed that writing parallel programs is hard. Therefore a pradigm for writing parallel programs that is not much harder than writing a sequeltial program is in demand. This paper describes a general method for parallelizing programs based on the idea of using recursive procedures as the grain of parallelism (PRP). This paradigm only adds a few new constructs to an ordinary sequential program with recursive procedures and makes both the underlying hardware topology and in most cases also the number of independant processing nodes, transparent to the programmer. The implementation reported in this paper uses workstations and servers connected to an Ethernet. The efficiency achieved by the PRP-concept must be said to be good with a more than 50% processor utilization on the two problems reported. Other implementatons of the PRP-paradigm is also reported.
-
Jørgensen, Magne & Maus, Arne (1993). A case study of software maintenance tasks.
-
Maus, Arne (1992). Entropy as a Complexity Measure, and the Optimal Module Size of Object Oriented Programs.
Vis sammendrag
This paper defines a measure for the complexity of a program and its components as seen from a maintenance programmer point of view. This is done by using the entropy measure from thermodynamics. It is shown that two programmes solving the same problem differ considerably in entropy - the program properly structured into classes and procedures having the lowest entropy. The optimal number of procedures and classes is derived. This complexity measure can easily be built into any compiler.
-
Maus, Arne (1992). Solutions to a trivial problem - a study in programming paradigms.
Vis sammendrag
The complexity theories of programming seek to find and classify the best algorithms for a given problem. This paper has a different perpective. The 'natural' solutions to a trivial problem (finding the sum of the n first natural numbers) are investigated, And it is demonstrated that there is an extreme variation in the time and space efficiency in the solutions we get when following dominant programming styles. This paper can both be used as a student tutorial and be seen as a criticism of some of the more popular programming paradigms.
-
Maus, Arne (1991). Entropy as a Complexity Measure, and the Optimal Module Size of Object Oriented Programs.
Vis sammendrag
This paper defines a measure for the complexity of a program and its components as seen from a maintenance programmer point of view. This is done by using the entropy measure from thermodynamics. It is shown that two programmes solving the same problem differ considerably in entropy - the program properly structured into classes and procedures having the lowest entropy. The optimal number of procedures and classes is derived. This complexity measure can easily be built into any compiler.
-
Thoresen, Kari Trædal & Maus, Arne (1979). Technological unemployment and working conditions in the comuterized office - two problem areas for trade unions.
-
Maus, Arne (1978). Interlude on Signals and Semaphores Revisited. Communications of the ACM.
ISSN 0001-0782.
21(7), s 592- 592
-
Krogdahl, Bjørn & Maus, Arne (1978). Offentlige etaters anskaffelse av EDB-systemer.
Se alle arbeider i Cristin
Publisert 4. nov. 2010 14:08
- Sist endret 22. mai 2019 11:54