对几乎已排序的数组进行排序(元素错位不超过 k) [英] Sorting an almost sorted array (elements misplaced by no more than k)

问题描述

我最近被问到这个面试问题:

I was asked this interview question recently:

您得到一个几乎已排序的数组，其中每个 N 元素可能会从正确的排序顺序错位不超过 k 个位置.找到一种空间和时间高效的算法来对数组进行排序.

You're given an array that is almost sorted, in that each of the N elements may be misplaced by no more than k positions from the correct sorted order. Find a space-and-time efficient algorithm to sort the array.

我有一个 O(N log k) 解决方案，如下所示.

I have an O(N log k) solution as follows.

让我们表示 arr[0..n) 表示从索引 0(含)到 N(不含)的数组元素).

Let's denote arr[0..n) to mean the elements of the array from index 0 (inclusive) to N (exclusive).

• 排序 arr[0..2k)
  • 现在我们知道 arr[0..k) 处于它们最终的排序位置...
  • ...但是 arr[k..2k) 仍然可能被 k 错位！
  • Sort arr[0..2k)
    • Now we know that arr[0..k) are in their final sorted positions...
    • ...but arr[k..2k) may still be misplaced by k!
    • 现在我们知道 arr[k..2k) 处于它们最终的排序位置...
    • ...但是 arr[2k..3k) 仍然可能被 k
    错位
    • Now we know that arr[k..2k) are in their final sorted positions...
    • ...but arr[2k..3k) may still be misplaced by k
    • 当您剩余的元素少于 2k 时，这最后一步可能比其他步骤便宜
    • This final step may be cheaper than the other steps when you have less than 2k elements left

    在每一步中，您最多对 O(k log k) 中的 2k 个元素进行排序，至少将 k 个元素放入它们的最后在每一步结束时对位置进行排序.有O(N/k)步，所以整体复杂度是O(N log k).

    In each step, you sort at most 2k elements in O(k log k), putting at least k elements in their final sorted positions at the end of each step. There are O(N/k) steps, so the overall complexity is O(N log k).

    我的问题是:

    • O(N log k) 是最优的吗?这可以改进吗?
    • 你能在不(部分)重新排序相同元素的情况下做到这一点吗?
    • Is O(N log k) optimal? Can this be improved upon?
    • Can you do this without (partially) re-sorting the same elements?

    推荐答案

    As Bob Sedgewick在他的论文(和后续)中表明，插入排序绝对粉碎几乎排序的数组".在这种情况下，您的渐近线看起来不错，但如果 k <;12 我打赌插入排序每次都会赢.我不知道对于为什么插入排序效果这么好有一个很好的解释，但是可以在 Sedgewick 的一本名为 Algorithms 的教科书中查看(他已经完成了不同语言的许多版本).

    As Bob Sedgewick showed in his dissertation work (and follow-ons), insertion sort absolutely crushes the "almost-sorted array". In this case your asymptotics look good but if k < 12 I bet insertion sort wins every time. I don't know that there's a good explanation for why insertion sort does so well, but the place to look would be in one of Sedgewick's textbooks entitled Algorithms (he has done many editions for different languages).

    • 我不知道 O(N log k) 是否最优，但更重要的是，我并不在乎—如果 k 小，重要的是常数因素，如果 k 大，你也可以对数组进行排序.

    • I have no idea whether O(N log k) is optimal, but more to the point, I don't really care—if k is small, it's the constant factors that matter, and if k is large, you may as well just sort the array.

    插入排序可以解决这个问题，而无需重新排序相同的元素.

    Insertion sort will nail this problem without re-sorting the same elements.

    Big-O 表示法非常适合算法类，但在现实世界中，常量很重要.很容易忽视这一点.(我是作为教授 Big-O 符号的教授这么说的！)

    Big-O notation is all very well for algorithm class, but in the real world, constants matter. It's all too easy to lose sight of this. (And I say this as a professor who has taught Big-O notation!)

    这篇关于对几乎已排序的数组进行排序(元素错位不超过 k)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！