Sorting an array. Fastest way.

[Sanny]

I have an array of int.

It is already sorted.

int[] car = new int[100];

Now I sort it.

After sorting The Value of 1st element is changed array So I need to
sort it again.

I find using binarydearch the position "pos" where the ist elewment
need to go.

Then I do arraycopy to shift all elements by 1 and copy the 1st
element to the "pos" position.

This terchnique takes lots of time.

I want to use linkedlist.

But when I use LinkedList car = new LinkedList();

To access ith element I use

int ii=car.get(i); It gives error saying says Object cannot be copied
to int. How to know the value of ith element in LinkedList.

And Is there an efficient way.

And which Sort is the best for sorting 40 random numbers out of
QuckSort/ MergeSort and Bubble Sort?

Bye
Sanny

 

[Lew]

I have an array of int.

It is already sorted.

int[] car = new int[100];

At this point you have 100 slots for int with no explicit values set, so every
member of the array is set to zero. That is sorted, yes.

Now I sort it.

After sorting The Value of 1st element is changed array So I need to
sort it again.

We need to see a code sample. I don't even understand this sentence - what
exactly happens to the first element, i.e., what exactly is the new value?

It would help to provide an SSCCE:
<http://www.physci.org/codes/sscce.html>

then we could see precisely what values are changing to what values and how.

I find using binarydearch the position "pos" where the ist elewment
need to go.

Then I do arraycopy to shift all elements by 1 and copy the 1st
element to the "pos" position.

This terchnique takes lots of time.

Well, if you sorted the array the first time through, none of this would have
been necessary, assuming I've even understood what "this" is.

I want to use linkedlist [sic].

Just out of curiosity (it doesn't really impact your question), why do you
need LinkedList and not some other List?

But when I use LinkedList car = new LinkedList();

To access ith element I use

int ii=car.get(i); It gives error saying says Object cannot be copied
to int. How to know the value of ith element in LinkedList.

LinkedList, like all Lists, holds objects not primitives. You would need to use

Object ii = car.get( i );

Even better would be to use generics. If you used

List <Integer> car = new LinkedList <Integer> ();

then autounboxing (which is occasionally dangerous) would let you get away
with the assignment directly to an int:

int ii = car.get( i );

And Is there an efficient way.

Efficient to do what exactly, retrieve the value? Insert it? Sort the List?

Characteristics (in big-O terms) of the collection classes are usually
described in the Javadocs for those classes.

And which Sort is the best for sorting 40 random numbers out of
QuckSort/ MergeSort and Bubble Sort?

With only forty ints, the differences between these algorithms shouldn't make
much difference at all.

The speed of each sort depends in part on whether the input is highly sorted
or highly unsorted.

 

[Andreas Leitgeb]

Given an initially sorted collection, the first element is
modified/replaced, and the collection needs to be re-sorted.

For an array, this means the described "algorithm":
Since the expensive part is shifting, it appears obvious that a
collection that allows easy inserting/removal of items may be
better, but unfortunately I think that such structures do not
behave as well with binary search (which requires random index
addressing)

I'm not entirely sure about other possible disadvantages, but
it looks like TreeMap or TreeSet might be an optimal collection
for OP's needs.

LinkedList, like all Lists, holds objects not primitives. You would need to use
Object ii = car.get( i );
Even better would be to use generics. If you used
List <Integer> car = new LinkedList <Integer> ();
then autounboxing (which is occasionally dangerous) would let you get away
with the assignment directly to an int:
int ii = car.get( i );

These remarks of course apply to TreeMap or TreeSet, as well.

 

[Sanny]

I have an array of int.

It is already sorted.

int[] car = new int[100];

At this point you have 100 slots for int with no explicit values set, so every
member of the array is set to zero.  That is sorted, yes.

Just imagine 100 random numbers are there we sort them.

Now we Change the Highest Random number to a new value. Now that new
value need to be ordered at correct place in the sorted array.

For that I use binary search to know position when the new value
should be inserted. But then all other values of arrays has to be
shifted left.

This shifting is taking a lot of time. Since every time the First
Value is changed it has to be adjusted in the sorted array.

I wanted to use List. I found util.LinkedList.

But I do not understand how to get the value of ith element from a
linmked list. It do not support Int. So How will I get integer value
from Object.

And will not these conversion take more time.

Other posibilities are Vectors and TreeMaps But I dont know what they
are and how to use them.

I have to do ordering 100000s of time So it is taking lot of time is
Sorting the Array.

Since the Array is already Sorted I just want some efficient way to
move an item from First place to ith place and shift other elements.

I use ArrayCopy() for this but it is time consuming.

Bye
Sanny

Now I sort it.

After sorting The Value of 1st element is changed array So I need to
sort it again.

We need to see a code sample.  I don't even understand this sentence - what
exactly happens to the first element, i.e., what exactly is the new value?

It would help to provide an SSCCE:
<http://www.physci.org/codes/sscce.html>

then we could see precisely what values are changing to what values and how.

I find using binarydearch the position "pos" where the ist elewment
need to go.

Then I do arraycopy to shift all elements by 1 and copy the 1st
element to the "pos" position.

This terchnique takes lots of time.

Well, if you sorted the array the first time through, none of this would have
been necessary, assuming I've even understood what "this" is.

I want to use linkedlist [sic].

Just out of curiosity (it doesn't really impact your question), why do you
need LinkedList and not some other List?

But when I use LinkedList car = new LinkedList();

To access ith element I use

int ii=car.get(i); It gives error saying says Object cannot be copied
to int. How to know the value of ith element in LinkedList.

LinkedList, like all Lists, holds objects not primitives.  You would need to use

  Object ii = car.get( i );

Even better would be to use generics.  If you used

  List <Integer> car = new LinkedList <Integer> ();

then autounboxing (which is occasionally dangerous) would let you get away
with the assignment directly to an int:

  int ii = car.get( i );

And Is there an efficient way.

Efficient to do what exactly, retrieve the value?  Insert it?  Sort the List?

Characteristics (in big-O terms) of the collection classes are usually
described in the Javadocs for those classes.

And which Sort is the best for sorting 40 random numbers out of
QuckSort/ MergeSort and Bubble Sort?

With only forty ints, the differences between these algorithms shouldn't make
much difference at all.

The speed of each sort depends in part on whether the input is highly sorted
or highly unsorted.

 

[Jeff Higgins]

Sanny wrote:
I have to do ordering 100000s of time So it is taking lot of time is
Sorting the Array.

Are you simply wanting to sort an int[]?
Use java.util.Arrays.sort(int[] a).

import java.util.Arrays;
import java.util.Random;

public class Test {

public static void main(String[] args) {
Random rand = new Random();
int[] array = {0, 1, 2, 3, 4};
System.out.println(Arrays.toString(array));
for(int i = 0; i < 5; i++) {
array = rand.nextInt();
Arrays.sort(array);
System.out.println(Arrays.toString(array)); }}}

Do you want to implement a sort(int[] a) method?
Look in the source of java.util.Arrays
to see a reference implementation.

 

[Martin Gregorie]

Given an initially sorted collection, the first element is
modified/replaced, and the collection needs to be re-sorted.

For an array, this means the described "algorithm":

Since the expensive part is shifting, it appears obvious that a
collection that allows easy inserting/removal of items may be
better, but unfortunately I think that such structures do not
behave as well with binary search (which requires random index
addressing)

I'm not entirely sure about other possible disadvantages, but
it looks like TreeMap or TreeSet might be an optimal collection
for OP's needs.

A TreeMap, which implements a red-black balanced binary tree, will give
reasonable performance with any size of data set. Its performance isn't
degraded by loading pre-ordered data: this is a problem with simple
(unbalanced) unbalanced binary tree algorithms. Red-black trees are
never blindingly fast, but don't have performance black holes either.

Operations on a TreeMap won't be as fast as on an array, but they don't
degrade badly for a small dataset and do become spectacularly fast for
extremely large data sets. When the tree is very small the search
degenerates toward a sequential search, but as the data set grows the
number of key comparisons drops dramatically - it can find a match from
8388608 entries with only 23 key comparisons. The only drawback is that
an amendment that changes the key MUST be a deletion followed by an
insert to maintain the tree's ordering, so an amendment will take
approximately twice as long as a search.

A binary search on an ordered array will be quicker than walking the
tree, but any array insertion involves either resorting the entire array
or moving all higher keys up a cell to make space for the new value.
Deletions and key amendments have similar large overheads for large data
sets.

Finding the insertion point and making the insertion in a tree is much
faster. Same applies to a deletion. A key amendment is simply a deletion
plus an amendment.

 

[Lew]

I have an array of int.
It is already sorted.
int[] car = new int[100];

At this point you have 100 slots for int with no explicit values set, so every
member of the array is set to zero. That is sorted, yes.

Just imagine 100 random numbers are there we sort them.

I have a hard time understanding what you mean by this sentence.

Now we Change the Highest Random number to a new value. Now that new
value need to be ordered at correct place in the sorted array.

For that I use binary search to know position when the new value
should be inserted. But then all other values of arrays has to be
shifted left.

Follow Jeff Higgins advice and resort, or use a Collection that keeps things
in sorted order for you, as Andreas Leitgeib suggested.

This shifting is taking a lot of time. Since every time the First
Value is changed it has to be adjusted in the sorted array.

I wanted to use List. I found util.LinkedList.

There are others, such as ArrayList. Another alternative is the Apache
Commons Collections API.

But I do not understand how to get the value of ith element from a
linmked list. It do not support Int [sic]. So How will I get integer value
from Object.

This was answered in the post you cite below, in the part you cite. I repeat
it in this post as a reminder.

And will not these conversion take more time.

Other posibilities are Vectors and TreeMaps But I dont know what they
are and how to use them.

Read the Javadocs. But don't use Vector.

I have to do ordering 100000s of time So it is taking lot of time is
Sorting the Array.
Since the Array is already Sorted I just want some efficient way to
move an item from First place to ith place and shift other elements.

With an appropriate collection you should delete the desired element, which if
you use java.util.LinkedList takes care of the shift for you,
<http://java.sun.com/javase/6/docs/api/java/util/LinkedList.html#remove(int)>
then add the desired element at the desired location.
<http://java.sun.com/javase/6/docs/api/java/util/LinkedList.html#add(int, E)>

This should be faster than manually shifting elements yourself.

 

[Roedy Green]

I'm not entirely sure about other possible disadvantages, but
it looks like TreeMap or TreeSet might be an optimal collection
for OP's needs.

An array is great for something you sort once and leave alone. A
TreeSet is great for something you keep adding to and want to keep
ordered, particularly a large set since when you add very little needs
to shift position.

 

[Roedy Green]

I wanted to use List. I found util.LinkedList.

But I do not understand how to get the value of ith element from a
linmked list. It do not support Int. So How will I get integer value
from Object.

LinkedList will support the List interface. Have a look in there for a
indexing method. It is pretty slow. It works by wending its way down
the chain.

LinkedList has very slow access, but fast insert and delete.

If you have pointers to the elements where you want to insert rather
than indexes, you can work a lot faster.

Binary search will be impossibly slow on a LinkedList because of the
slow access.

You are better off to use a simple array and do your sliding with
System.arrayCopy.

 

[Eric Sosman]

Just imagine 100 random numbers are there we sort them.

Now we Change the Highest Random number to a new value. Now that new
value need to be ordered at correct place in the sorted array.

You may want a PriorityQueue. Or, if it's really just
a bunch of numbers, write yourself a heap.

 

[Lew]

LinkedList will support the List interface. Have a look in there for a
indexing method. It is pretty slow. It works by wending its way down
the chain.

LinkedList has very slow access, but fast insert and delete.

That's an advantage for the OP. They can delete the obsolete item and insert
the new one relatively quickly. They certainly should not shift elements
manually with LinkedList.

 

[Andreas Leitgeb]

That's an advantage for the OP. They can delete the obsolete item and insert
the new one relatively quickly. They certainly should not shift elements
manually with LinkedList.

That was surely, why the OP came up with it.
(remember? you asked, why he did)

But as I said, the b-search will not "work" with
Lists, therefore the TreeSet is probably better.

But then, the OP showed that he isn't yet comfortable
with generics, and other since-1.5 features, so
probably he rather stick to array-shifting for now,
and study the java-1.5 goodies, before actually using
any other collection-class.

 

[Lew]

That was surely, why the OP came up with it.
(remember? you asked, why he did)

I thought that might be, but their discussion of explicitly shifting elements
gave counter-evidence to that notion.

But as I said, the b-search will not "work" with
Lists, therefore the TreeSet is probably better.

But then, the OP showed that he isn't yet comfortable
with generics, and other since-1.5 features, so
probably he rather stick to array-shifting for now,
and study the java-1.5 goodies, before actually using
any other collection-class.

Generics are not essential to the Collections classes, which came out well
before generics were added to the language. Since array-shifting was the
original problem, the OP might not want to stick with it.

TreeSet will not allow duplicate entries, whereas Lists will. If they don't
need to maintain duplicates, a Set is a good idea, otherwise a LinkedList or
one of the Apache commons collections may solve the problem.

However, given the operations the OP described, there may be no sufficiently
quick solution using Sets or Lists. Eric Sosman's idea to build a heap seems
like the solution.