Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Method of Sorting Dates and Time Allowing for Wrapping

IP.com Disclosure Number: IPCOM000113409D
Original Publication Date: 1994-Aug-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 2 page(s) / 81K

Publishing Venue

IBM

Related People

Greer, TD: AUTHOR

Abstract

Disclosed is a method of sorting dates, times, or other data which may wrap the counter. The method does not require specification of an arbitrary window which is assumed to contain the times, but rather uses the data and the information that the numbers are all given modulo something in order to determine the correct ordering. Specific applications include the problems of sorting two-digit years which may cross a century boundary, months which may encompass the end of the year, and times which encompass midnight. The algorithm applies to sorting all cyclical groups of numbers; the sorted numbers need not represent time.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Method of Sorting Dates and Time Allowing for Wrapping

      Disclosed is a method of sorting dates, times, or other data
which may wrap the counter.  The method does not require
specification of an arbitrary window which is assumed to contain the
times, but rather uses the data and the information that the numbers
are all given modulo something in order to determine the correct
ordering.  Specific applications include the problems of sorting
two-digit years which may cross a century boundary, months which may
encompass the end of the year, and times which encompass midnight.
The algorithm applies to sorting all cyclical groups of numbers; the
sorted numbers need not represent time.

      The problem solved may be illustrated with dates in the
neighborhood of the year 2000.  The years labelled '03, '05, '02,
'99, '96, would properly be sorted chronologically as '96, '99, '02,
'03, '05.  A conventional sorting routine would sort them as '02,
'03, '05, '96, '99.  To obtain the correct sorting, a traditional
approach is to pick an arbitrary year and assume that all dates are
after that year, pre-append the appropriate century, and then use a
conventional sorting algorithm.  For example, one might assume that
all the specified dates are after the year 1975.  So '96 must mean
1996 and '03 must mean 2003.  The disclosed method avoids this
arbitrary designation of a date.  Instead, it examines the data,
taking into account the possibility of wrapping, finds the largest
gap, and then shifts the sort so that the number after the largest
gap comes first.  For the dates '02, '03, '05, '96, '99, the
successive differences are 1, 2, 91, 3, and 3 years.  The second
difference of 3 is found by using the understanding that the original
numbers are given modulo 100, i.e.  using circular subtraction.
Since the third difference, 91, is the largest, the fourth date, '96,
should come first, and the correct sorting is then '96, '99, '02,
'03, '05.

      Let MAXNUM be the largest possible number representable, that
is, one less than the modulo base.  For example, the largest year
representable with two digits is '99.  We wish to sort the array
A(i), taking into account the fact that the numbers A(i) may wrap.
The method is

1.  Sort the numbers A(i) using a conventional sorting routine.

2.  Find the largest gap...