-5

我正在尝试在 Haskell 中进行 CycleSort，这是我的任务，但没有人让我清楚如何使用 Haskell，我尝试了很多次，尝试从其他语言“翻译”代码，但没有奏效. 我到处寻找它，但什么也没有。如果有人帮助我解决这些问题，我将非常非常感激。Java中有CycleSort的代码。

// Function sort the array using Cycle sort
public static void cycleSort(int arr[], int n)
{
    // count number of memory writes
    int writes = 0;

    // traverse array elements and put it to on
    // the right place
    for (int cycle_start = 0; cycle_start <= n - 2; cycle_start++) {
        // initialize item as starting point
        int item = arr[cycle_start];

        // Find position where we put the item. We basically
        // count all smaller elements on right side of item.
        int pos = cycle_start;
        for (int i = cycle_start + 1; i < n; i++)
            if (arr[i] < item)
                pos++;

        // If item is already in correct position
        if (pos == cycle_start)
            continue;

        // ignore all duplicate elements
        while (item == arr[pos])
            pos += 1;

        // put the item to it's right position
        if (pos != cycle_start) {
            int temp = item;
            item = arr[pos];
            arr[pos] = temp;
            writes++;
        }

        // Rotate rest of the cycle
        while (pos != cycle_start) {
            pos = cycle_start;

            // Find position where we put the element
            for (int i = cycle_start + 1; i < n; i++)
                if (arr[i] < item)
                    pos += 1;

            // ignore all duplicate elements
            while (item == arr[pos])
                pos += 1;

            // put the item to it's right position
            if (item != arr[pos]) {
                int temp = item;
                item = arr[pos];
                arr[pos] = temp;
                writes++;
            }
        }
    }
}
4

1 回答 1

4

与其试图翻译，不如让我们去维基百科的定义：

算法

给定一个元素a，我们可以通过简单地计算整个列表中小于a的元素的数量来找到它在排序列表中出现的索引。现在

  1. 如果元素已经在正确的位置，什么也不做。
  2. 如果不是，我们会将其写入其预期位置。该位置由不同的元素 b 占据，然后我们必须将其移动到正确的位置。这个将元素移动到正确位置的过程一直持续到元素移动到 a 的原始位置为止。这样就完成了一个循环。

对每个元素重复此过程对列表进行排序，当且仅当元素尚未位于其正确位置时，才使用单个写入操作。虽然计算每个元素的正确位置需要 O(n) 时间，从而产生二次时间算法，但写入操作的数量被最小化。

执行

要从上述大纲创建一个工作实现，需要解决两个问题：

  1. 在计算正确位置时，我们必须确保不要重复计算循环的第一个元素。
  2. 如果存在重复元素，我们可以尝试将元素 a 移动到其正确位置，该位置恰好被 a 占据。简单地交换这些将导致算法无限循环。相反，我们必须在其任何重复项之后插入该元素。

在haskell中实现cycleSort，我们的第一个问题应该是类型应该是什么cycleSort？

normal sort 有 type sort :: Ord a => [a] -> [a]，但这不适用于cycleSort. 循环排序是一种就地算法，因此对列表进行排序没有意义。相反，我们想要对一个可变向量进行排序。

cycleSort :: Ord a => MVector s a -> MVector s a

不过这种类型不太对劲。对MVectors 的操作不是纯粹的——它们在某些 monad 中返回操作，通常是ST sor IO。所以这种类型需要稍微调整一下。

我们将返回一个在执行时对可变向量进行排序的操作，而不是返回一个排序的向量：

cycleSort :: (PrimMonad m, Ord a) => MVector (PrimState m) a -> m ()

（PrimMonad m只是意味着m可以构造改变向量的动作， PrimState m用于将 绑定MVector到这个特定的 monad）。

为了与其他实现进行比较，我们可能想要计算写入次数：

cycleSort :: (PrimMonad m, Ord a) => MVector (PrimState m) a -> m Int

所以现在我们可以研究算法本身了。

由于这是一项作业，我不会为您提供解决方案，但这里有一些有用的功能：

  • Data.Vector.Mutable.length :: MVector s a -> Int获取可变向量的长度
  • Data.Vector.Mutable.read :: PrimMonad m => MVector (PrimState m) a -> Int -> m a读取可变向量中索引处的值
  • Data.Vector.Mutable.write :: PrimMonad m => MVector (PrimState m) a -> Int -> a -> m ()在可变向量中的索引处写入值

作为一个使用示例，这是一个反转 MVector 的函数：

import Control.Monad (when)
import Control.Monad.Primitive (PrimMonad, PrimState)
import qualified Data.Vector.Mutable as MV

reverseMVector :: PrimMonad m => MV.MVector (PrimState m) a -> m ()
reverseMVector v = loop 0 (MV.length v - 1) where
  loop lo hi = when (lo < hi) $ do
    a <- MV.read v lo
    b <- MV.read v hi
    MV.write v lo b
    MV.write v hi a
    loop (lo+1) (hi-1)

有许多先进的技术可以使解决方案更漂亮，但递归函数（loop如上）就足够了。

例如，可以翻译

// ignore all duplicate elements
while (item == arr[pos])
    pos += 1;

作为

-- ignore all duplicate elements
let skipDupes pos = do
      jtem <- MV.read v pos
      if item == jtem
        then skipDupes (pos + 1)
        else return pos
pos <- skipDupes pos

如果您想在各种输入上测试您的代码，请使用 Data.Vector.thaw/将 aData.Vector.freeze转换Vector a为 MVector s a.

当您遇到问题时，请发布您目前拥有的代码以及您遇到的错误。

于 2018-05-09T04:12:09.520 回答