# A new attemp to Sorting and Searching

• 09-18-2012, 08:49 PM
drakula941
A new attemp to Sorting and Searching
I have recently done this code,can any one here just tell me whether this is something new and good? or has something similar or same has already been done.
Code:

class sort_search
{
public static void main(String arg[])
{
Random r = new Random();
int[] x = new int[99999999];
for (int i = 0; i < x.length; i++) {
x[i] = r.nextInt(99999);
}
int largest=x[0];
for(int q=0; q<x.length; q++){
if(x[q]>largest){
largest = x[q];
}
}
//--------X----DO NOT BOTHER MUCH TILL HERR----X--------
//SORTING
int arr[]=new int[largest+1];
long startTime = System.currentTimeMillis();
for(int i=0;i<x.length;i++)
{
arr[x[i]]++;
}
//SEARCHING
int pos=100;
if(arr[pos]>0)
System.out.println(pos+"*"+arr[x[pos]]);
else
long endTime = System.currentTimeMillis();
System.out.println("Time Taken "+(endTime-startTime));
}
}

• 09-18-2012, 09:25 PM
JosAH
Re: A new attemp to Sorting and Searching
So for a two element array { 1, 99999999 } you need a 99999999 element auxiliary array to increase the search speed by 50% at best ...

kind regards,

Jos
• 09-18-2012, 09:35 PM
drakula941
Re: A new attemp to Sorting and Searching
the aux array structure will be same as the originall array structure. :) so what would you conclude sir? is it good and new?(interms of time efficiency only)
• 09-19-2012, 06:51 AM
JosAH
Re: A new attemp to Sorting and Searching
Quote:

Originally Posted by drakula941
the aux array structure will be same as the originall array structure. :) so what would you conclude sir? is it good and new?(interms of time efficiency only)

In line #18 of your code you create a new array proportional to the largest element in your original array, so (given my example) you create an array of size 99999999 for an original array with 2 elements.

kind regards,

Jos
• 09-19-2012, 11:03 AM
drakula941
Re: A new attemp to Sorting and Searching
Quote:

Originally Posted by JosAH
In line #18 of your code you create a new array proportional to the largest element in your original array, so (given my example) you create an array of size 99999999 for an original array with 2 elements.

kind regards,

Jos

So.. you are suggesting me to create a multi dimensional array? like "[2][99999999]" this?
• 09-19-2012, 12:56 PM
JosAH
Re: A new attemp to Sorting and Searching
Quote:

Originally Posted by drakula941
So.. you are suggesting me to create a multi dimensional array? like "[2][99999999]" this?

Nope, I didn't suggest anything.

kind regards,

Jos
• 09-19-2012, 01:41 PM
drakula941
Re: A new attemp to Sorting and Searching
Quote:

Originally Posted by JosAH
so (given my example) you create an array of size 99999999 for an original array with 2 elements.

kind regards,

Jos

so what exactly do you mean by this? please explain properly. :) and please do conlude whether it is new and good or not,with a reason. :)
• 09-19-2012, 03:24 PM
JosAH
Re: A new attemp to Sorting and Searching
Quote:

Originally Posted by drakula941
so what exactly do you mean by this? please explain properly. :) and please do conlude whether it is new and good or not,with a reason. :)

I already gave you the reason and your approach is not new and it's only 'good' if the range of the numbers more or less equals the number of numbers.

kind regards,

Jos
• 09-19-2012, 03:37 PM
drakula941
Re: A new attemp to Sorting and Searching
Quote:

Originally Posted by JosAH
I already gave you the reason and your approach is not new and it's only 'good' if the range of the numbers more or less equals the number of numbers.

kind regards,

Jos

ohk!! thankyou for your review :) can you tell me my approach is similar to which kind of sort or search which already exists? because of which you say its not new. :)
• 09-19-2012, 04:44 PM
JosAH
Re: A new attemp to Sorting and Searching
Quote:

Originally Posted by drakula941
ohk!! thankyou for your review :) can you tell me my approach is similar to which kind of sort or search which already exists? because of which you say its not new. :)

It is a form of 'bucket sorting'; Donald Knuth's 'Searching and Sorting' discusses it; it has limited applicability.

kind regards,

Jos
• 09-19-2012, 07:05 PM
drakula941
Re: A new attemp to Sorting and Searching
Quote:

Originally Posted by JosAH
It is a form of 'bucket sorting'; Donald Knuth's 'Searching and Sorting' discusses it; it has limited applicability.

kind regards,

Jos

can you tell me where its application is limited?? so that i can look on too it... :) please give me some good cases where there are limitations. :) I am desperately waiting for a reply to this... to work on the limitations :D
• 09-19-2012, 09:05 PM
JosAH
Re: A new attemp to Sorting and Searching
I already gave you one of its most severe limitations (see reply #2): if the range of the elements is larger than the number of elements, it needs way too much storage. Your implementations can't handle negative numbers either.

kind regards,

Jos
• 09-20-2012, 02:13 PM
drakula941
Re: A new attemp to Sorting and Searching
Quote:

Originally Posted by JosAH
I already gave you one of its most severe limitations (see reply #2): if the range of the elements is larger than the number of elements, it needs way too much storage. Your implementations can't handle negative numbers either.

kind regards,

Jos

Thanks for that... i will try to work on the negative thing... i doubt the {1,99999999} problem can b solved.. but still ill try to think of some new method and report the solution. :)