Inversions in \(k\)-sorted permutations
type: Item
instance of: scholarly article
title: Inversions in \(k\)-sorted permutations
zbMATH Open document ID: 0908.05002
DOI: 10.1016/S0166-218X(98)00099-7
author: Ronald D. Dutton
published in: Discrete Applied Mathematics
publication date: 1999-03-07T00:00:00Z
full work available at URL: dam
review text: From author's 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 \textit{K. A. Berman} and \textit{J. L. Paul} [Fundamentals of sequential and parallel algorithms (1997)] and determine the maximum number of inversions in \(k\)-sorted permutations of size \(n\). This number is approximately \(0.6kn\).
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 68R05
zbMATH DE Number: 1218467
zbMATH Keywords: inversions
zbMATH Keywords: permutations
zbMATH Keywords: insertion sort
zbMATH Keywords: \(k\)-ordered
zbMATH Keywords: \(k\)-sorted
reviewed by: R. Scurr
MaRDI profile type: Publication
cites work: Q5585020
description: scientific article; zbMATH DE number 1218467