Title

Inversions in k-sorted permutations

Keywords

Insertion sort; Inversions; k-ordered; k-sorted; Permutations

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. © 1998 Elsevier Science B.V. All rights reserved.

Publication Date

10-5-1998

Publication Title

Discrete Applied Mathematics

Volume

87

Issue

1-3

Number of Pages

49-56

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/S0166-218X(98)00099-7

Socpus ID

0041720979 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0041720979

This document is currently not available here.

Share

COinS