de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Impressum Kontakt Einloggen

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

#### Desnakification of mesh sorting algorithms

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45478

Sibeyn,  Jop Frederic
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)

MPI-I-94-102.pdf
(beliebiger Volltext), 224KB

##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Sibeyn, J. F.(1994). Desnakification of mesh sorting algorithms (MPI-I-94-102). Saarbrücken: Max-Planck-Institut für Informatik.

Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-B4FC-3
##### Zusammenfassung
In all recent near-optimal sorting algorithms for meshes, the packets are sorted with respect to some snake-like indexing. Such algorithms are useless in many practical applications. In this paper we present deterministic algorithms for sorting with respect to the more natural row-major indexing. For 1-1 sorting on an $n \times n$ mesh, we give an algorithm that runs in $2 \cdot n + o(n)$ steps, with maximal queue size five. It is considerably simpler than earlier algorithms. Another algorithm performs $k$-$k$ sorting in $k \cdot n / 2 + o(k \cdot n)$ steps. Furthermore, we present {\em uni-axial} algorithms for row-major sorting. Uni-axial algorithms have clear practical and theoretical advantages over bi-axial algorithms. We show that 1-1 sorting can be performed in $2\frac{1}{2} \cdot n + o(n)$ steps. Alternatively, this problem is solved in $4\frac{1}{3} \cdot n$ steps for {\em all $n$}. For the practically important values of $n$, this algorithm is much faster than any algorithm with good {\em asymptotical} performance.