Inversions in k-sorted permutations

    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