快速排序不按预期使用链接列表

Question

前言：

我不关心我的快速排序算法的可行性。这不是问题所在。我很好奇为什么我已经写好的程序的行为方式，而不是为什么我应该使用STL或其他什么。这是为了学习。(例如，我知道选择枢轴不是最好的情况-这不是我要问的)

问题：

我有一个由Node*组成的链表，我专门为它编写了一个快速排序算法。它的工作方式是获取给定的链表，并根据所选的pivot递归地将其拆分为子列表。支点始终是列表的head (前端)，子列表left和right分别包含小于或等于枢轴的值。我几乎把它弄下来了，但我不知道如何正确地add_link枢轴。在上一次迭代中，我只需要始终将枢轴转到右边的子列表，但这会导致无限循环，因此，当比较值与之比较时，我最终完全跳过了add_link。结果列表是排序的，但是它丢失了每个用于支点的值。我该怎么解决这个问题？

下面是一个最小的可重现性示例：

#include <iostream>
struct Link {
    Link(int d=int(), Link* n=nullptr) {
        data = d;
        next = n;
    }
    int         data;
    Link* next;
};

struct LinkList {
  Link* sentinel;
  size_t      size;

 LinkList(Link* h=new Link, size_t s=0) {
    size = s;
    sentinel = h;
  }

  ~LinkList() {
    Link* current = sentinel;
    while (current != 0) {
      Link* next = current->next;
      delete current;
      current = next;
    }
    sentinel = 0;
  }
};

// Prototypes

Link* sort_q(Link* sentinel);
void  divide(Link* sentinel, Link* cmp, Link*& lower, Link*& greater);
Link* concatenate(Link* lower, Link* greater);

// helpful function calls quick sort
void sort(LinkList& l) {
    l.sentinel = sort_q(l.sentinel);
}


// returns false if there sentinel = null; true if add_link was successful
bool add_link(Link* sentinel, Link* add_link, Link*& end) {
    if (sentinel == nullptr) {
        return false;
    }
    Link* curr = sentinel;
    for (; curr->next; curr = curr->next) {}
    curr->next = add_link;
    end = curr->next;
    return true;
}

Link* sort_q(Link* sentinel) {

    Link* lower = nullptr;
    Link* greater = nullptr;
    Link* cmp = sentinel;

  // base case LinkList = null or sentinel->null
    if (sentinel == nullptr || sentinel->next == nullptr) {
        return sentinel;
    }

    divide(sentinel, cmp, lower, greater);

    lower = sort_q(lower);

    greater = sort_q(greater);

    return concatenate(lower, greater);
}

void divide(Link* sentinel, Link* cmp, Link*& lower, Link*& greater) {
    lower = new Link, greater = new Link;
  // lend is pointer to end of lower subLinkList
  // rend is pointer to end of greater subLinkList
    Link* lend = nullptr, * rend = nullptr;

  // loop through LinkList until end
    while (sentinel != nullptr) {
        if (sentinel == cmp) {
            sentinel = sentinel->next; continue;
        }
        if (sentinel->data < cmp->data) {
            // break current link
            Link* tmp = sentinel;
            sentinel = sentinel->next;
            tmp->next = nullptr;
      // if subLinkList is not empty, add_link current Link to subLinkList and update end pointer
            if (add_link(lend, tmp, lend))
                continue;
        // otherwise, "add_link" current Link to empty subLinkList and update end pointer manually
            lower->next = tmp;
            lend = lower->next;
        }
        else {
            // break current link
            Link* tmp = sentinel;
            sentinel = sentinel->next;
            tmp->next = nullptr;
            // if subLinkList is not empty, add_link current Link to subLinkList and update end pointer
            if (add_link(rend, tmp, rend))
                continue;
            // otherwise, "add_link" current Link to empty subLinkList and update end pointer manually
            greater->next = tmp;
            rend = greater->next;
        }
    }
    // remove dummy Link(s)
    if (lower->next)
        lower = lower->next;
    else
        lower = cmp;
    if (greater->next)
        greater = greater->next;
    else
        greater = cmp;
    // unlink cmp
    cmp->next = nullptr;
}

// connected subLinkLists
Link* concatenate(Link* lower, Link* greater) {
    Link* sentinel;

    sentinel = lower;

    while (lower->next != nullptr) {
        lower = lower->next;
    }

    lower->next = greater;

    return sentinel;
}

void print(LinkList &l) {
  for (Link* n = l.sentinel; n != NULL; n = n->next) {
    std::cout << n->data << '\n';
  }
}

int main() {
  // set up linked LinkList 8->4->5->11->7->5->3->9->null
  Link* sentinel = new Link(8 , new Link(4, new Link(5, new Link(11, new Link(7, new Link(5, new Link(3, new Link(9))))))));
  LinkList l(sentinel,5);

  sort(l);
  print(l);

  return 0;
}

我想要的输出是

3
4 // pivot missing from output
5
5
7
8 // pivot missing from output
9
11

但它的输出

3
5
5
7
9
11

编辑#1：

我尝试过在连接之间添加支点，但这也不起作用。它产生不同的结果，但并不完全相同。修改sort_q()和partition()如下：

Link* qsort(Link* sentinel) {
   // ... other stuff before modification
   return concatenate(lower, cmp); // changed greater argument to pass cmp which is now cmp->next = greater once finishing partition()
}

void partition(Link* sentinel, Link*& cmp, Link*& lower, Link*& greater) {
    // .. other stuff before modifications

    // remove dummy Link
    if (lower->next)
        lower = lower->next;

    if (greater->next)
        greater = greater->next;

    cmp->next = greater; // cmp points to greater (greater) sublist
}

输出变成

3
4
5
7
0
8
11
0

Answer 1

你有一个假设，你可以得到一个较低的和更大的列表，你已经确保你至少有两个项目在列表中，然后你调用除法，所以这是很好的。

你只需要在分歧结束的时候处理所有的案子。确保cmp在这两个列表中的一个结束。几乎和以前一样，但是您需要处理低列表和大列表都是非空的情况。

// remove dummy node(s)
    cmp->next = nullPtr;
    if (lower->next && greater->next) {
        // we have two lists. put cmp on greater
        lower = lower->next;
        cmp->next = greater->next;
        greater = cmp;
    }
    else if (lower->next) {
        // only a lower list, use cmp on greater
        lower = lower->next;
        greater = cmp;
    }
    else if (greater->next) {
        // only a greater list, use cmp as lower.
        greater = greater->next;
        lower = cmp;
    }

综上所述，处理这三种情况，可以简化为：

// remove dummy node(s)
    if (lower->next) {
        // we have lower node, so put cmp on greater
        lower = lower->next;
        cmp->next = greater->next;
        greater = cmp;
    }
    else if (greater->next) {
        // only a greater list, use cmp as lower.
        greater = greater->next;
        lower = cmp;
        cmp->next = nullPtr;
    }

然后使用concatenate(lower,greater)。虽然可以对divide进行优化，使其连接列表并返回哨兵，但这更像是重写。

编辑:把它放在一起，以消除你的内存泄漏，它应该是这样(注意，我没有编译或测试)

void divide(Node* sentinel, Node* cmp, Node*& lower, Node*& greater) {
    lower = nullptr, greater = nullptr;
  // lend is pointer to end of lower sublist
  // rend is pointer to end of greater sublist
    Node* lend = nullptr, * rend = nullptr;

  // loop through list until end
    while (sentinel != nullptr) {
        if (sentinel == cmp) {
            sentinel = sentinel->next; continue;
        }
        if (sentinel->data < cmp->data) {
            // break current link
            Node* tmp = sentinel;
            sentinel = sentinel->next;
            tmp->next = nullptr;
      // if sublist is not empty, append current node to sublist and update end pointer
            if (append(lend, tmp, lend))
                continue;
        // otherwise, "append" current node to empty sublist and update end pointer manually
            lend = lower = tmp;
        }
        else {
            // break current link
            Node* tmp = sentinel;
            sentinel = sentinel->next;
            tmp->next = nullptr;
            // if sublist is not empty, append current node to sublist and update end pointer
            if (append(rend, tmp, rend))
                continue;
            // otherwise, "append" current node to empty sublist and update end pointer manually
            rend = greater = tmp;
        }
    }
    // insert cmp node
    if (lower) {
        // we have lower node, so put cmp on greater
        cmp->next = greater;
        greater = cmp;
    }
    else if (greater) {
        // only a greater list, use cmp as lower.
        lower = cmp;
        cmp->next = nullptr;
    }
}

Answer 2

我看到的主要问题是，您有时(但不总是)将枢轴添加到partition()中的“左”或“右”列表中。这种不一致性很可能违反了partition()所需的功能。但是，这个功能没有文档化的。因此，我将修改我的评估，说主要的问题是，您没有记录您的功能。您的项目越大，您就越有可能因为缺乏文档而遇到问题。

文档！

我希望看到partition()文档化，它将列表划分为三个部分:左、右和支点。

/// Partitions the list starting at `head` into three pieces. Data less than
/// the given partition's data is put in the `left` list, while the remaining
/// data (except `*partition` itself) is put in the `right` list. The third
/// piece consists of `*partition`, which is assumed to be in the given list.
void partition(Node* head, Node* pivot, Node*& left, Node*& right) {

另一种选择可能是立即将枢轴放在其中一个列表中。但是，这些列表将在调用partition()之后立即排序，并且没有必要将*partition包括在这类列表中。向左排序，向右排序，然后连接左、分区和右。除了由于下一个递归调用中需要排序的节点较少而速度更快之外，将分区节点排除在列表之外还可以保证每次递归调用时列表会变得更短。

不过，这是你的决定，因为你是设计师。重要的是决定您想要的功能，记录它，并遵循这个决定。

强制一致性！

一旦您指定了功能，就更容易验证您的代码是否尊重您所做的任何设计决策。您的sort_q()函数未能考虑上述规范，因为它没有将分区添加到列表中。可能有一种比下面更简单的方法来实现这一点，但是下面的方法只需要很少重写代码就可以达到目的。(这是sort_q()的结束。)

    // ** Return left -> pivot -> right, not just left -> right **
    return concatenate(left, concatenate(pivot, right));
}

此外，您的partition()函数违反了此规范，因为(有时)将分区节点添加到您的列表中。别这么做了。将链接设置为null。

    // remove dummy node(s)
    if (left->next)
        left = left->next;
    else
        left = nullptr;   // <-- null, not pivot
    if (right->next)
        right = right->next;
    else
        right = nullptr;   // <-- null, not pivot

嗯..。我之前没有重写您的代码，但是这个特殊的结构让我觉得不必要的复杂。如果某个指针不是null，则将其赋值给某个对象。否则(当指针为空时)，指定null而不是指针(指针为null，所以是相同的事情)。那是相当冗长的。只需分配指针。

    // remove dummy node(s)
    left = left->next;
    right = right->next;
    // *** Memory leak, as we removed the nodes without deleting them ***

哦，记忆泄漏是一种痛苦。特别是因为你不需要虚拟节点。但是，这就变成了一个单独的问题，所以现在我只想指出，如果您将left和right初始化为nullptr，那么您的代码非常接近于工作。(您的提示是，如果left初始化为nullptr，那么在调用append()时，lend为null当且仅当left为null。)

最后一段:如果您已经跟踪了所有这些，那么您可能在某个时候遇到了一个分段错误。您在concatenate()中缺少一个检查(可能是您开始使用虚拟节点的原因吗？)

// connected sublists
Node* concatenate(Node* left, Node* right) {
    if ( left == nullptr )   // <-- Add this check
        return right;        // <-- It is very easy to concatenate to nothing.
    Node* head = left;

这应该解决眼前的问题。不过还有其他地方需要改进，所以继续努力吧。(您的代码还有其他部分，我称之为“不必要的复杂”，尽管比if语句变得不那么严重--而且不那么明显。)