1

I am working on a program that uses just one for-loop for N times and sorts the N elements. Just wished to ask, is it worth it? Because I know it's gonna work because it is working pretty well on paper. It also uses comparisons. I also wished to know if there were any drawbacks in Radix Sort. Cheers.

Anand Akshay
  • 33
  • 6
  • 1
    I'm not sure what you mean. The lower bound on comparison sorts is O(n*lg(n)) how are you implementing it in O(n)? – Benjy Kessler Apr 26 '15 at 17:34
  • See http://stackoverflow.com/questions/3539265/why-quicksort-is-more-popular-than-radix-sort on drawbacks of Radix sort. – Benjy Kessler Apr 26 '15 at 17:35
  • 1
    It's a secret. Just the "coding part" is left. Is it worth the invention? – Anand Akshay Apr 26 '15 at 17:35
  • No, because it is wrong. You can't sort an array in O(n) without prior knowledge of the distribution of the elements in the array. If you do know the distribution then bucket sort works in O(n). – Benjy Kessler Apr 26 '15 at 17:36
  • I am a 17 year old. Can you please elaborate on this? Thanks. (I did not get that "distribution of the elements in the array" part) – Anand Akshay Apr 26 '15 at 17:38
  • If let's say you know that your elements are the numbers 1 to n. Then you can sort them in O(n) by placing number i in index i in the array. In general if you have information regarding what numbers you will be asked to sort you can perform this trick. This is called bucket sort. – Benjy Kessler Apr 26 '15 at 17:39
  • On the other hand if you do not have any information regarding the numbers you will be asked to sort and you want to implement a general purpose sorting algorithm the best you will ever be able to do is O(n*lg(n)). – Benjy Kessler Apr 26 '15 at 17:41
  • What if I told you that my algorithm will be capable of sorting any no. of random positive integers(or negative) in O(n) ? – Anand Akshay Apr 26 '15 at 17:42
  • 2
    Well if you could then you would be incredibly rich and famous but that is because it is mathematically impossible. – Benjy Kessler Apr 26 '15 at 17:43
  • Oh. Well. It's Time to Code then :D – Anand Akshay Apr 26 '15 at 17:44
  • Does your algorithm loop through all N elements of the array N times? Because that would be a complexity of O(n^2), not O(n). – BJ Myers Apr 26 '15 at 17:49
  • @AnandAkshay that Benjy wants to say is, that you will NOT be able to write such a program (if it uses comparison), since there is a proof from theoretic computer science that says it is **impossible** to be faster than O(n log n) if a comparison-based sorting algorithm. See [here](http://www.bowdoin.edu/~ltoma/teaching/cs231/fall07/Lectures/sortLB.pdf) and [here](http://www.cs.cmu.edu/~avrim/451f11/lectures/lect0913.pdf) – Slizzered Apr 26 '15 at 17:50
  • just once @BJMyers or less probably – Anand Akshay Apr 26 '15 at 17:50
  • Next criterion - does it work with floating-point values? And strings? – BJ Myers Apr 26 '15 at 17:54
  • It will work with floating-point values and "may be able to work with strings" using some kind of ASCII code manipulation or string comparison – Anand Akshay Apr 26 '15 at 17:59
  • Based on that answer, I strongly suspect your algorithm is not a true comparison-based sort. I'm still interested to see what you come up with though! – BJ Myers Apr 26 '15 at 18:05
  • 2
    `What if I told you that my algorithm will be capable of sorting any no. of [unrestricted integers] in O(n)?` When finished, move on to [_random compression_](http://marknelson.us/2012/10/09/the-random-compression-challenge-turns-ten/) and [infinite power sources/perpetuum mobile](http://en.wikipedia.org/wiki/Perpetual_motion). – greybeard Apr 26 '15 at 18:36
  • @BenjyKessler my code is ready :D – Anand Akshay Apr 27 '15 at 09:20
  • Cool, how are you benchmarking it? – Benjy Kessler Apr 27 '15 at 09:22
  • Can you help me out on this one? Actually I got question banned for 2 days , didn't know the rules that we can't post duplicate questions. Anyways, I actually want to confirm the complexity of my algorithm and I am I want to benchmark it but don't know how to start with. :( – Anand Akshay Apr 27 '15 at 09:46
  • Generate a long random list. Sort it. Measure the time it took. Double the size of the array. Measure the time. Keep doing this and generate a chart. If the runtime is O(n) then you should see that doubling the length of the array doubles the runtime. Another way is to count how many times you perform a comparison instead of counting time but for now I would stick with time. – Benjy Kessler Apr 27 '15 at 10:51
  • Should I use file streams to input the long random list? By the way! The Space Complexity for my algorithm is O(1) ! :D – Anand Akshay Apr 27 '15 at 12:18
  • "Is it worth the invention?" yes ! good luck – yeg Apr 26 '15 at 17:43
  • Thanks a lot for that motivation! :D I am participating in Google Science Fair with this project of mine – Anand Akshay Apr 26 '15 at 17:45
  • It is worth it in the same sense that building perpetual motion machines and discovering magic fairy dust is worth it. – Benjy Kessler Apr 26 '15 at 17:45
  • I would surely inform you if I succeed :D @BenjyKessler thanks for your help anyways! – Anand Akshay Apr 26 '15 at 17:47
  • come on guys this kid will be your next CEO. don't listen to any one. even if you will fail to do this or you will give up in some point ,im sure this process will teach you more then you can learn in any uni or maybe lead you to other ideas. – yeg Apr 26 '15 at 17:51
  • That is a sentiment I am willing to second :-) – Benjy Kessler Apr 26 '15 at 17:55
  • Yeah you can use file streams. Sorting algorithms that run in O(1) (usually technically O(log(n) because you need to store a loop index to iterate over the loop) space are called in place. You can see http://planetmath.org/inplacesortingalgorithm. – Benjy Kessler Apr 27 '15 at 17:02
  • @BenjyKessler Not O(n) though but probably O(nk) where k is a constant! http://stackoverflow.com/questions/29951428/what-would-be-the-space-and-time-complexity-of-my-sorting-algorithm – Anand Akshay Apr 29 '15 at 18:36
  • If k is constant then O(nk) =0(n) – Benjy Kessler Apr 29 '15 at 19:26
  • If you really want to benchmark the sorting algorithm then count how many ifs get called. You claim that fewer than nlogn if statements get called. An easy way to do this is to write a function called my_if that receives a boolean and just returns the boolean it receives and also increments a global counter. Then replace all your ifs with if(my_if(some predicate)) – Benjy Kessler Apr 29 '15 at 19:39
  • Can you open the link^ and help out with making that function? – Anand Akshay Apr 30 '15 at 03:06

1 Answers1

1

Your post mentions that you are using comparisons. Comparison-based sorting algorithms need at least O(n log n) comparisons for average inputs. Please note that Ω(n log n) lower bound on comparison sorting algorithms has been proven mathematically using information theory. You can only achieve O(n) is the best case scenario where the input data is already sorted. There is a lot more detail on sorting algorithm on Wikipedia.

I would only implement your sorting algorithm as a challenging programming exercise. Most modern languages already provide fast sorting algorithms that have been thoroughly tested.

Alex
  • 21,273
  • 10
  • 61
  • 73