ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Electronic Resource

Encroaching lists as a measure of presortedness (1988)

Skiena, Steven S.

Springer

BIT 28 (1988), S. 775-784

add to mindlist on the mindlist

Details

ISSN: 1572-9125

Keywords: F.2.2 ; 68R05 ; sorting ; presortedness ; encroaching lists ; melsort ; permutations

Source: Springer Online Journal Archives 1860-2000

Topics: Mathematics

Notes: Abstract Encroaching lists are a generalization of monotone sequences in permutations. Since ordered permutations contain fewer encroaching lists than random ones, the number of such listsm provides a measure of presortedness with advantages over others in the literature. Experimental and analytic results are presented to cast light on the properties of encroaching lists. Also, we describe a new sorting algorithm,melsort, with complexityO(nlogm). Thus it is linear for well ordered sets and reduces to mergesort andO(nlogn) in the worst case.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF01954897

	Location	Call Number	Expected	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit