Understanding Binary Radix Sort for Efficient Data Sorting

Slide Note

Explore the concept of Binary Radix Sort explained through sorting punch cards into order with a pencil. Learn how to efficiently sort data using divide and conquer techniques based on binary numbers. Discover the practical ways to teach computing and computational thinking without relying on computers. Enhance your knowledge of sort algorithms and their importance in making data easier to find.

taily Follow

Uploaded on Sep 19, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

Punch Card Sorting: Binary Radix Sort Paul Curzon Queen Mary University of London CAS London With support from Google, Dept for Education the Mayor of London www.teachinglondoncomputing.org Twitter: @TeachingLDNComp

Aims Give you deeper understanding of core topics Binary Radix Sort Binary numbers Divide and Conquer Efficiency of algorithms Computational thinking Give you practical ways to teach computing in a fun, thought provoking way away from computers, focus on concepts Linked activity sheets and booklets can be downloaded from our website: www.teachinglondoncomputing.org

Sort Algorithms A sort algorithm takes an array of data and puts it into order (either ascending order or descending order) eg [5, 7, 2, 99, 4] -> [2, 4, 5, 7, 99] [ cat , hat , ant ] -> [ ant , cat , hat ] Often used as a way of making things easier to find (eg in a telephone directory) There are many sort algorithms some more efficient than others www.teachinglondoncomputing.org

Sorting Punch Cards Suppose we want to sort a pile of cards in to order? All we need is a pencil and as if by magic 1

Binary Radix Sort To sort an pile of punch cards: place a pencil in the right most hole Shake out all those with a slot in that position Put them to the back without changing their order Repeat the above on the second hole, then the third and so on through all the holes. The cards are now sorted (it is very fast) 1

An example Take the cards: 2, 1, 3, 0 That is 10, 01, 11, 00 Sorting on the first digit, we get 01, 11 and 10, 00 Putting the 1s to the back, gives 10, 00, 01, 11 Doing the same on the second digit gives 00, 01, 10, 11 (ie 0, 1, 2, 3) For bigger numbers we would now move to the next digit,

How does it work It is a form of divide and conquer We solve the problem by splitting it in to two halves based on the next digit those numbers with a digit 0 and those with a digit 1 We then face the same problem again with the next digit just smaller (fewer digits left to do) 1

It is fast parallel programming Divide and Conquer is very fast We can also do the splitting in parallel, checking the digit of every card at once using the pencil and gravity! That makes it even faster 1

Generalising: Radix Sort The algorithm can be generalised to any base not just binary You need one bucket per digit For binary we had two buckets , the front and back of the pack In decimal you work through the digits in the same way. you need a place to put the 9s, a place to put the 8s, and so on, keeping the order in each bucket Then put them back together keeping the order Move to the next digit. 1

Computational Thinking Lessons Algorithmic thinking Decomposition Data Representation Evaluation Logical Thinking Generalisation

Summary A well-chosen algorithm can do a job incredibly quickly A poorly chosen algorithm can be very slow by comparison.

More support On our website to support this session: Activity sheets Story sheets Slides Details of more workshops/courses Teaching London Computing is now morphing in to CAS London www.teachinglondoncomputing.org Twitter: @TeachingLDNComp