Apparatus and method for sorting a list of items

• US 5,218,700 A
• Filed: 01/30/1990
• Issued: 06/08/1993
• Est. Priority Date: 01/30/1990
• Status: Expired due to Fees

• Current Assignee: Allen Beechick
• Original Assignee: Allen Beechick
• Inventors: Beechick, Allen
• Primary Examiner(s): Heckler, Thomas M.
• Assistant Examiner(s): Butler, Dennis M.
• Application Number:
  US07/472,303
• Time in Patent Office: 1,225 Days
• Field of Search: 364/200, 364/900, 395/700
• US Class Current: 712/300
• 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

Method and apparatus for sorting a stream of data such as a numerical or alphabetical list by stratifying vis-a-vis a hierarchal system thereby providing a list of items. This method begins with an unsorted list. For example, if a field of data is to be alphabetized, it groups words letter by letter, and it ends up with a sorted list. The sorting begins by grouping words according to their first letter. All words that begin with the same letter end up in the same group. The first group typically contains all words that begin with "A" if words are sorted or "1" if numbers are sorted. This method then takes the first group and re-groups it according to the second letter. The first group is thereby subdivided into smaller groups. Re-grouping continues in this fashion until the first group contains only one item. That one item is now sorted and it becomes the first item in the new sorted list. Re-grouping continues group by group and letter by letter until the entire list is sorted. Computer use is kept minimal by accounting for the location of unsorted, sorted or partially sorted items and elements comprising respectively (for example) a word and a letter in the word. By accounting using a location with directions to another location reflecting subsequent items to be sorted less memory is used than by traditional techniques and less time is required for sorting.

Claims

1. In a radix sorting method for computing equipment, in which words are sorted by association with their individual characters, said characters in said words consisting of any computer recognizable character including alphabetic letters, numbers, or other character represented by the American Standard Code for Information Interchange, the steps comprising:

assigning each said word a numerical value in order of appearance on a list, so that the first word or number has the value of 1, the second word has the value of 2, and so on;

storing in memory said numerical values that belong to each said word such that individual words can be individually remembered and recalled during the sorting process;

assigning a lettertracker array in the computers memory, said lettertracker being indexed in two dimensions, one dimension corresponding to the position of a letter in a word, the other index corresponding to a value of a letter on a value chart such as the American Standard Code for Information Interchange, and using said lettertracker to keep track of individual letters by which words are being sorted during the sorting process comprising the step of;

(a) using said lettertracker to hold in memory said numerical values of words in such a way that the indexes of said lettertracker point to a specific letter and to the position of that letter within a word, and that said numerical value stored at those indexes corresponds to the appearance location of said word on the list, providing a way to easily recall said word for further processing;

assigning a wordtracker array in the computers memory, said wordtracker being indexed in one dimension, and using said wordtracker to hold in memory said numerical values of words in such a way that groups of words are linked together because the numerical value of a word at one index equals the index at which the numerical value of the next word is stored, the radix sorting method further comprising the steps of;

recalling a first word in a group of words, for the purpose of further sorting that group of words, by matching said numerical value in said lettertracker to the index of said wordtracker;

using the numerical value of the first word in said group of words to recall from memory the rest of the words in said group of words, each said numerical value of a word corresponding to an index of said wordtracker, at which index the numerical value of another word is stored, which corresponds to the next index, and so on, until all words in said group of words are recalled;

changing the values in said wordtracker and said lettertracker as said words are recalled, with the result that said group of words is subdivided into smaller groups, the words in each smaller group being linked together by the indexes and newly changed numerical values in said lettertracker and said wordtracker;

repeatedly subdividing said groups of words into smaller groups, by changing the numerical values stored in said lettertracker and said wordtracker, until only one word remains in each group, with the result that all said words are alphabetically sorted.

2. In a radix sorting method for computing equipment, in which words are sorted by association with their individual characters, said characters in said words consisting of any computer recognizable character including alphabetic letters, numbers, or other character represented by the American Standard Code for Information Interchange, the steps comprising:

(a) assigning a wordtracker array equal in length to a list of words being sorted, said wordtracker array being a single-dimensional array of integers in a computers memory, each memory location in said wordtracker being identified, or located in memory, by its index, with the result that each memory location in wordtracker is identified by one index, and each memory location itself holds one integer;

(b) assigning a letter tracker array equal in length to the number of characters in the longest word in the list, and equal in width to the range of values of the characters being sorted, such as 0 through 9 for numerical sorting or 0 through 255 for the full range of computer recognizable characters, said lettertracker array being a two dimensional array of integers in a computers memory, one dimension corresponding to the position of a particular character in a word, counting the first character as being in the first position, the second character as being in the second position, and so on, and the other dimension corresponding to the ASCII values of characters, ranging in count from 0 through 255, with the result that each memory location in said lettertracker is identified, or located in memory, by its two indexes, one index corresponding to the position of a character in a word and the other index corresponding to the ASCII value of that same character, and the memory location itself holds one integer;

(c) initializing all memory locations in said wordtracker and said lettertracker to zero, so that the integer zero is stored in all memory locations of both arrays before sorting begins;

(d) the steps of storing different integers in said wordtracker and said lettertracker, changing the integer in one memory location at a time, as sorting proceeds, according to the following steps;

(1) after a character of a word is examined, as is the manner of radix sorting, locating the particular memory location in lettertracker that corresponds to the letter just examined,so that one index of lettertracker corresponds to the position of the character in the word, and the other index corresponds to the ASCII value of that same character, and once located, the integer held at that location is put into a certain memory location in wordtracker in the following manner;

(2) wordtracker receives the integer just located in lettertracker and stores that same integer in its next memory location, said next memory location is determined in one of two ways;

(i) during the first sorting pass, in which the first character of each word is being examined, as in the manner of radix sorting, the next memory location of wordtracker is found by the sequential counting of its index, so that the first memory location is used for processing the first word, the second memory location is used for processing the second word, and so on;

(ii) during subsequent sorting passes, in which the second or following characters of each word is being examined, as is the manner of radix sorting, the next memory location used in wordtracker is not necessarily sequential, but rather is located either by the integer held in the previously accessed location of lettertracker when the word being processed is the first in a group of words, or by the integer held in the previously accessed location of wordtracker when the word being processed is the second or following word in a group of words, such that said integer previously accessed (whether from wordtracker or from lettertracker) corresponds to an index of wordtracker, said index being wordtrackers said next memory location, so that if the integer previously accessed were 10, then the next memory location used in wordtracker would be 10, in a like manner, the integer held in the newly located memory position in wordtracker, before said integer is replaced, will locate the next memory location in wordtracker where the next integer is to be stored;

(3) after wordtracker receives said integer from lettertracker, then lettertracker receives a new integer which is stored in the identical memory location previously located in lettertracker, replacing the integer that was formerly held there, said new integer corresponding to the memory location, or index, of wordtracker most recently located, so that lettertracker remembers the last accessed location of wordtracker.

3. The method of claim 2, whereby the storing of integers in one location at a time in wordtracker and lettertracker has the following functions and results:

(1) if an integer in wordtracker is greater than zero, the that integer corresponds to the next memory location to be located in wordtracker, such that the integer 10 in any memory location of wordtracker points to the 10th memory location of wordtracker and to whatever integer may be stored in that location;

(2) any non-zero integer in wordtracker also identifies a particular word in the list being sorted, such that the integer 10 corresponds to the tenth word in the list, and so on, so that wordtracker acts as a linking mechanism, linking words together in groups, because the integer in one location points to another location, and therefore to another word also, so that words can be examined one by one in a particular order;

(3 ) if an integer in wordtracker equals zero, then that signals the end of a current group of words, and so the sorting process continues on a different group of words as follows;

i. if a group of words just finished needs no further subdividing, as is the manner in radix sorting, then the sorted word or words are added to a sorted list, and the sorting process continues on a next group of words;

ii. if the group of words just finished needs further subdividing, as is the manner in radix sorting, then the sorting process continues on a subgroup within the group just finished;

(4) if an integer in lettertracker is greater than zero, then it locates a first word in a group of words, because said integer corresponds to a memory location in wordtracker, such that the integer 10 in lettertracker points to the tenth memory location in wordtracker, which location holds another integer that points to the first word in a group of words, such that the integer 10 in wordtracker signifies that the tenth word in the list being sorted is the first word in a group of words within that list;

(5) if an integer in lettertracker equals zero, then that signifies an empty group of words, namely no words within a particular letter in a particular position of a word are currently being processed;

(6) after one group of words is processed, examining the integers in lettertracker in sequential order locates a next group of words to be processed, because an integer of zero indicates passing over that empty group, and a non-zero integer indicates the next group to process.