algorithm - 外部quicksort算法讲解

Question

我正在尝试了解快速排序的外部版本(当数据无法装入主内存时)。我找到了 following link和关于 Wiki 的类似解释外部快速排序过程:

Definition: Read the M/2 first and last elements into a buffer (the buffer acts like the pivot in quicksort), and sort them. Read the next element from the beginning or end to balance writing. If the next element is less than the least of the buffer, write it to available space at the beginning. If greater than the greatest, write it to the end. Otherwise write the greatest or least of the buffer, and put the next element in the buffer. Keep the maximum lower and minimum upper keys written to avoid resorting middle elements that are in order. When done, write the buffer. Recursively sort the smaller partition, and loop to sort the remaining partition.

我理解有问题:

• M是指主存的大小吗？我在某个驱动器上还有剩余的 N-M 元素？

• 缓冲区就像快速排序中的枢轴 - 这是否意味着我需要将驱动器中剩余的 N-M 元素分成两部分 a 和 b，其中 a 中的元素低于缓冲区中的所有元素，而 b 中的元素大于或等于最大值来自缓冲区的元素？

• 从开头或结尾读取下一个元素以平衡书写。 平衡书写 是什么意思？应该从缓冲区(内存)还是从驱动器读取下一个元素？

• 否则写入最大或最少的缓冲区，并将下一个元素放入缓冲区 - 如果我将下一个元素放入缓冲区(已经排序)，我需要再次对缓冲区进行排序吗？

一些示例如何工作或更好的解释将非常有用。

Answer 1

注意 - 我不知道有任何库使用快速排序进行外部排序，所以这主要是一种教育练习。

维基文章提到了磁带，但这是错误的。不可能在合理的时间内从磁带上的数据“两端”读取数据，并且不可能在不破坏数据之后的现有数据的情况下覆盖磁带上的数据。因此，请将其视为硬盘驱动器或 SSD 类型设备上文件的外部排序，具有随机访问和就地覆盖数据的能力。

Is M refering to the size of main memory?

根据上下文，工作内存区域的大小为M·sizeof(element)。需要有额外的可用内存才能在不覆盖缓冲区的情况下读取元素。

'N-M` elements on some drive?

是的，因为内存只能容纳M个元素，所以N-M个元素留在外接设备上。

The buffer acts like the pivot in quicksort?

缓冲区被排序为单次运行，缓冲区中的最小值和最大值加上刚刚读取的一个元素作为一个枢轴值范围，以确定写入哪个元素。

Read the next element from the beginning or end to balance writing.` What does it mean to balance writing? Should next element be read from the buffer (memory) or from the drive?

在文件的开头或结尾有可以写入M/2个元素的空间。可以从任一端读取第一个元素读取。如果从头读取一个元素+M/2。然后缓冲区中最小的元素从头开始写入，仍然为要写入的元素留出 M/2 空间。如果从末尾读取元素 - M/2，则将最大元素写入文件中的最后一个元素，并在末尾留出 M/2 空间用于写入元素。

此时算法有问题。每读取一个元素，都需要合并到M个元素的缓冲区中，非常慢。此问题的一种解决方案是为缓冲区使用最小-最大堆。

https://en.wikipedia.org/wiki/Min-max_heap

最终，文件从两端开始写入，在中间 M 元素处相遇，然后写入 M 元素缓冲区。此时，文件开头的所有元素都小于或等于文件结尾的所有元素，文件可以认为是2个分区。然后对每个分区进行分区，产生 4 个分区，然后是 8 个分区，依此类推，直到最终一个分区适合内存并使用正常的内存排序。

所描述的算法很慢，因为它一次读取和写入一个元素。预留一部分内存来缓冲分组读写会快很多。