# HashSort?

**807596**Dec 17, 2004 11:22 PM

Okay, I was just writing a method that sorts an array of ints with very, very, quick runtime- much better than Quicksort and even Radix.

public static int[] sort(int[] a)

{

int[] sorted = new int[getMax(a)+1];

for(int i = 0; i < a.length; i++)

sorted[a[i]] = a

public static int[] sort(int[] a)

{

int[] sorted = new int[getMax(a)+1];

for(int i = 0; i < a.length; i++)

sorted[a[i]] = a

*; //assigns the value to the array[value] somewhat like hashing*

int free = 0;

/*

*Note: This for loop is optional, it just eliminates empty spaces in O(n)

*/

for(int k = 0; k < sorted.length; k++)

{

if(sorted[k]==0)

free = k;

else

{

sorted[free] = sorted[k];

sorted[k] = 0;

}

}

return sorted;

}

This makes this algorithm O(n+N), where the least efficient aspect is eliminating the empty spaces(zeros). As of now, I am not concerned about duplicates (dont want to get into buckets) and the numbers must be positive as well.

So, I had two questions:

1.)

Is there any way to improve the efficiency of this sort? (runtime, not O notation)

- a thought- would using an ArrayList make it more efficient? (eliminates one loop)

the downside would be that I would have to store the values as Integers.

Also, would using ArrayList.trimToSize() be a good idea here?

2.)

And, is there any easy way to apply this to objects?

-here is my plan (very very inefficient though)

use obj.toString() to gen a distinct string value for each object

convert this string to a char array (String.toCharArray())

and than convert each character to a number to use as a key

but this makes the algorithm n^2, ie totally useless in my case

Sorry for the intolerable length of this post.

Thanks for you efforts...int free = 0;

/*

*Note: This for loop is optional, it just eliminates empty spaces in O(n)

*/

for(int k = 0; k < sorted.length; k++)

{

if(sorted[k]==0)

free = k;

else

{

sorted[free] = sorted[k];

sorted[k] = 0;

}

}

return sorted;

}

This makes this algorithm O(n+N), where the least efficient aspect is eliminating the empty spaces(zeros). As of now, I am not concerned about duplicates (dont want to get into buckets) and the numbers must be positive as well.

So, I had two questions:

1.)

Is there any way to improve the efficiency of this sort? (runtime, not O notation)

- a thought- would using an ArrayList make it more efficient? (eliminates one loop)

the downside would be that I would have to store the values as Integers.

Also, would using ArrayList.trimToSize() be a good idea here?

2.)

And, is there any easy way to apply this to objects?

-here is my plan (very very inefficient though)

use obj.toString() to gen a distinct string value for each object

convert this string to a char array (String.toCharArray())

and than convert each character to a number to use as a key

but this makes the algorithm n^2, ie totally useless in my case

Sorry for the intolerable length of this post.

Thanks for you efforts...

- 14592 Views
- Tags: none (add)