Figure 2. Schematic overview of natural sort algorithm

Natural Sort Option in Sort Dialog

OpenOffice.org 2.0+

Document - ID	Specification Owner	Last Change	Status
	Kohei Yoshida	2005-06-21	Draft
Conforms to	
Applies to	Calc
Task ID(s)	i26565
Category	Feature

Abstract

A new sort algorithm known as the "natural sort" will be added to the cell sort options to provide users an option of sorting string-prefixed numbers in the "natural" way i.e. A1, A2, A3, ... , A19, A20 instead of the current behavior of A1, A10, A11, A12, ... ,A19, A2, A20, A3, A4, ... , A8, A9.

i-Team Members (The specification owner is part of the i-Team)

	Name	E-mail Address
User Experience	<Name + Initials>	
Development	Kohei Yoshida (KY)	kohei@openoffice.org
Quality Assurance		
Documentation		

Approved for Implementation

	Approved by	Date
User Experience	<Name>	<Date>
Development		
Quality Assurance		
Documentation		
String Review		

Document Change History

Rev. Level	Change	Initials	Date
1.0	Initial draft	KY	2004-03-14
1.1	- Modified text in the Technical Dependencies section to fix some technical inaccuracies. - Fixed the dialog screenshot (Figure 1) to include the "Data area" display.	KY	2004-04-23
1.2	- Fixed the dialog screenshot (Figure 1) to remove the "Data area" display, and documented its removal.	KY	2004-05-01
1.3	- Added some note regarding a treatment of a context-dependent decimal separator. - Added future tasks (whole number v.s. Real number, Japanese numeral characters, and in-place switching of locales).	KY	2005-06-21

Contents

Glossary	1

1	Motivation	1

2	User Scenarios	1

2.1	Scenario 1:	1

2.2	Scenario 2:	1

3	Goals	1

4	Requirements and Dependencies	1

4.1	Requirements	1

4.2	Technical Dependencies	2

5	Competitive Analyses	2

6	Detailed Specification	2

6.1	G11n	4

6.2	Error Conditions	4

6.3	Migration	4

7	Future Tasks	4

8	Notes	4

9	References	5

Glossary

Term	Description
normal string comparison	existing string comparison algorithm provided by i18npool module.

Motivation

When cells containing string-prefixed numbers (e.g. A34) are sorted using the current sort function found under Tool - Sort, the result is often not what one would normally expect because the cell contents are compared as strings despite the presence of the numeric component. For instance, when cells containing a series of A1, A2, A3, ... ,A19, A20 are sorted using the regular sorting algorithm, the result will be A1, A10, A11, ... ,A19, A2, A20, A3, A4, ..., A8, A9. This is because the numeric part of a string is evaluated digit by digit, which inadvertently declares A2 to be greater than A19, A3 greater than A20, and so on. This is simply not the natural human way of doing the sort; therefore the natural sorting algorithm needs to be introduced to solve this problem.

User Scenarios

Scenario 1:

A user wants to sort a table consisting of product records stored in rows by the part number. Each part number consists of the prefix manufacturer code, and the middle numeric product code of varying digits, and the product version code suffixed to the end, and looks like "MKG-234049AH". The user wishes to have the records sorted correctly in ascending order by the prefix string part ("MKG-") first, then by the numeric part ("234049") and then the remaining part of the string ("AH").

Scenario 2:

A user, who is a geo-scientist, maintains a series of ground water observation wells to monitor the quality of ground water. The wells are numbered sequentially from MW-1 through MW-30. His table contains information about these wells, and he wants to present the table sorted correctly from the top down by the well number.

Goals

The goal of this proposed feature is to provide a user with an option of sorting string-prefixed numbers in the way that naturally makes sense. Since this feature is not yet provided in the competitor product, this will give OO.o a competitive advantage over that other spreadsheet program that we all know of.

Requirements and Dependencies

Requirements

This feature does not have any external requirements.

Technical Dependencies

As this proposed feature consists of string comparison and numeric comparison parts the former of which will be simply passed onto the existing string comparison mechanism, it must take into account the case (in)sensitivity and/or a presence or absence of custom sort order when those string comparisons are performed.

In addition, the state of the corresponding check box for this "natural sort" algorithm needs to be remembered for subsequent operations in the same manner the states of the other check box options in the sort option tab are remembered. It will revert back to its default value in the manner consistent with the other options in the dialog.

Since using this algorithm will involve extra computing cycles, the natural sort check box is off by default to avoid performance loss, but this is subject to discussion.

Competitive Analyses

Not applicable as this feature is not yet present in the most popular spreadsheet program (not verified with any other spreadsheet programs).

Detailed Specification

A new check box named "Enable natural sort" will be placed below the existing "Include formats" check box as illustrated in Figure 1. When this check box is checked, the applicable string comparison will use the natural sort algorithm instead of the existing text comparison algorithm.

As a result of this, the "Data data" display that was originally placed near the bottom of the tab page will be removed in order to preserve the size of the tab page. The preservation of the tab page size is important because the tab page may be used in another dialog, and altering its size may cause breakage in other parts of the application.

Internally, the new algorithm will be given as a helper function which returns either 1, 0, or -1 depending upon the comparison result of the two given strings. A return value of 1, 0, and -1 indicates the first string is greater, the two strings are equal, and the second string is greater, respectively. The compared strings are to be given as strings of type rtl::OUString.

Figure 1. New sort option dialog (screenshot taken in Fedora Core 1)

The following illustrates how two strings are compared under the natural sort algorithm.

Step 1. First of all, the two strings are compared by using the normal string comparison algorithm to ensure that they are not equal. If they are, the function will return immediately with equality (value of 0).

Step 2. Next, each of the two strings is divided into three parts:

Prefix substring

Numeric substring

Suffix substring

The prefix substring is determined by locating the first occurrence of a digit character; the substring from the very first character through the character preceding the first digit is considered the prefix. Now, if the first digit happens to be the first character of the whole string, the prefix substring becomes empty. If there is no digit in either one of the compared strings, the natural sort process will end and the normal string comparison will be performed instead. The digit determined herein is locale-aware, and therefore is not limited to ASCII digits. A decimal separator may also be considered a digit so that real numbers can also be supported if the appropriate conditions are met (see Section 8.1).

Step 3. After the prefix substring is extracted from both of the compared strings, a normal string comparison is performed on the extracted prefixes. If they differ, the result is returned and the process will end. If they are equal, it will proceed to the next step of numeric string comparison.

Step 4. In this step, the numeric substring is determined by locating the first occurrence of a non-digit character after the first digit character; the substring from the first digit character through the character preceding the first non-digit is considered the numeric substring. This substring is then converted into a double-precision variable. This step is performed on both of the compared strings, and the converted values are compared by simple numeric comparison. If these values differ, then the result will be returned and the process will end. If they are equal to one another, then the process will proceed to the next step.

Step 5. After the numeric comparison returns equality, the suffix substring, which is simply the rest of the string that occurs after the last digit of the numeric substring, will be extracted. This suffix substring will then replace the original string, and the whole process will repeat (i.e. back to Step 1).

This sorting process is illustrated in Figure 2. Note that the term "normal string comparison" repeatedly mentioned in the algorithm description refers to a locale-specific string comparison whose algorithm should be provided by the i18npool module; therefore the term does not refer to a simple ASCII string comparison. This locale setting is either explicitly given by the user via the language option setting in the sort option dialog, or the default locale when the language option is not explicitly specified (current behavior).

G11n

As mentioned in Section 6, the string comparison part of the natural sort algorithm relies on a locale-specific algorithm. But since all locale-specific part is handled by a separate i18n facility, there should be no need to introduce any new locale-handling code into this proposed algorithm.

Error Conditions

Not applicable.

Migration

Not applicable.

Future Tasks

Whole Number v.s. Real Number

In the current implementation, a numeric substring is treated as a real number when a decimal separator is present in the manner described in Section 8.1. However, several users have suggested via personal email as well as via comment in IssueTracker that allowing whole numbers only, thus regarding decimal separators as non-digit characters under any conditions, may provide more practical use. This point should be discussed further after the initial implementation whether or not this suggestion is valid. If it is considered valid, then the algorithm used for natural sorting will need to be modified to only allow whole numbers, or make it a user's choice by introducing an additional boolean parameter in an appropriate location.

Treatment of Japanese Numeral Characters

Figure 3. Typical appearance of half-width Arabic numerals (above) and full-width Arabic numerals (below) at identical font size in Japanese encoding system. In the Japanese character-coding system, users use full-width Arabic numerals quite frequently in lieu of half-width counterparts. The half-width numerals are technically equivalent of digit characters in western language encoding systems and use the same character addresses; therefore, the natural sorting will work as expected if all digit characters used in compared strings are half-width numerals.

In contrast, the full-width Arabic numerals are similar in appearance to the half-width (see Figure 3), but are mapped to different addresses than the half-width ones, and currently they are treated as non-numerals in Calc. As such, the natural sorting will not be applied to the full-width numerals in the current implementation.

However, because of such frequent use of the full-width numerals in spreadsheet documents among Japanese users, it will be highly beneficial to treat them in the same manner as the half-width numerals. The feasibility of this enhancement should therefore be considered for the future implementations, possibly with selective use of the UNO NativeNumberSupplier service.

In-place Switching of Locales

In European countries, documents are frequently exchanged between locales where different decimal separators are used. It is therefore useful to give the user an ability to temporarily switch the locale used in natural sorting without switching the locale for the whole application.

Notes

Treatment of decimal separators

The treatment of a decimal separator is context-dependent, that is, when a decimal separator occurs adjacent to one or two digit characters, it is considered a digit character as long as it's the only occurrence in that given numeric substring. In other words, a second occurrence of a decimal separator in any numeric substring is treated as a non-digit character; therefore the character immediately preceding the separator becomes the last character of the numeric substring, while the separator itself becomes the first character of the suffix substring.

References

<Give references to related documentation, such as engineering designs, technical specs, and other sources for related units. Also include links to documents that other sections in this spec need to refer to, such as user opinions usability test reports.>

Natural Sort Option in Sort Dialog

Page 5

http://specs.openoffice.org/calc/ease-of-use/natural_sort_algorithm.sxw

Natural Sort Option in Sort Dialog

Kohei Yoshida

2004-03-02T13:28:04