This content originally appeared on DEV Community and was authored by Prateek budhiraja
This method only works with an array with numbers that meets some conditions. As I am not an alien from some other galaxy to prove the laws of mathematics wrong ?!
Preface
We know that the fastest algorithm to sort an array takes O(n*log(n)) time, which is also mathematically backed.
But in the quest to do something on a Friday night rather than overthinking why my friends haven't invited to their party ?, I chose this.
This algorithm is based on one condition that the numbers are scattered by MSB's which means there should only be one number from each range category. i.e.
To get this range we will look at the most significant 1 bit of an element (fist encounter of 1 from the left). Which actually tells the highest number it can make.
We can found that with the help of bit manipulations and then we will decide the position(index) of the number in the array based on its MSB position.
Let's code the No Friends Sort!
As I am home on a Friday night, and every number that it sorts is far from each other!
public void noFriendSort(){
int[] arr= {45, 1, 5, 150, 100, 3, 24, 11, 460};
int[] newarr=new int[9];
for(int v : arr) {
int temp=v;
int count=0;
for(int i=1; i<=9; i++) {
temp=temp>>1;
if(temp==0)
break;
count++;
}
newarr[count]=v;
}
}
This code can sort values till 511, though it can go up to the range of int, but the higher the number, the less sense the code makes. As the inputs should be more scattered. So the time complexity of this code would be O(n*9) which is O(n).
But as it only considers one number per range, now I can say that I successfully wasted my Friday night ?.
But it delivers what it says sort array in O(n)!
Google I will be waiting for your call.
This content originally appeared on DEV Community and was authored by Prateek budhiraja
Prateek budhiraja | Sciencx (2021-04-09T21:06:25+00:00) Sort array in O(n) time. Retrieved from https://www.scien.cx/2021/04/09/sort-array-in-on-time/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.