排序使用自定义的API - removeAndAppend [英] Sorting using a custom API - removeAndAppend

问题描述

我们将得到一个API -

We are given an API -

removeAndAppend(val)
//Removes val and appends it to the given collection 

我们需要使用此API收集整理...

we need to sort the collection using this API..

我知道我可以做到这一点 -

I know that I can do this by -

for i <- N to 1
    extract max //in O(n) 
    removeAndAppend.. //Consider this O(1)

这是二次..

现在的问题是，我可以做得比这更好的......？

The question is can I do better than this..?

编辑：我们可以收集喜欢做的读操作 - 比较（VAL1，将val2）

We can do READ operations on collection like - compare(val1, val2)

推荐答案

如果不使用额外的数据结构/定空间限制：

在为O（n 2 ）你描述的算法本质上的选择排序。

如果你有机会到某种类型的迭代器（如果没有，怎么回事，你会访问元素集合中？），我相信我们可以做到通过使用自定义的归并排序如下：

If you have access to an iterator of some kind (if not, how else would you access elements in the collection?), I believe one can do better by using a custom merge-sort as follows:

• 元素比较1和2 removeAndAppend 中较小的一个，那么 removeAndAppend 剩下的一个。做相同的元件3和4，5和6，...和元素n-1和n

• Compare element 1 and 2. removeAndAppend the smaller one, then removeAndAppend the remaining one. Do the same for element 3 and 4, 5 and 6, ... and element n-1 and n.

2的元素现在，你已经整理每一个子集合

Now you'll have sorted subcollections of 2 elements each.

合并指数（1,2）和（3,4）。要做到这一点，有2个迭代器从头开始。开始通过增加两倍，。然后继续做使用 removeAndAppend 功能的合并排序如常。做相同的（5,6）和（7,8），（9,10）和（11,12），...和（n-3，N-2）和（n-1，n）的。

Merge indices (1,2) and (3,4). To do this, have 2 iterators starting from the beginning. Start by incrementing the one twice. Then proceed to do a merge-sort as usual using the removeAndAppend function. Do the same for (5,6) and (7,8), (9,10) and (11,12), ... and (n-3,n-2) and (n-1,n).

4个元素现在，你已经整理每一个子集合

Now you'll have sorted subcollections of 4 elements each.

合并尺寸4集类似于上面，然后从8，16，32，等等，直到到达集合的大小。

Merge size 4 collections similar to above, then 8, 16, 32, etc., until you reach the collection size.

整个过程将是这个样子：

The whole process will look something like this:

// setSize is how large sets we're currently merging
for setSize = 1; setSize <= n/2; setSize *= 2
  iterator left = begin
           right = begin
  for pos = 1 to n/(2*setSize)
    // here right and left are both at the beginning
    // even after the previous iteration of the loop,
    //   since we've removed and appended all other elements
    // so we only need to increase right by setSize
    right += setSize

    for i = 1 to 2*setSize
      if (left.value <= right.value)
        removeAndAppend(left)
      else
        removeAndAppend(right)

上面仅仅是一个基本的草案，它可能不是100％正确和不占当集合不是2的幂（这会经常发生）。你必须要小心，在这种情况下，否则你可能会环绕，或还远远不够，并最终有一个部分的分类收集。

The above is just a basic draft, it might not be 100% correct and doesn't account for when the collection isn't a power of 2 (which will happen often). You need to be careful in this case otherwise you might wrap around, or not go far enough and end up with a partially sorted collection.

的复杂性分析应该是几乎等同于常规的合并排序并导致为O（n log n）的运行时间。

The complexity analysis should be almost identical to regular merge-sort and result in an O(n log n) running time.

随着更多的数据结构/没有固定空间限制：

提取所有的元素融入到另一个集合，排序这 0 （使用你选择的排序算法）（N日志N），并遍历有序集合，调用 removeAndAppend 对原收集每个。

Extract all the elements into another collection, sort this in O(n log n) (using a sorting algorithm of your choice) and iterate through the sorted set, calling removeAndAppend on the original collection for each.

如果您不能提取元素，这种方法仍然可以使用其指数，而不是一个集合，做了一个比较，简单地查找适用的元素。然而，这是有效的，你会被索引需要一定时间查找。

If you're not allowed to extract elements, this method can still be used by having a collection of indices instead and, to do a compare, simply look up the applicable elements. However, for this to be efficient, you'll need constant time lookup by index.

这篇关于排序使用自定义的API - removeAndAppend的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！