RegisterHomeForumsGallerySearchFAQMemberlistLog in
Bin Sorting: CS11 Assignment

 
Reply to topic    DOST-SEI Online :: [Scholars and Alumni Community] Forum Index » Knowledge Resource Center View previous topic
View next topic
Bin Sorting: CS11 Assignment
Author Message
administrator
DOST-SEI Administrator
DOST-SEI Administrator


Joined: 12 Jun 2006
Posts: 220
Location: Singapore, Singapore

Post Bin Sorting: CS11 Assignment Reply with quote
BIN SORTING

In a bin sorting method for computing equipment in which a group of keys are sorted by association with bins, wherein a key consists of the values which govern the sorting process, the steps comprising:

(a) testing by computer comparison for equality between a portion of a key and a corresponding portion of a prior adjacent key;

( if said portions are not equal,

i. determining the location of a bin corresponding to said portion of said key, and

ii. associating said key with said corresponding bin thereby ordering said key, and

? if said portions are equal, omitting steps ( i. and ( ii. and permitting said key to remain adjacent to said prior adjacent key.

2. In a bit sorting method for computing equipment wherein keys each formed by a plurality of characters are ordered by successive iterations of processing into any of a number of bins M, the step comprising:

identifying in an auxiliary table all of the different characters of a sub-group of keys encountered during a current iteration through such sub-group, and

if the number of said characters identified in said auxiliary table is not greater than a threshold level at the end of said current iteration, processing in a predetermined order only those bins corresponding to characters identified in said auxiliary table, and

if the number of said characters identified in said auxiliary table is greater that said threshold level at the end of the current iteration, checking all bins to determine which ones have been used, and processing only those bins actually used.

3. The method of claim 2, characterized in that said threshold level is between approximately three percent and approximately twenty-five percent of said M total of bins.

4. In a bin sorting method for computing equipment by sorting a group of records comprised of a group of identifying keys and related data into desired sequence, the steps comprising:

i. fetching and evaluating a portion of a key, said portion having one of M possible distinct values,

ii. determining whether said portion of a key has been previously encountered in a present iteration of said sorting procedure,

iii. appending said key to a bin identified by said one of M possible distinct values,

iv. repeating (i), (ii) and (iii) until each key in at least a sub-group of keys has been evaluated and appended to a bin,

v. selecting, in a predetermined order, a first bin with a sub-group of appended keys as a new beginning portion of a file, wherein said selecting includes a process of determining which bins have at least one appended key and which bins do not,

vi. selecting, in said predetermined order a next bin with a next sub-group of appended keys, and appending said next sub-group of appended keys onto said file, wherein said selecting includes a process of determining which bins have at least one appended key and which bins do not,

vii. repeating step (vi) through (vii) until all of said bins have been tested, and all of said keys have been appended to said file, and

viii. performing steps (i) through (vii) until all keys are sorted, wherein the improved method comprises the steps:

(a) after an unsorted key is fetched and prior to determining whether said portion of a key has been previously encountered in a present iteration of said sorting procedure, performing an additional step of determining whether said portion of a key is equal to a second portion of a key in the same respective position of an adjacent key, and

( if said portion of a key is equal to said second portion of a key, failing to perform steps (ii) and (iii) and proceeding to step (iv).

5. The process of claim 4 characterized in that said adjacent key is the prior key.

6. The process of claim 4 characterized in that said adjacent key is the subsequent key.

7. In a bin sorting procedure for computing equipment by sorting a group of records comprised of a group of identifying keys and related data into a desired sequence, the steps comprising:

i. fetching and evaluating a portion of a key, said portion having one of M possible distinct values,

ii. determining whether said portion of a key has been previously encountered in a present iteration of said sorting procedure,

iii. appending said key to a bin identified by said one of M possible distinct values,

iv. repeating steps (i), (ii) and (iii) until each key in at least a sub-group of keys has been evaluated and appended to a bin,

v. selecting, in a predetermined order, a first bin with a sub-group of appended keys, and treating said sub-groups of appended keys as a new beginning portion of a file, wherein said selecting includes a process of determining which bins have at least one appended key and which bins do not,

vi. selecting, in said predetermined order, a next bin with a next sub-group of appended keys, and appending said next sub-group of appended keys onto said file, wherein said selecting includes a process of determining which bins have at least one appended key and which bins do not,

vii. repeating step (vi) until all of said bins have been tested, and all of said keys have been appended to said file, and

viii. performing steps (i) through (vii) until all keys are sorted, wherein the improved method comprises the steps:

(a) performing an additional step of utilizing an auxiliary table to identify each said M possible distinct values actually encountered during a current iteration through said sub-group of keys, and

( if said number of values actually encountered is not greater than a threshold level at the end of said current iteration, processing in a predetermined order only those bins identified by said auxiliary table, and failing to determine which bins have at least one appended key and which bins do not.

8. The process of claim 7 characterized in that said threshold level is between approximately three percent and approximately twenty-five percent of said M possible distinct values.

9. Apparatus for sorting a group of keys by association with bins, comprising:

testing means for determining whether a portion of a key is equal to a corresponding portion of a prior adjacent key;

first ordering means for determining the location of a bin corresponding to said portion of said key and associating said key with said corresponding bin if said portions are not equal; and

second ordering means for permitting said key to remain adjacent to said prior adjacent key if said portions are equal.

10. Apparatus for sorting a group of keys wherein each of said keys are formed by a plurality of characters and are ordered by successive iterations of processing into any of a number of bins M, comprising:

means for defining a said number of bins M,

identifying means responsive to said iterations for identifying all of the difference characters of a sub-group of keys encounter during a current iteration through such sub-group, and

counting means for determining whether said identified different characters exceeds a threshold level,

processing means responsive to a determination by said counting means that said identified different characters does not exceed said threshold level, for processing in a predetermined order only those bins corresponding to said identified different characters, and

checking means responsive to a determination by said counting means that said identified different characters exceeds said threshold level, for checking all bins to determine which ones have been used, and processing only those bins actually used.

11. The apparatus of claim 10, characterized in that said threshold level is between approximately three percent and approximately twenty-five percent of said M total of bins.

12. Apparatus for sorting a group of records comprised of a group identifying keys and related data into a desired sequence, comprising:

i. means for fetching sand evaluating a portion of a key, said portion having one of M possible distinct values,

ii. means for determining whether said portion of a key has been previously encountered in a present iteration of said sorting procedure,

iii. identifying means for appending said key to a bin identified by said one of M possible distinct values,

iv. distributing means for repeating steps (i), (ii) and (iii) until each key in at least a sub-group of keys has been evaluated and appended to a bin,

v. first selecting means responsive to said distributing means, for choosing, in a predetermined order, a first bin with a sub-group of appended keys, and treating said sub-group of appended keys as a new beginning portion of a file, wherein said selecting includes a process of determining which bins have at least one appended key and which bins do not,

vi. next selecting means responsive to said distributing means, for choosing, in said predetermined order, a next bin with a next sub-group of appended keys, and appending said next sub-group of appended keys onto said file, wherein said selecting includes a process of determining which bins have at least one appended key and which bins do not,

vii. means for repeating step (vi) until all of said bins have been tested, and all of said keys have been appended to said file, and

viii. means for performing steps (i) through (vii) until all keys are sorted, wherein the improved apparatus comprises:

(a) testing means responsive to said means for fetching and evaluating, for performing an additional step of determining whether said portion of a key is equal to a second portion of a key in the same respective position of an adjacent key, and

( skipping means responsive to a determination by said testing means that said portion of a key is equal to said second portion of an adjacent key, for skipping over steps (ii) and (iii) and proceeding to step (iv).

13. The apparatus of claim 12 characterized in that said adjacent key is the prior key.

14. The apparatus of claim 12 characterized in that said adjacent key is the subsequent key.

15. Apparatus for sorting a group of records comprised of a group of identifying keys and related data into a desired sequence, comprising:

i. means for fetching and evaluating a portion of a key, said portion having one of M possible distinct values,

ii. means for determining whether said portion of a key has been previously encountered in a present iteration of said sorting procedure,

iii. identifying means for appending said key to a bin identified by said one of M possible distinct values,

iv. distributing means for repeating steps (i), (ii) and (iii) until each key in at least a sub-group of keys has been evaluated and appended to a bin,

v. first selecting means responsive to said distributing means for choosing, in a predetermined order, a first bin with a sub-group of appended keys, and treating said sub-group of appended keys as new beginning portion of a file, wherein said selecting includes a process of determining which bins have at least one appended key and which bins do not,

vi. next selecting means responsive to said distributing means, for choosing, in said predetermined order, a next bin with a next sub-group of appended keys, and appending said next sub-group of appended keys onto said file, wherein said selecting includes a process of determining which bins have at least one appended key and which bins do not,

vii. means for repeating step (vi) until all of said bins have been tested, and all of said keys have been appended to said file, and

viii. means for performing steps (i) through (vii) until all keys are sorted, wherein the improved apparatus comprises:

(a) auxiliary identifying means for performing an additional step of identifying, in an auxiliary table, each of said M possible distinct values actually encountered during a current iteration through said sub-group of keys,

( counting means for determining whether the number of said M values actually encountered exceeds a thresholds level,

? processing means responsive to a determination by said counting means that said number of M values actually threshold level, for processing in a predetermined order only those bins identified by said auxiliary table, and failing to determine which bins are associated with at least one key and which bins are not.

16. The apparatus of claim 15 characterized in that said threshold level is between approximately three percent and approximately twenty-five percent of said M possible distinct values.

_________________

We live among you, hidden in plain sight, we have a different language, but we don't speak it, we are elite, but we don't flaunt it, we are different, but we are on...
DOST-SEI Alumni Community :: DOST-SEI Web Mail
Tue Jun 27, 2006 5:49 pm View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger ICQ Number
Display posts from previous:    
Reply to topic    DOST-SEI Online :: [Scholars and Alumni Community] Forum Index » Knowledge Resource Center All times are GMT + 8 Hours
Page 1 of 1

 
Jump to: 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Copyright © 2006 - 2013. DOST-SEI Scholars Online Community. All Rights Reserved