Shulou(Shulou.com)05/31 Report--

This article mainly explains "what kind of REPLACEMENT SELECTION SORT is used in PostgreSQL". Friends who are interested may wish to have a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "what is the use of REPLACEMENT SELECTION SORT in PostgreSQL?"

REPLACEMENT SELECTION SORT, suitable for situations with small memory (in the era when Gartner proposed the algorithm, memory was N orders of magnitude less than it is now).

The algorithm is in use in PG 9.x or below, but has been abandoned in higher versions. The algorithm is implemented as follows:

Let mbe the number of records to be sorted which can be kept in the main memory. Imagine that these memory locations are registers and assume we can mark them as "on" or "off". Replacement selection can overlap reading, sorting and writing.

Step1: The m registers are filled with records from the input to be sorted.Step2: All registers are put into the "on" state.Step3: Select the register which has the smallest of all "on" registers.Step4: Transfer the contents of the selected register to the output (call it as key Y). Step5: Replace the contents of the selected register by the next input record If new record key > Y Go to step 3 If new record key = = Y Go to step 4 If new record key < Y Go to step 6Step6: Turn the selected key register "off". If all registers are now "off" We have completed a sorted substring (run). We start a new substring group and go to step 2. Else Go to step 3

Here is an example of the algorithm:

Example: Suppose number of registers is 3 and input keys are 5, 2, 9, 7, 0, 8, 1, 6, 3, 4... Registers Output 5 2 9 2 5 7 9 5 0 7 7 7 0 8 9 8 * 0 1 9 9 0 0 1 60 1 6 03 1 6 13 4 6 3-4 64-- 66

Related data structures: two arrays, one to store the actual data read, one to mark the array, and one external memory to store a sorted run.

If the tag array is all F (inactive), a run is generated over and over again until all inputs are exhausted.

With this method, N runs can be generated (each run corresponds to some of the sorted data).

CS 351-Data Organization and Management (Section: 02)

External_sorting

Replacement-selection-sort vs selection-sort

At this point, I believe that you have a deeper understanding of "the use of REPLACEMENT SELECTION SORT in PostgreSQL and what kind of situation". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.