Title

Inversions in k-sorted permutations

Authors

Authors

R. D. Dutton

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Discret Appl. Math.

Keywords

inversions; permutations; insertion sort; k-ordered; k-sorted; Mathematics, Applied

Abstract

When a list of size n is nearly sorted, a straight insertion sort algorithm is highly efficient since only a number of comparisons equal to the number of inversions in the original list, plus at most n - 1, is required. We use a definition of nearly sorted, k-sorted, as given in Berman (1997) and determine the maximum number of inversions in k-sorted permutations of size n. This number is approximately 0.6kn. (C) 1998 Elsevier Science B.V. All rights reserved.

Journal Title

Discrete Applied Mathematics

Volume

87

Issue/Number

1-3

Publication Date

1-1-1998

Document Type

Article

Language

English

First Page

49

Last Page

56

WOS Identifier

WOS:000076462200005

ISSN

0166-218X

Share

COinS