System and method for sorting data

• US 20030233340A1
• Filed: 04/22/2003
• Published: 12/18/2003
• Est. Priority Date: 06/18/2002
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sharpe, David C., Flasza, Miroslaw A.
• Application Number:
  US10/421,176
• Publication Number:
  US 20030233340A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 7/24 Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in generalG06F7/36 takes precedence

Abstract

A method for ordering a first and a second character string is disclosed. The method comprises determining which of the two character strings has a lower collating weight according to a first dictionary sort order table with a non-unique collating sequence, and determining which of the two character strings has a lower collating weight according to a second dictionary sort order table with a unique collating sequence.

Claims

1. A method for ordering a first character string and a second character string comprising the steps of:

(a) determining which of the first character string and the second character string has a lower collating weight according to a first dictionary sort order table with a non-unique collating sequence; and

(b) determining which of the first character string and the second character string has a lower collating weight according to a second dictionary sort order table with a unique collating sequence.

2. The method of claim 1, wherein if the collating weight according to the non-unique collating sequence of the first character string is equal to that of the second character string, the first character string and the second character string are in a single equivalence class.

3. The method of claim 2, wherein step (b) is performed only if the first and second character strings are in the single equivalence class.

4. The method of claim 1, wherein determining step (a) comprises:

(a1) comparing a non-unique collating weight according to the first dictionary sort order table of a first character of the first character string to that of a first character of the second character string;

(a2) if the non-unique collating weight of the first character string'"'"'s first character is equal to that of the second character string'"'"'s first character, determining whether the first character string and the second character string are in a single equivalence class;

(a3) if the non-unique collating weight of the first character string'"'"'s first character is less than that of the second character string'"'"'s first character, ordering the first character string before the second character string;

else

(a4) ordering the second character string before the first character string.

5. The method of claim 4, wherein determining step (a2) comprises:

(a2i) determining whether a next character in the first character string exists and whether a next character in the second character string exists;

(a2ii) if the next character of the first character string does not exist, and the next character in the second character exists, ordering the first character string before the second character string;

(a2iii) if the next character of the second character string does not exist, and the next character in the first character exists, ordering the second character string before the first character string;

else

(a2iv) if the next character of the first and second character strings do not exist, designating the first and second character strings in the single equivalence class;

else

(a2v) comparing the non-unique weight for the first character string'"'"'s next character to that of the second character string'"'"'s next character;

(a2vi) if the non-unique weight for the first character string'"'"'s next character is equal to that of the second character string'"'"'s next character, repeating steps (a2i) through (a2vi);

(a2vii) if the non-unique weight for the first character string'"'"'s next character is less than that of the second character string'"'"'s next character, ordering the first character string before the second character string;

else

(a2viii) ordering the second character string before the first character string.

6. The method of claim 3, wherein the determining step (b) comprises:

(b1) comparing a unique collating weight according to the second dictionary sort order table of a first character of the first character string to that of a first character of the second character string;

(b2) if the unique collating weight of the first character string'"'"'s first character is equal to that of the second character string'"'"'s first character, determining whether the first character string and the second character string are equivalents;

(b3) if the unique collating weight of the first character string'"'"'s first character is less than that of the second character string'"'"'s first character, ordering the first character string before the second character string within the single equivalence class;

else

(b4) ordering the second character string before the first character string within the single equivalence class.

7. The method of claim 6, wherein determining step (b2) comprises:

(b2i) determining whether a next character in the first and second character strings exist;

(b2ii) if the next character exists, comparing the unique weight for the first character string'"'"'s next character to that of the second character string'"'"'s next character;

(b2iii) if the unique weight for the first character string'"'"'s next character is equal to that of the second character string'"'"'s next character, repeating steps (b2i) through (b2iii);

(b2iv) if the unique weight for the first character string'"'"'s next character is less than that of the second character string'"'"'s next character, ordering the first character string before the second character string within the single equivalence class;

(b2v) if the unique weight for the second character string'"'"'s next character is less than that of the first character string'"'"'s next character, ordering the second character string before the first character string within the single equivalence class;

else

(b2vi) designating the first and second characters stings as equivalents.

8. The method of claim 1, further comprising the steps of:

(c) receiving the first and second character strings from an invoking module; and

(d) returning results from determining steps (a) and (b) to the invoking module.

9. The method of claim 1, wherein the unique collating sequence is case sensitive.

10. The method of claim 1, wherein the non-unique collating sequence is case insensitive.

18. The computer readable medium of claim 1, further comprising instructions for:

(c) receiving the first and second character strings from an invoking module; and

(d) returning results from determining steps (a) and (b) to the invoking module.

11. A computer readable medium containing programming instructions for ordering a first character string and a second character string comprising instructions for:

(a) determining which of the first character string and the second character string has a lower collating weight according to a first dictionary sort order table with a non-unique collating sequence; and

(b) determining which of the first character string and the second character string has a lower collating weight according to a second dictionary sort order table with a unique collating sequence.

12. The computer readable medium of claim 11, wherein if the collating weight according to the non-unique collating sequence of the first character string is equal to that of the second character string, the first character string and the second character string are in a single equivalence class.

13. The computer readable medium of claim 12, wherein determining instruction (b) is performed only if the first and second character strings are in the single equivalence class.

14. The computer readable medium of claim 11, wherein determining instruction (a) comprises:

(a1) comparing a non-unique collating weight according to the first dictionary sort order table of a first character of the first character string to that of a first character of the second character string;

(a2) if the non-unique collating weight of the first character string'"'"'s first character is equal to that of the second character string'"'"'s first character, determining whether the first character string and the second character string are in a single equivalence class;

(a3) if the non-unique collating weight of the first character string'"'"'s first character is less than that of the second character string'"'"'s first character, ordering the first character string before the second character string;

else

(a4) ordering the second character string before the first character string.

15. The computer readable medium of claim 14, wherein determining instruction (a2) comprises:

(a2i) determining whether a next character in the first character string exists and whether a next character in the second character string exists;

(a2ii) if the next character of the first character string does not exist, and the next character in the second character exists, ordering the first character string before the second character string;

(a2iii) if the next character of the second character string does not exist, and the next character in the first character exists, ordering the second character string before the first character string;

else

(a2iv) if the next character of the first and second character strings do not exist, designating the first and second character strings in the single equivalence class;

else

(a2v) comparing the non-unique weight for the first character string'"'"'s next character to that of the second character string'"'"'s next character;

(a2vi) if the non-unique weight for the first character string'"'"'s next character is equal to that of the second character string'"'"'s next character, repeating instructions (a2i) through (a2vi);

(a2vii) if the non-unique weight for the first character string'"'"'s next character is less than that of the second character string'"'"'s next character, ordering the first character string before the second character string;

else

(a2viii) ordering the second character string before the first character string.

16. The computer readable medium of claim 13, wherein the determining instruction (b) comprises:

(b1) comparing a unique collating weight according to the second dictionary sort order table of a first character of the first character string to that of a first character of the second character string;

(b2) if the unique collating weight of the first character string'"'"'s first character is equal to that of the second character string'"'"'s first character, determining whether the first character string and the second character string are equivalents;

(b3) if the unique collating weight of the first character string'"'"'s first character is less than that of the second character string'"'"'s first character, ordering the first character string before the second character string within the single equivalence class;

else

(b4) ordering the second character string before the first character string within the single equivalence class.

17. The computer readable medium of claim 16, wherein determining instruction (b2) comprises:

(b2i) determining whether a next character in the first and second character strings exist;

(b2ii) if the next character exists, comparing the unique weight for the first character string'"'"'s next character to that of the second character string'"'"'s next character;

(b2iii) if the unique weight for the first character string'"'"'s next character is equal to that of the second character string'"'"'s next character, repeating instructions (b2i) through (b2iii);

(b2iv) if the unique weight for the first character string'"'"'s next character is less than that of the second character string'"'"'s next character, ordering the first character string before the second character string within the single equivalence class;

(b2v) if the unique weight for the second character string'"'"'s next character is less than that of the first character string'"'"'s next character, ordering the second character string before the first character string within the single equivalence class;

else

(b2vi) designating the first and second characters stings as equivalents.

19. The computer readable medium of claim 11, wherein the unique collating sequence is case sensitive.

20. The computer readable medium of claim 11, wherein the non-unique collating sequence is case insensitive.

21. A method for sorting an input data list comprising a plurality of character strings, the method comprising the steps of:

(a) selecting a first character string and a second character string from the plurality of character strings;

(b) comparing the first character string to the second character string according to a first dictionary sort order table with a non-unique collating sequence;

(c) comparing the first character string to the second character string according to a second dictionary sort order table with a unique collating sequence;

(d) selecting a different pair of first and second character strings in accordance with a sorting algorithm;

(e) repeating steps (a) through (d) iteratively;

(f) sorting the character strings into at least one equivalence class based on comparing step (b); and

(g) sorting the character strings within the at least one equivalence class based on comparing step (c).

22. The method of claim 21, wherein comparing step (b) is performed to determine whether the first character string has a lower collating weight than that of the second character string according to the non-unique collating sequence of the first dictionary sort order table, whether the second character string has a lower collating weight than that of the first character string, and whether the collating weight of the first character string is equal to that of the second character string.

23. The method of claim 22, wherein the sorting step (f) comprises:

(f1) grouping the first and second character strings into an equivalence class if the collating weight according to the non-unique collating sequence of the first character string is equal to that of the second character string.

24. The method of claim 21, wherein comparing step (c) is performed to determine whether the first character string has a lower collating weight than the second character string according to the unique collating sequence of the second dictionary sort order table, whether the second character string has a lower collating weight than the first character string, and whether the collating weight according to the unique collating sequence of the first and second character strings are equal.

25. The method of claim 23, wherein step (c) is performed only if the first and second character strings are in the same equivalence class.

26. The method of claims 21, further comprising:

(h) receiving the input data list from a calling program; and

(i) passing the sorted character strings to the calling program as an output data list.

27. The method of claim 21, wherein the unique collating sequence is case sensitive.

28. The method of claim 21, wherein the non-unique collating sequence is case insensitive.

29. A computer readable medium containing program instructions for sorting an input data list comprising a plurality of character strings, comprising the instructions for:

(a) selecting a first character string and a second character string from the plurality of character strings;

(b) comparing the first character string to the second character string according to a first dictionary sort order table with a non-unique collating sequence;

(c) comparing the first character string to the second character string according to a second dictionary sort order table with a unique collating sequence;

(d) selecting a different pair of first and second character strings in accordance with a sorting algorithm;

(e) repeating instructions (a) through (d) iteratively;

(f) sorting the character strings into at least one equivalence class based on comparing instructions (b); and

(g) sorting the character strings within the at least one equivalence class based on comparing instructions.