Data sorting method and navigation method and system using the sorting method

• US 20040030678A1
• Filed: 08/12/2002
• Published: 02/12/2004
• Est. Priority Date: 08/12/2002
• Status: Active Grant

• Current Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Original Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Inventors: Tu, Ihung S.
• Granted Patent: US 6,934,705 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 7/22 Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A data sorting method for sorting data at high speed with small memory capacity. The sorting method sorts an array of data where sorted data is constituted by a combination of a plurality of blocks where each block is produced separately from one another during the sorting process. In another aspect, a navigation method and system utilizes the data sorting method for quickly sorting and displaying requested information such as POIs sorted by distance with use of a small memory.

Claims

1. A data sorting method for sorting an array of input data in a specified order to a plurality of blocks, comprising the following steps of:

(a) defining a number of data entries A for each block when the input data array has N entries and a total number of blocks is N/(X−

B), where X is smaller than N;

(b) creating a buffer of X=A+B entries configured by a series of a sorted buffer of A entry positions and a working buffer of B entry positions;

(c) defining “

previous high” and

a reference entry where the previous high is a highest value in a block of sorted entries obtained in an immediately previous sorting and the reference entry is a value in a last entry position of the sorted buffer;

(d) searching an entry that satisfies conditions of (1) larger than the previous high and (2) smaller than the reference entry and load the entry that satisfies the conditions in the sorted buffer;

(e) sorting the entries in the sorted buffer in a forward order when the sorted buffer is full;

(f) searching an entry that satisfies conditions of (1) larger than the previous high and (2) smaller than a new reference entry and load the entry that satisfies the conditions in the working buffer;

(g) sorting the entries in the buffer in the forward order when the buffer is full;

(h) repeating the above steps (f)-(g) until no entry satisfies the conditions in the step (f); and

(i) producing a block of sorted entries by taking the entries A from the sorted buffer.

2. A data sorting method as defined in claim 1, further comprising a step of determining whether all the blocks of sorted entries are produced, and if not, repeating the steps (c)-(i) until all the blocks of sorted entries are produced.

3. A data sorting method as defined in claim 1, wherein said new reference entry is a value in the last entry position of the sorted buffer after the sorting step (e) or the sorting step (g), thereby collecting an entry of a smallest value from the input data array.

4. A data sorting method as defined in claim 1, wherein an initial value of said reference entry in the step (c) is a maximum value larger than any entry in the input data array.

5. A data sorting method for sorting an array of input data in a specified order to a plurality of blocks, comprising the following steps of:

(a) defining a number of data entries A for each block when the input data array has N entries and a total number of blocks is 2N/(X−

B), where X is smaller than N;

(b) creating a buffer of X=A+B entries configured by a series of a sorted buffer of A entry positions and a working buffer of B entry positions;

(c) defining “

previous low” and

a reference entry where the previous low is a lowest value in a block of sorted entries obtained in an immediately previous sorting and the reference entry is a value in a last entry position of the sorted buffer;

(d) searching an entry that satisfies conditions of (1) smaller than the previous low and (2) larger than the reference entry and load the entry that satisfies the conditions in the sorted buffer;

(e) sorting the entries in the sorted buffer in a reverse order when the sorted buffer is full;

(f) searching an entry that satisfies conditions of (1) smaller than the previous low and (2) larger than a new reference entry and load the entry that satisfies the conditions in the working buffer;

(g) sorting the entries in the buffer in the reverse order when the buffer is full;

(h) repeating the above steps (f)-(g) until no entry satisfies the conditions in the step (f); and

(i) producing a block of sorted entries by taking the entries A from the sorted buffer.

6. A data sorting method as defined in claim 5, further comprising a step of determining whether all the blocks of sorted entries are produced, and if not, repeating the steps (c)-(i) until all the blocks of sorted entries are produced.

7. A data sorting method as defined in claim 5, wherein said new reference entry is a value in the last entry position of the sorted buffer after the sorting step (e) or the sorting step (g), thereby collecting an entry of a largest value from the input data array.

8. A data sorting method as defined in claim 5, wherein an initial value of said reference entry in the step (c) is a minimum value smaller than any entry in the input data array.

9. A navigation method for displaying point of interest (POI) information for selecting a destination, comprising the following steps of:

specifying a category of POI in a navigation system for displaying a list of specified POIs;

collecting a predetermined number (N) of POIs in an input data array;

defining a number A of POIs to be contained in each block to produce a series of blocks each having the sorted POIs, where X is smaller than N, and a total number of blocks is N/(X−

B);

sorting the POIs by distance from a predetermined position in a forward order or a reverse order to produce a block of POIs sorted by distance where each block has A of POIs;

displaying a list of POIs using the block of POIs sorted by distance and scrolling the list of POIs on a display screen in response to a scroll request; and

repeating the above steps of sorting the POIs and displaying the POIs to produce another block of sorted POIs when the sorted POIs from previous sorting become insufficient for a further scroll request.

10. A navigation method as defined in claim 9, wherein said step of sorting the POIs in the forward order is comprised of the following steps of:

(a) creating a buffer of X=A+B entries configured by a series of a sorted buffer of A entry positions and a working buffer of B entry positions;

(b) defining “

previous high” and

a reference entry where the previous high is a largest distance value in a block of sorted POIs obtained in an immediately previous sorting and the reference entry is a distance value in a last entry position of the sorted buffer;

(c) searching a POI that satisfies conditions of (1) larger than the previous high and (2) smaller than the reference entry and load the POI that satisfies the conditions in the sorted buffer;

(d) sorting the POIs in the sorted buffer in a forward order when the sorted buffer is full;

(e) searching a POI that satisfies conditions of (1) larger than the previous high and (2) smaller than a new reference entry and load the POI that satisfies the conditions in the working buffer;

(f) sorting the POIs in the buffer in the forward order when the buffer is full;

(g) repeating the above steps (e)-(f) until no POI satisfies the conditions in the step (f); and

(h) producing a block of sorted POIs by taking the A POIs from the sorted buffer.

11. A navigation method as defined in claim 10, further comprising a step of determining whether all the blocks of sorted POIs are produced, and if not, repeating the steps (b)-(h) until all the blocks of sorted POIs are produced.

12. A navigation method as defined in claim 10, wherein said new reference entry is a distance value in the last entry position of the sorted buffer after the sorting step (d) or the sorting step (f), thereby collecting a POI of a smallest distance value from the input data array.

13. A navigation method as defined in claim 10, wherein an initial value of said reference entry in the step (b) is a maximum distance value larger than any POI in the input data array.

14. A navigation method as defined in claim 9, wherein said step of sorting the POIs in the reverse order is comprised of the following steps of:

(a) creating a buffer of X=A+B entries configured by a series of a sorted buffer of A entry positions and a working buffer of B entry positions;

(b) defining “

previous low” and

a reference entry where the previous low is a smallest distance value in a block of sorted POIs obtained in an immediately previous sorting and the reference entry is a distance value in a last entry position of the sorted buffer;

(c) searching a POI that satisfies conditions of (1) smaller than the previous low and (2) larger than the reference entry and load the POI that satisfies the conditions in the sorted buffer;

(d) sorting the POIs in the sorted buffer in a reverse order when the sorted buffer is full;

(e) searching a POI that satisfies conditions of (1) smaller than the previous low and (2) larger than a new reference entry and load the POI that satisfies the conditions in the working buffer;

(f) sorting the POIs in the buffer in the reverse order when the buffer is full;

(g) repeating the above steps (e)-(f) until no POI satisfies the conditions in the step (e); and

(h) producing a block of sorted POIs by taking the A POIs from the sorted buffer.

15. A navigation method as defined in claim 14, further comprising a step of determining whether all the blocks of sorted POIs are produced, and if not, repeating the steps (b)-(h) until all the blocks of sorted POIs are produced.

16. A navigation method as defined in claim 14, wherein said new reference entry is a distance value in the last entry position of the sorted buffer after the sorting step (d) or the sorting step (f), thereby collecting a POI of a largest distance value from the input data array.

17. A navigation method as defined in claim 14, wherein an initial value of said reference entry in the step (b) is a minimum distance value smaller than any POI in the input data array.

18. A navigation system for displaying point of interest (POI) information for selecting a destination, comprising:

means for specifying a category of POI in a navigation system for displaying a list of specified POIs;

means for collecting a predetermined number (N) of POIs in an input data array;

means for defining a number A of POIs to be contained in each block to produce a series of blocks each having the sorted POIs, where X is smaller than N, and a total number of blocks is N/(X−

B);

means for sorting the POIs by distance from a predetermined position in a forward order or a reverse order to produce a block of POIs sorted by distance where each block has A of POIs;

means for displaying a list of POIs using the block of POIs sorted by distance and scrolling the list of POIs on a display screen in response to a scroll request; and

means for repeating the above procedure of sorting the POIs and displaying the POIs to produce another block of sorted POIs when the sorted POIs from previous sorting become insufficient for a further scroll request.

19. A navigation system as defined in claim 18, wherein said means for sorting the POIs in the forward order performs the following steps of:

(a) creating a buffer of X=A+B entries configured by a series of a sorted buffer of A entry positions and a working buffer of B entry positions;

(b) defining “

previous high” and

a reference entry where the previous high is a largest distance value in a block of sorted POIs obtained in an immediately previous sorting and the reference entry is a distance value in a last entry position of the sorted buffer;

(c) searching a POI that satisfies conditions of (1) larger than the previous high and (2) smaller than the reference entry and load the POI that satisfies the conditions in the sorted buffer;

(d) sorting the POIs in the sorted buffer in a forward order when the sorted buffer is full;

(e) searching a POI that satisfies conditions of (1) larger than the previous high and (2) smaller than a new reference entry and load the POI that satisfies the conditions in the working buffer;

(f) sorting the POIs in the buffer in the forward order when the buffer is full;

(g) repeating the above steps (e)-(f) until no POI satisfies the conditions in the step (f); and

(h) producing a block of sorted POIs by taking the A POIs from the sorted buffer.

20. A navigation system as defined in claim 18, wherein said means for sorting the POIs in the reverse order performs the following steps of:

(a) creating a buffer of X=A+B entries configured by a series of a sorted buffer of A entry positions and a working buffer of B entry positions;

(b) defining “

previous low” and

a reference entry where the previous low is a smallest distance value in a block of sorted POIs obtained in an immediately previous sorting and the reference entry is a distance value in a last entry position of the sorted buffer;

(c) searching a POI that satisfies conditions of (1) smaller than the previous low and (2) larger than the reference entry and load the POI that satisfies the conditions in the sorted buffer;

(d) sorting the POIs in the sorted buffer in a reverse order when the sorted buffer is full;

(e) searching a POI that satisfies conditions of (1) smaller than the previous low and (2) larger than a new reference entry and load the POI that satisfies the conditions in the working buffer;

(f) sorting the POIs in the buffer in the reverse order when the buffer is full;

(g) repeating the above steps (e)-(f) until no POI satisfies the conditions in the step (e); and

(h) producing a block of sorted POIs by taking the A POIs from the sorted buffer.