Academic Publishing Wiki
Register
Advertisement

Check sort and Rapid sort

Rapid sort 3

Summary

Sorting consists of the two operations of separating items and arranging them in order. The Check sort and the Rapid sort routines combine these operations into one by assigning the value of the quality of the item which will serve as the basis for the item's detection or distinction to an array variable index rather then assigning the value to a variable as its contents, cargo or payload. The representation of the value of the quality being sorted by an index establishes the difference between other sort routines and the Check sort and Rapid sort routines[1]. The difference between the Check sort and the Rapid sort routine is that the Check sort is used to sort sets while the Rapid sort is used to sort multisets.

Description

The Check sort[2] is the logical precursor of the Rapid sort although the Rapid sort was discovered prior to the Check sort. Both sorts were discovered without knowledge of any prior discoveries. Both sort routines are compact high speed numerical data Class L[3] sort routines.

Both sort routines are dependent upon a numerical value being assigned to represent the desired order of the quality being sorted, such as color or size, to index an array variable. One advantage of doing this is that the sort can be performed in sequence or in parallel depending upon the capability of the Computer. When the presence of a particular item quality is detected the variable's index is set equal to the numerical value of the order assigned to the particular quality of the item and the contents of the variable incremented, starting from zero, whenever an assigned quantity is detected. The Check sort uses a "check mark" consisting of a count from zero to one, i.e., a(n)=one while the Rapid sort continues to increment the indexed variable's value each time a duplicate or multiset quality is detected. The Rapid sort functions in the identical manner as the Check sort with the exception that incrementation of the digit is allowed to extend past a value of one by replacing the a(n)=one assignment with a(n)=a(n)+one.

Separation is preformed by inputing the data, while sorting is accomplished by sequentially printing the index of each variable containing a value greater than zero. The incrementation of a binary digit from one to zero is technically counting but neither the Check sort or the Rapid sort should be confused with the Counting sort, even though all three are dependent upon array indexing and array value incrementation to accomplish the sort.

Counting sort difference

How is the Check sort different from the Counting sort? The Check sort function is identical to a function published by Bentley[4] in which a binary string of digits is used to indicate the presence or absence of a political precinct number in a file by setting all digits in the string of binary digits to zero and then changing the value to one as each precinct reports in. There is no functional deference between Bentley's unnamed sort and the Check sort except for the step which is used to clear the bit array and its defining application[5] and the date of publication. Bentley's sort was first published in 1986 while the Check sort was published in 1996. The Rapid sort[6] preceded development of the Check sort, which is its logical precursor. The Distribution Counting sort[7] is functionally not different from the Rapid sort, except for its defining application of counting and sorting measurement frequencies per statistical interval in a histogram or other statistical distribution, which are technically multisets.

The Counting sort can sort items that, in addition to the key, also have arbitrary data associated with each item. The Check sort, like the Rapid sort, only sorts keys. In other words, items to be sorted consist solely of the key; there is no additional data in items[8]. What makes this distinction significant is that the key itself can be data, as in values contained by sets and multisets, which can be counted and sorted.

Radix sort difference

The Check sort and the Rapid sort are also not the same as the Radix sort which sorts each digit based on the positional significance of each digit in the number.

Bucket sort difference

How is the Check sort different from the Bucket sort? Although an item may be placed into a particular bucket according to the quality of the item to be sorted with the first item serving as the index of the quality being sorted and in effect "marking" each bucket with the quality of the item the bucket will receive, a decision still has to be made for each item which is selected as to what quality the item has and what bucket it should go into. This is true whether the decision maker is a person or an "if/then" statement in a computer program.

The Check sort and the Rapid sort, on the other hand, eliminate the need for a decision for each and every item as to the item's quality and as to which bucket the item will go into. The only decisions required are the initial decisions as to the order of the index that will be assigned to a particular quality of the items to be sorted. Thereafter the contents of the variable which is indexed will only be incremented. When all items are processed the array index can then be reset to zero and incremented sequentially to the number of qualities assigned. If the indexed contents of the variable is greater than zero it is decremented and the value of the index listed or printed, rather than the contents of the indexed variable being listed or printed.

The Rapid sort functions in the identical manner as the Check sort with the exception that incrementation of the digit is allowed to extend past a value of one by replacing the a(n)=one assignment with a(n)=a(n)+one.

Instant Sort

The hardware version of the Check sort is called the "Instant sort" and uses a single bit data bus random access memory chip (such as the NTE2102 1024x1 static ram chip) to record the binary incrementation at any location indexed by the data which is applied to the random access memory chip address bus. The Rapid sort is implemented in hardware in the same manner as the Check sort (also called the "Instant sort") by using a random access memory chip with a wider data bus. The Check sort and Rapid sorts are also known as the "Simple sort" due to their simplicity.[9]

Computer Programs

Visual Basic v6 Code
Check Sort Performance Analysis

Data

Rapid Sort Performance Analysis

Data

C++ Code
Check Sort Performance Analysis

Data

Usage Example

Multisets counted and automatically sorted

notes

  1. The flowchart of the Distribution Counting sort, however, published by Knuth in his "Sorting and Searching" on page 79 represents a prior description and name for the same function with a different application, "distribution" referring to areas beneath a normal statistical distribution or histogram where the areas served as the location index for the count of frequency within the areas.
  2. For a prior unnamed and unsourced sort with the same function see: "Programming Pearls", 1986 edition, Jon Louis Bentley, Addison-Wesley, Column 1, Cracking the Oyster, page 5, Section 1.4, Implementation Sketch for the sort routine he shows on page 6 and states it came from his "Programming Pearls" column in the Communications of the Association for Computing Machinery with publication history in the introductions to Parts I,II and III and that "...the input is from a small range, it contains no duplicates, and no data is associated with the record beyond the single integer." possibly referencing Harold H. Seward's Counting sort which may be proceeded by a hardware version by Robbins who patented a hardware version of the Radix sort a month and a half prior to publication of the Radix sort claimed by Seward to be his invention. Robbins' patent application was filed in 1952.
  3. Class refers to the type of performance derived from the regression analysis of the ratio of time in seconds to the number of items sorted. If the ratio is constant the regression curve will be straight or linear, hence a Class L sort routine is one with a linear performance curve. Where f(n) = t/n or f of n is theta g of n in Big O notation.
  4. See reference #1, "Programming Pearls", 1986 edition, Jon Louis Bentley, Addison-Wesley, Column 1, Cracking the Oyster, page 5, Section 1.4, Implementation Sketchof the sort routine Bentley shows on page 6.
  5. Alternate names for the same function are important in helping to eliminate confusion as to subject matter of the application.
  6. The Rapid sort is the result of an effort by the author to maximize Shell sort speed by eliminating repetitions at the expense of memory.
  7. Donald E Knuth gives credit to H. Seward for its initial publication in 1954
  8. Paul E. Black, "rapid sort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 19 June 2006. (accessed 2008-09-18) Available from: http://www.nist.gov/dads/HTML/rapidSort.html
  9. Both sorts are claimed to be the World's fastest and the World's simplest sort routines in absence of any proof or empirical data to the contrary.


Advertisement