The Notes

User Tools

Site Tools

Trace:
public:how_parkrun_volunteers_sort_barcodes_-_a_computer_scientist_s_perspective

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
Last revisionBoth sides next revision
public:how_parkrun_volunteers_sort_barcodes_-_a_computer_scientist_s_perspective [2018/12/28 03:12] – fangfufupublic:how_parkrun_volunteers_sort_barcodes_-_a_computer_scientist_s_perspective [2018/12/28 11:20] – 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. 
  
 ===== Analysis of algorithms  ===== ===== Analysis of algorithms  =====
Line 59: Line 59:
 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 98:
 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