The BitImageSort
I learned an interesting sorting function today.
This is first time for me to read a book that teaches you how to implement a sorting function by yourself.
I found it’s more interesting than I thought.
This is the user story.
One day. A friend asked me to help him. He said:”Hi Deron, how can I sort a disk file?”
I replied:“You can easily find the way on some algorithm books like XXX and XXX”. But it looked like he wasn’t interested in deep learning, he was interested in how to solve the problem. So I told him there was a code part in one popular book that can solve this problem. It could be around 200 lines code and 10+ functions, I think he needs 1 week to implement it and test the code.
I thought I found a solution, but was still in doubt. So, I kept thinking.
I asked:“What data do we need to sort out, how many lines and what should be the input format?”
He said:“There are 1,000,000 lines in the file and every line is an integer and there are all 8-letters long integers”
I asked:“anything else?”
He said:“They are all positive integers and they don’t contain any linked data”.
So, this is the information I got.
input:
A file with the largest number of N positive integers, every integer are less or equals than n, n = 10,000,000 and N = 1,000,000
output:
A file has intergers in the ascending order.
constraint:
The run time should be less than 5 minutes. If the run time is 10 seconds then we don’t need to optimize it.
We can use a 20 bit long list to store 20 numbers who are all less than 20 like:
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0
This means [1, 2, 3, 5, 8, 13]. Every number is set to 1.
All the code is here:
You can also see the source code and result file by clicking on this link:
I wrote it in Python because it’s easy to implement and easy to read.
And you can also think how to implement it with negative numbers in the input and How should we change the code?
