# Differences

This shows you the differences between two versions of the page.

Both sides previous revision Previous revision Next revision | Previous revision | ||

public:how_parkrun_volunteers_sort_barcodes_-_a_computer_scientist_s_perspective [2018/12/28 03:12] fangfufu |
public:how_parkrun_volunteers_sort_barcodes_-_a_computer_scientist_s_perspective [2018/12/28 11:23] fangfufu |
||
---|---|---|---|

Line 4: | Line 4: | ||

Sorting numbers inside a computer is a bit different to sorting objects in physical world. This is mainly because the uniform cost model does not apply in the physical world [(costmodel > https://en.wikipedia.org/wiki/Analysis_of_algorithms#Cost_models)]. However some of the concepts in algorithm analysis can still be applied to physical world, for example time complexity and space complexity [(https://www.cs.utexas.edu/users/djimenez/utsa/cs1723/lecture2.html)]. | Sorting numbers inside a computer is a bit different to sorting objects in physical world. This is mainly because the uniform cost model does not apply in the physical world [(costmodel > https://en.wikipedia.org/wiki/Analysis_of_algorithms#Cost_models)]. However some of the concepts in algorithm analysis can still be applied to physical world, for example time complexity and space complexity [(https://www.cs.utexas.edu/users/djimenez/utsa/cs1723/lecture2.html)]. | ||

- | In this blog post, we analyse the algorithm which Parkrun volunteers use to sort barcodes, using some concepts from computer science. | + | In this blog post, we analyse the algorithm which Parkrun volunteers use to sort barcodes, using some concepts from computer science. This blog post is written in such a way so you can follow it, even if you have not formally studied computer science. |

+ | | ||

+ | In short, Parkrun uses bucket sort to sort their barcodes after each event. I do not think I have encountered an implementation of bucket sort on computers, yet I was treated with a real life implementation of bucket sort on Christmas day. | ||

===== Analysis of algorithms ===== | ===== Analysis of algorithms ===== | ||

Line 59: | Line 61: | ||

The first stage establishes a partial ordering [(https://en.wikipedia.org/wiki/Partially_ordered_set)] of the original data structure (all of the barcodes) - there is ordering amongst the buckets, but there is no ordering within each bucket. To establish total ordering [(https://en.wikipedia.org/wiki/Total_order)], each bucket need to be sorted using comparison sort. | The first stage establishes a partial ordering [(https://en.wikipedia.org/wiki/Partially_ordered_set)] of the original data structure (all of the barcodes) - there is ordering amongst the buckets, but there is no ordering within each bucket. To establish total ordering [(https://en.wikipedia.org/wiki/Total_order)], each bucket need to be sorted using comparison sort. | ||

- | ==== Sorting individual buckets ==== | + | ==== Sorting individual buckets using insertion sort ==== |

Different worker threads (volunteers) tend to use different sorting algorithm. Personally I use insertion sort, which is a comparison sort. | Different worker threads (volunteers) tend to use different sorting algorithm. Personally I use insertion sort, which is a comparison sort. | ||

Line 98: | Line 100: | ||

However there are some physical optimisation which I made. I collapsed consecutive sorted barcodes into clusters. This is because physically inserting a barcode involves moving all the adjacent barcodes, which takes quite a bit of effort on a rough surface. The two figures below illustrate what I meant: | However there are some physical optimisation which I made. I collapsed consecutive sorted barcodes into clusters. This is because physically inserting a barcode involves moving all the adjacent barcodes, which takes quite a bit of effort on a rough surface. The two figures below illustrate what I meant: | ||

- | <columns 100% - - > | + | <columns 100% 50% 50% > |

<WRAP centeralign> | <WRAP centeralign> | ||

//Uncollapsed barcodes, they became a bit unwieldy to shuffle around. // | //Uncollapsed barcodes, they became a bit unwieldy to shuffle around. // | ||

+ | |||

+ | {{:public:parkrun:20181225_102455.jpg?400}} | ||

</WRAP> | </WRAP> | ||

- | {{ :public:parkrun:20181225_102455.jpg?400 |}} | ||

<newcolumn> | <newcolumn> | ||

<WRAP centeralign> | <WRAP centeralign> | ||

- | //Partially collapsed clusters of consecutive barcodes, it was much easier to perform insertion. // | + | //Partially collapsed clusters of consecutive barcodes, this made it much easier to perform insertion. // |

- | </WRAP> | + | |

- | {{ :public:parkrun:20181225_103446.jpg?400 |}} | + | {{:public:parkrun:20181225_103446.jpg?400}} |

+ | </WRAP> | ||

</columns> | </columns> | ||