This week's book giveaway is in the Jobs Discussion forum. We're giving away four copies of Customer Requirements for Developers and have Marcho Behler on-line! See this thread for details.

Rajasekar doesn't seem to understand how the Ranch works: we don't like to see people handing out answers to homework questions. Rather, we like to help people learn how to do the work themselves. Luckily, he didn't understand the question, so he didn't ruin your opportunity to learn.

OK, Ankur, let's begin: what sorting algorithms have you talked about in class or read about in your text? Which one did you try to implement and fail?

This is basically the algorithm called "bubblesort", and yes, it's quite inefficient: the number of comparisons and swaps it does is proportional to the square of the array size N , which makes it very slow for large arrays.

By the way: although you are asking about a sort in "reverse" order, this sorts numbers in what I think of as the "forward" order -- increasing from smaller to larger. Do you know how to modify it to sort in the other direction?

There are other more efficient sorting algorithms: quicksort, mergesort, heapsort, Shell sort. All of these do a factor of ln(N)/N fewer operations, where ln() is the natual logarithm. Did you learn anything about any of these? The problem is that although they're all more efficient, they're also considerably more complex and tricky to code.

I know all algorithms but I have never heard "Natural Algorithm".. Any ways I am putting all the code What I have code till now...... Yes One more thing to add is that my problem was originally

"SOrt an array in reverse order without taking any other array or any standard JAVA API's"

I know this is not the best algorithm... but according to my constraints I think that this is best... Now I left upto ranchers what that have opinion on this program and if is possible then I also request you to suggest me where I can improve the efficiency of this Algorithm.....

One more thing I know that is Upto 6-7 Elements this is the best known algorithm for sorting .... ya but this is also true that after 6-7 elements this can be worst as the number of elements going to be large as 10000 and more.....

Now pls suggest me best suited algorithm followed by my Constraints....

"SOrt an array in reverse order without taking any other array or any standard JAVA API's"

I have some different objective.... as Ernest Friedman-Hill suggested me that this is very time consuming algorithm.......

otherwise problem has been solved....

its very easy really, I had a pretty hard time too when i first had to do

this.

hope this helps..

-Justin-

I didn't get you by this statement... my problem is still there........ code is still very much time consuming....... need some improved algorithm with my constraints...

Sort an array in reverse order without taking any other array or any standard JAVA API's

Not "natural algorithm", but natural logarithm, the inverse of the exponential function. It's a function that increases very slowly with N, so that N*ln(N) is much smaller than N*N for large(ish) values of N.

Regarding eliminating the "reverse" function -- yes, good. Sorting in one order, then reversing, was pretty silly.

In any case: what I'm trying to tell you is that you can't improve bubble sort much -- that's just how it works. If you want a considerably better sort, then you need to use a better algorithm, one that works in an entirely different way. If, as you say, you "know all algorithms", then you should know that they're all superior to bubble sort.

And ignore Justin -- he apparently also doesn't understand what you're trying to do. Read the questions carefully, please, people, before answering!

Sort an array in reverse order without taking any other array or any standard JAVA API's

I agree that you have "reversed" the array BUT have you "sorted" it? The example that you took was ALREADY sorted. Here, we are talking about an array that will initially be "unsorted". Hope, now you understand the question at hand.

Hmm, Ernest I was wondering, is a quick sort solution possible without maintaining two temporary lists or arrays? (another part of Ankur's restrictions - the use of arrays at least.) I don't have my data algorithm books to hand at work, so I was just curious.

It may well be possible, but would it be clean and more importantly, efficient?

Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802

posted

0

ohhhh!!! ok, so...

say you have the array {4,3,1,2,5}

instead of sorting it like {1,2,3,4,5)

you want to sort it like {5,4,3,2,1)

am I right?

use a selection sort.

for(int i = 0; i<array.length-1;i++) { int Max = i; for (int j = i + 1; j<array.length; j++) { if(array[j] > array[Max]) Max = array[j]; }

What "updates" are you expecting, exactly? I told you if you want a better sort, you need to use a better algorithm. You claimed to know all about these algorithms. Therefore, the ball is in your court. We're waiting for you to show us your quicksort implementation!