Video 3-4: §3.4 Integer sorting

0:04 in the next subsection we'll look at sorting algorithms that can beat the lower bound that we have for comparison based algorithms and apart from being a building block that will come back to later in uh Unit 8 it's also just an important piece to know that um this is sometimes possible and when and how so here again um the lower bound does not really mean that sorting always takes that time the lower bound only applies to the comparison model so if the algorithm has only pair wise comparisons at its dis disposal to uh determine the order of elements then this lower bound applies but it also means if we want to beat this lower bound we have to change the model we have to break out of the comparison model and one example where you can do that and we'll see more in the future is one example is sorting integers if we sort numbers we can do more with numbers in particular we can compute with them and do all sorts of operations which in the word Ram model at least might be much faster than comparisons so uh comparing two integers in the word Ram depending on how big the numbers are uh might be constant time for each comparison that's great but

1:26 that wouldn't allow us to beat the lower bound if we do just comparisons but we can do all sorts of other things now that might mean that the lower bound doesn't apply but it also means uh we have to somehow exploit this and it's not not a prior clear how it would help you to be able to compute with numbers to sort okay so it's

1:53 um sometimes you can you can see how you can do things on top of what the model in the lower bounds allows you but it might not be easy to exploit that but we can use the full power of the word Ram which is not just Computing numbers but also using memory access where the address of the memory cell we read or write to is part of another register indirect

2:22 addressing and so we can use that to build what's called Counting sort again some people will know this um but let's go through this one a bit slowly we have to talk about the range of numbers otherwise um we can't make a definitive statement how long things take so we assume that the numbers are positive integers or or non- negative integers starting including zero up to some upper bound and uh we usually assume that this upper bound is is a power of two so that just means we have B bit binary numbers that we're trying to sort okay so you can think of them as bit strings or you can think think of them as numbers whatever is more convenient and helps you to work with them is

3:09 allowed and uh if we have that assumption plus [Music] um an additional one on the model so this is where things get a little tricky we have uh four parameters flying around we'll have the number of integers that we're sorting that's the little n like we had it all the time we have the capital u which is the upper bound on the range of integers which is related to Little B the number of bits but then we also have W from the word Ram think back unit one that's the the width of the words that's the number of bits we can operate on in constant time and here's an assumption um under which we can sort quickly if the numbers have fewer bits than our word size and and here's the algorithm in in detail uh the way it works is it creates an array with counters and instead of messing with comparing numbers in any B in any uh binary comparisons we'll just go through all the numbers in our list and increment the appropriate counter and for that that key step uses the indirect address mode of of the word Ram so you take the value at that position I in the array and use that as address or offset for this array so after uh the first Loop we have

4:31 in in the counter array all the number of occurrences of that number uh and all we have to do at the second step is just produce a sorted list that has the same numbers so we don't even bother to uh preserve the old numbers because these are just bit strings or numbers they don't have an identity in this case they're not complicated objects anymore just numbers so we go through all the all the numbers that we have and then for each one we repeat as many times as we've seen it in the input that we append it to the output that's what counting sort does in the simplest possible

5:12 way uh let's let's look at the running time a little bit so uh there's different stages we have to initialize the array to zero so that will take take time proportional to U and uh then we have to iterate through our array that Loop runs n times and uh each step is constant time on the word Ram under our assumptions so this is this is constant time but then the loop in total is is

5:50 linear because we run for nend times and then the last bit so this is potentially a bit more tricky so again the the innermost thing does just a a constant number of different steps um a few reads and writes and an addition if we look at how often we execute this then here all we can say is we do it C of K

6:16 times but we don't necessarily know what c of K is so we can't really make a more more clear statement at this point but if we look at the entire Loop um we know that what comes out here is the sum of all the C of K

6:38 values from zero up to U minus one and we have to add some constant overhead for checking so for some of the values that we have never seen in the input we may never execute this inner loop but we're still doing some constant overhead for each iteration of the outer loop we don't get that for free to check that we don't have to run the inner loop so we'll get this this uh plus some constant effort for each I guess I should write this times a constant effort for the inner loop and then plus constant effort now the observation that you need at this point is that uh this sum is just n because it's the occurrences of all the numbers in the input but there they have to be exactly n numbers overall we don't know which ones are more more or less frequent but over all this is this sum is uh is n let's maybe write it separate so the sum of C of K is n so if we simplify this it's n plus u and the plus u comes from this second term I have a constant contribution for every iteration of the outer loop and I run the outer loop for U

8:00 times that's where this running time comes from uh the space is simple that's just the count array we need that much space for storing the counters and uh that can also be a problem right if if U is really big you need space for storing a counter for every possible value that might be a problem but depending on how big U is maybe it's not a problem so the key point for you to take away is is in this box if you have an integers and they are from a small range for example they're bounded in size so the the size of the numbers is bounded in the number of numbers then we can sort them in linear time and

8:52 space you can pump this result up to something called radic sord that's what's um just mentioned here without going into details you can sort in linear time also if the numbers are in a bigger range here we needed that U itself is linear in N maybe 10 times n uh but it can't be much bigger whereas you can improve this to any power of n say n cubed or something like that uh the way to do is uh to do this is using radic sword where you use 2 to the W as your radex if you haven't seen radic sword we don't need it here so uh you can you can ignore it and you can uh forget about this fact for this module uh but I think it's it's useful to know that it's it's possible uh then let me point out that this is not part of the exam material I will sometimes give some pointers to the State ofth art in algorithms just to sprinkle in some knowledge and uh you may wonder ha can I push this idea idea further and almost always the answer is a big yes uh we don't have time to do this in detail and it would take us too far um but I wanted to uh at least mention this that there's

10:15 again some some fairly fundamental questions still open um if we set the range for our numbers to be exactly the word size so we use exactly W bits for our numbers or flip it the other way around you have an input and you choose your your machine appropriately uh then we can reason about what happens if the word size grows or depends on the number of numbers we sort n and then there's different regimes depending on how W relates to n uh different algorithms work with different different performance um if W is relatively small then we can use radic sord as we've seen uh if W is much bigger than log n then again um a different algorithm that you haven't seen uh but it achieves linear time but then there's a a range in between where it's not known whether you can do linear time sorting so this is still is still open as as far as I know um and there's a few really fancy algorithms that achieve some running time much better than n log n which you would get from comparison based sorting uh but they're also in a way far away from linear

11:47 okay as I said if you wish for this module you can mostly ignore that slide um but I think it's useful to have some pointers in there for the rest of the unit we'll go back to the comparison model and we'll focus on that one just because if you were if you use sorting as a building block it's useful to have it as versatile as possible but we'll come back to the simple counting sord from the previous slide in a different context so uh that part you should keep in mind um this slide you can't forget and for now back to the comparison model back to only pair wise

12:52 in I should probably retract so we're still in the word Ram model for this question after that we go back to the comparison model I used in here in the sense that uh I guess C and C++ would use it or Java would use it uh it's just an integer that has the 64 bits is uh nothing nothing special the problem with python is that you don't have a a bounded type every python integer object can be an arbitrarily big number and it will swap out the representation automatically it's convenient to use it but uh the running time might differ

14:01 vastly all right quite a lot of votes are in so let's um have a overlapping uh I think I allowed the last one basically because um it's not it's not completely formally clear what uh what we're supposed to think here if um if n becomes bigger and bigger are we are we supposed to assume the 64 stays as it is or not it's kind of a question in practice you can never have infinite inputs so uh if you talk about astics it's always with a little bit of an asterisk uh but really these two these two are both justifiable this one's easy you can just do merge sort and um unless the comparisons are crazy expensive it'll be uh and log and time and uh for for 64-bit integers you can do it in constant time under this assumption but you can also use the counting sword that we've seen now here's the catch uh remember counting sword so in theory totally

15:26 yes in also in theory you can use radex sword and it will it will fly it will work fine you can in principle use the counting sword I had on the slides but it would use two to the 64 counters and two to to 64 is an incredibly large number you'll probably uh not find it might be at the edge of uh the largest supercomputers on this planet as clusters may have roughly that space maybe not even but it's it's a huge number so you don't want to sort that way but um if you ignore the space cost uh the L the time is fine