Topic: Sort_Merge() algorithm? (1 of 7), Read 49 times
Conf: Other, General, etc.
From: Pauli Lindgren
Date: Tuesday, June 09, 2009 05:26 AM

Vedit documentation does not say which algorithm the Sort_Merge() command uses.

The name suggest that it could be Merge Sort. But maybe it only refer to the merging of the blocks?

The important point is whether or not the sorting is stable. That is, does it retain the order of lines that have the same key value. Merge sort is table, but for example Quicksort and Shell Sort are not.

At least in the short tests I made, the order was retained, so maybe the sorting is stable?

--
Pauli

 

Topic: Re: Sort_Merge() algorithm? (2 of 7), Read 42 times
Conf: Other, General, etc.
From: Ted Green
Date: Tuesday, June 09, 2009 10:28 AM

At 05:49 AM 6/9/2009, vtech-other Listmanager wrote:
>From: "Pauli Lindgren"
>
>Vedit documentation does not say which algorithm the Sort_Merge() command uses.
>
>The name suggest that it could be Merge Sort. But maybe it only refer to the merging of the blocks?
>
>The important point is whether or not the sorting is stable. That is, does it retain the order of lines that have the same key value. Merge sort is table, but for example Quicksort and Shell Sort are not.
>
>At least in the short tests I made, the order was retained, so maybe the sorting is stable?

Its been many years since Tom Burt implemented the sorting, which was took 6 months of full-time programming. Tom first read Knuth's entire book on Sorting. It is a combination of sorting smaller blocks and then merging them together. For Gigabyte sized files, there are several levels of merging. I suspect the basic sort is a modified-Quicksort that recognizes sorted sections and keeps them together.

We compared VEDIT's speed to several commercial dedicated sorting programs and determined that our speed was equal to the best in most situations.

Ted.

 

Topic: Re: Sort_Merge() algorithm? (3 of 7), Read 52 times
Conf: Other, General, etc.
From: Pauli Lindgren
Date: Wednesday, June 10, 2009 03:48 AM

On 6/9/2009 10:28:06 AM, Ted Green wrote:
> It is a
> combination of sorting smaller
> blocks and then merging them
> together. For Gigabyte sized
> files, there are several
> levels of merging. I suspect
> the basic sort is a
> modified-Quicksort that
> recognizes sorted sections and
> keeps them together.

If the sorting algorithm is stable, then at least that should be mentioned in the manual. Too bad if you do not know for sure.

The manual does describe how the blocks are combined, but it does not give information about the basic sorting algorithm. It is common in the implementations of Merge Sort to use some other algorithm to sort the smaller blocks. That is how I made my FSORT program some 25 years ago, see
http://koti.mbnet.fi/pkl/dos_sw.htm
At that time I didn't even know that the method of sorting large files by merging smaller sorted blocks was called Merge Sort. Because I used Shell Sort to sort the small blocks, FSORT is not stable.

I would have needed the information in order to add Vedit entry on this Rosetta Code page:
http://www.rosettacode.org/wiki/Sort_stability

--
Pauli

 

Topic: Re: Sort_Merge() algorithm? (4 of 7), Read 52 times
Conf: Other, General, etc.
From: Ted Green
Date: Friday, June 26, 2009 07:27 PM

At 03:51 AM 6/10/2009, vtech-other Listmanager wrote:
>If the sorting algorithm is stable, then at least that should be mentioned in the manual. Too bad if you do not know for sure.

Tom Burt just confirmed that his sorting algorithm was designed to be "stable", and barring any bugs, we can assume that it is. I have also done some tests to confirm that it is "stable" - i.e. records with duplicate keys are kept in the same order as they appear in the original file.

Ted.

 

Topic: Sort_Merge() algorithm? (5 of 7), Read 47 times
Conf: Other, General, etc.
From: Peter Rejto
Date: Tuesday, May 25, 2010 11:35 PM

On 6/9/2009 5:26:38 AM, Pauli Lindgren wrote:
>Vedit documentation does not
>say which algorithm the
>Sort_Merge() command uses.
>
>The name suggest that it could
>be Merge Sort. But maybe it
>only refer to the merging of
>the blocks?
>
>The important point is whether
>or not the sorting is stable.
>That is, does it retain the
>order of lines that have the
>same key value. Merge sort is
>table, but for example
>Quicksort and Shell Sort are
>not.
>
>At least in the short tests I
>made, the order was retained,
>so maybe the sorting is
>stable?
>
>--
>Pauli
>
>


Thanks Pauli,

for raising the Merge Sort issue and for your subsequent research. I do hope that you will have the time to put it on rosetta.


The very fact that you raised the issue allowed me to learn about Merge Sort on Wikipedia. There I learned this is an algorithm to sort a list.


Now I have a very simple question. Can I sort a list in Vedit ? For example, can I sort the numbers, {1,5,3} in Vedit ? In the special case that the list is given as a column, I did succeed with the menu command {Edit, Sort, Sort lines.}. I take in this special case Vedit considered my list as a collection of lines of lenght 1.

In other words my problem is to sort a row, from left to right in Vedit ? A possible work around would be:

Import it into a spreadsheet, take the transpose, export
the transpose. Finally, import the transpose into Vedit and sort it from top to bottom. But then, Excel for example can also sort a row.


Thanks as always,


-peter.

 

Topic: Sort_Merge() algorithm? (6 of 7), Read 47 times
Conf: Other, General, etc.
From: Pauli Lindgren
Date: Sunday, May 30, 2010 08:43 AM

On 5/25/2010 11:35:51 PM, peter rejto wrote:
>
>The very fact that you raised the issue
>allowed me to learn about Merge Sort on
>Wikipedia. There I learned this is an
>algorithm to sort a list.

There is nothing in Merge Sort or any other algorithms that would limit it to specific data type such as list. The term "list" is used in the Wikipedia article just to refer any collection of objects to be sorted, whether it is an array, text file or whatever.

>
>Now I have a very simple question. Can I
>sort a list in Vedit ? For example,
>can I sort the numbers, {1,5,3} in Vedit
>?
>
>In other words my problem is to sort a
>row, from left to right in Vedit ?

To sort a comma separated list (from cursor position to end of file), you could do for example:
#1 = CP
Replace(",", "|N", ALL)
Sort(#1, EOB_pos)
GP(#1)
Replace("|N", ",", ALL)

However, sorting numeric values may need more works, since there is no numeric option in the sort command.

You could always implement the sort algorithm yourself.
There are some examples in Rosetta Code. For example in the Anagrams example, the letters of the word are sorted with insertion sort, see:
http://rosettacode.org/wiki/Anagrams#Vedit_macro_language

--
Pauli

 

Topic: Sort_Merge() algorithm? (7 of 7), Read 49 times
Conf: Other, General, etc.
From: Peter Rejto
Date: Wednesday, June 02, 2010 07:15 PM

On 5/30/2010 8:43:49 AM, Pauli Lindgren wrote:
>On 5/25/2010 11:35:51 PM, peter rejto
>wrote:

>There is nothing in Merge Sort or any
>other algorithms that would limit it to
>specific data type such as list. The
>term "list" is used in the Wikipedia
>article just to refer any collection of
>objects to be sorted, whether it is an
>array, text file or whatever.
>
>>
>>Now I have a very simple question. Can I
>>sort a list in Vedit ? For example,
>>can I sort the numbers, {1,5,3} in Vedit
>>?
>>
>>In other words my problem is to sort a
>>row, from left to right in Vedit ?
>
>To sort a comma separated list (from
>cursor position to end of file), you
>could do for example:

>#1 = CPReplace(",", "|N", ALL)Sort(#1,
>EOB_pos)GP(#1)Replace("|N", ",", ALL)

>However, sorting numeric values may need
>more works, since there is no numeric
>option in the sort command.
>

>Pauli,

Thanks for putting me on the right track. After some, experimentation, I did put the following two lines into my USER_MNU:

Transpose Highlighted Line(Pauli Lindgren)
Goto_Pos( Min(Block_Begin,Block_End) ) Replace_Block(",","|N",BB,BE,ALL)


(Well, the above three lines is only two in my USER_MNU.)
This converts the line into a column. Then, the Vedit Menu Command, {Edit, Sort, Sort lines(keys, options)...}
did the actual sorting.

You also mention additional numerical work. I forgot to tell you that I am mainly interested in the case of my CSV line having positive integer entries. I take the additional work refers to the general case.


I like your idea of replacing the comma by the end of line character very much. In fact, I would like to pursue two generalizations as well. Since I do not have a programming background, I shall try to pursue only the first one. I do hope that somebody wil have an interest in the second one:

1.: According to Chapter 4 of the Vedit User Manual, the
{Edit, Sort, Sort lines(keys, options)...} command uses the SORT_MERGE.VDM macro. Hence, I can edit this menu
command by editing this macro. What do you think would be a good name for this option ?


2.: I have been wondering, ever since Scott Lambert wrote his beautiful arithmetic macros, about importing spreadsheet commands into Vedit. To be sure, I know that Vedit is not a spreadsheet! At the same time, Scott has shown that some special cases of some spreadsheet commands, can be imported.

It seems to me, that you have just shown me, how to import this special case of the transpose command. This special case is general enough for me. Specifically, it allows me to find the sum of the six best quizzes out of eleven quizzes.

Once again, a big thank you.

-peter.