Differences

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

Link to this comparison view

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>​
  
  • public/how_parkrun_volunteers_sort_barcodes_-_a_computer_scientist_s_perspective.txt
  • Last modified: 2018/12/28 11:23
  • by fangfufu