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
public:how_parkrun_volunteers_sort_barcodes_-_a_computer_scientist_s_perspective [2018/12/28 03:11] – fangfufupublic:how_parkrun_volunteers_sort_barcodes_-_a_computer_scientist_s_perspective [2018/12/28 11:23] (current) – fangfufu
Line 1: Line 1:
 ====== How Parkrun volunteers sort barcodes - a computer scientist's perspective ====== ====== How Parkrun volunteers sort barcodes - a computer scientist's perspective ======
-On the Christmas day of 2018, I volunteered at Norwich Parkrun. Towards the end, I ended up helping out with sorting the plastic barcodes. I find the whole process interesting. This is because sorting algorithm is an essential part of computer science curriculum [(https://en.wikipedia.org/wiki/Sorting_algorithm#History)]. I do have a special connection to sorting algorithm - I bumped into Sir Charles Antony Richard Hoare FRS FREng [(https://en.wikipedia.org/wiki/Tony_Hoare)][(https://www.fangfufu.co.uk/wiki/doku.php?id=public:bumping_into_sir_tony_hoare_on_the_day_before_i_learnt_quicksort)], the inventor of quicksort algorithm [(https://en.wikipedia.org/wiki/Quicksort)], the day before I was formally taught quicksort for the second time [(I was taught it once in A-Level Maths D1 module when I was a Year 12 student in Ashmole School, London.)] as a computer science undergrad in University of York.+On the Christmas day of 2018, I volunteered at Norwich Parkrun. Towards the end, I ended up helping out with sorting the plastic barcodes. I find the whole process interesting. This is because sorting algorithm is an essential part of computer science curriculum [(https://en.wikipedia.org/wiki/Sorting_algorithm#History)]. I do have a special connection to sorting algorithm - I bumped into Sir Charles Antony Richard Hoare FRS FREng [(https://en.wikipedia.org/wiki/Tony_Hoare)][(https://www.fangfufu.co.uk/wiki/doku.php?id=public:bumping_into_sir_tony_hoare_on_the_day_before_i_learnt_quicksort)], the inventor of quicksort algorithm [(https://en.wikipedia.org/wiki/Quicksort)], the day before I was formally taught quicksort for the second time [(I was taught it once in A-Level Maths D1 module when I was a Year 12 student in Ashmole School, London.)] as a first year computer science undergrad in University of York.
  
 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