Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# Sort the Array in reverse order

Shaan Shar
Ranch Hand
Posts: 1249
We have to sort the array in reverse order without using any standard JAVA API and also we cann't use any other array...

I tried a lot but got failed...

Required help ....

Early help will be appreciated....

Jesper de Jong
Java Cowboy
Saloon Keeper
Posts: 15485
43
Tell us what you tried and why it failed.

Rajasekar Elango
Ranch Hand
Posts: 105

Shaan Shar
Ranch Hand
Posts: 1249
Thanks,

Rajasekar Elango

Shaan Shar
Ranch Hand
Posts: 1249
Thankx Rajasekar alango,

But still one problem is missing how to sort the array till now you have only reverse back the array but how to sort that???
still missing???

Thankx for early help in Advance....

Ernest Friedman-Hill
author and iconoclast
Marshal
Posts: 24212
35
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?

Shaan Shar
Ranch Hand
Posts: 1249
Ok,

Now I display my code which is as following:

Now my problem is, this algorithm is taking so much iterations which are not needed...
So that's why I require a more prowerfull algorithm....

That's all I really want......

Thankx Ernest Friedman-Hill to recall my memory..

but now can I expect any sort of help regrading improvment of the algorithm.

Ernest Friedman-Hill
author and iconoclast
Marshal
Posts: 24212
35
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.

Shaan Shar
Ranch Hand
Posts: 1249
Yes Ernest Friedman-Hill,

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"

Shaan Shar
Ranch Hand
Posts: 1249
I know that this can be somehow reduced by

changing this code as

I create that method for just a trial .... Otherwise this can directly generate reverse order sorted Array... isn't it........

Need to be some more improved.........

[ April 27, 2006: Message edited by: Ankur Sharma ]

Justin Fox
Ranch Hand
Posts: 802
ok,

you have to have two variables one at 0 and one a array.length.

and the one at 0 increments and the one at array.length decrements.

and until the two variables meet, you keep incrementing and switching as

you go.

so your for loop would look like this..

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

this.

hope this helps..

-Justin-

Justin Fox
Ranch Hand
Posts: 802
the very first one you had would've worked...

but you have to do a for loop to print out each char in the array..

like

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

System.out.print(arr[i]);
}

oh yeah, and putt the int j = arr.length in the for loop right after

int i = 0;

-Justin-

Shaan Shar
Ranch Hand
Posts: 1249
I didn't get you clearly.....

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

Shaan Shar
Ranch Hand
Posts: 1249
Still unresolvable compilation error ...

I mean to say that still my problem is still there...

could you pls more eloborate this one::

the very first one you had would've worked...

but you have to do a for loop to print out each char in the array..

like

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

System.out.print(arr[i]);
}

oh yeah, and putt the int j = arr.length in the for loop right after

int i = 0;

-Justin-

My problem is still there......

Ernest Friedman-Hill
author and iconoclast
Marshal
Posts: 24212
35
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!

Shaan Shar
Ranch Hand
Posts: 1249
Thankx Ernest Friedman-Hill.....

I was really expecting a very gentle reply by this forum... And I got it...

Ernest Friedman-Hill I am still working on this problem but while working I have to know my constraints.....

But meanwhile you generate my interest in "natural logarithm"..

Could you pls eloborate some more on this algorithm....

meanwhile I will get back very soon with my problem solution....
and if any rancher have anything to contribute then he/she can do it....

Thanks for Early help in Advance.....

Shaan Shar
Ranch Hand
Posts: 1249
Sorry Ernest Friedman-Hill,

I got really very mad... I knew this natural logarithm so no need to reply Igot confused that whether is that a new algorithm for sorting...

Sorry for inconvenience....

Justin Fox
Ranch Hand
Posts: 802
yeah, well you say you want to take an array and make it reverse right?

then sort it?...

or just reverse, because reversing it and the sorting the array would be

umm...i tried my for loop as well and it gave me compilation errors too..

so i used a while loop instead...try this code out...

i dont think you need all that log mumbo jumbo..

now if this is not what your doing... then im lost...

cause you quoted...

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

-Justin-

Ranch Hand
Posts: 209
Hey Justin,

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.

Shaan Shar
Ranch Hand
Posts: 1249
I really don't understand what really Justin want to convey.......

Justing will you be more clear and precise from next reply....

That makes me confuesd over & over everytime whenever I read your replies.........

Pls be sure what are you replying and for what are you going to reply......

Hope next time I will get more precise solutions......

well yes Shyama.. now you can be more on this reply....

have you some more idea...

Shaan Shar
Ranch Hand
Posts: 1249
Hey no updates from a long time...

I am waiting for new updates....

Ernest Friedman-Hill
author and iconoclast
Marshal
Posts: 24212
35
Ignore Justin. He was trying to show you how to reverse the array, not how to sort it in reverse order.

As far as waiting for new updates: we're waiting to see your implementation of quicksort!

Jody Brown
Ranch Hand
Posts: 43
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
Posts: 802
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];
}

int temp = array[Max];
array[Max] = array[i];
array[i] = temp;
}

so you will have 4 3 1 2 5 at first right?

so on first loop i will point at 4;

then j will compare each number after that to 4 to find greatest number.

so Max will be 5 right?

so after switch you'll have 5 3 1 2 4

then on the second loop i will point at 3.

and Max will be 4.

so after you switch, you will have 5 4 1 2 3.

then after next loop you will have 5 4 3 2 1.

now if this isn't what you want to do...

owell..

-Justin-

Justin Fox
Ranch Hand
Posts: 802
and sorry for the confusion, I just wasn't paying good enough attention i guess..

-Justin-

Ernest Friedman-Hill
author and iconoclast
Marshal
Posts: 24212
35
Originally posted by Justin Fox:

use a selection sort.

But we started out with a working bubble sort, and he was asking about something more efficient. Selection sort has the same performance!

Ernest Friedman-Hill
author and iconoclast
Marshal
Posts: 24212
35
Originally posted by Jody Brown:
His a quick sort solution possible without maintaining two temporary lists or arrays?

This is not only possible, but traditional. Quicksort works in-place.

Jody Brown
Ranch Hand
Posts: 43
Right, just found it. Got to love quiet Fridays. :-)

Justin Fox
Ranch Hand
Posts: 802
lol the prof gonna clock your programs time it takes to run?

didn't think so...

he asked how to sort the array in reverse order and i showed....

he didn't say "ohhh show me in bubble sort!"

a hole.

-Justin-

Shaan Shar
Ranch Hand
Posts: 1249
Hey I was on leave for three days... as Ist May is celebreated as "Labour Day" So there was leave on this monday...

But anyways I am now going to work on any other efficient algorithm....

Till then I expect some more resolutions over this problem.....

Early Birds are Never reflected

Shaan Shar
Ranch Hand
Posts: 1249
No solutions till now....More waiting for solution

no replies... waiting for early replies....

Early Birds are Never reflected
[ May 04, 2006: Message edited by: Ankur Sharma ]

Shaan Shar
Ranch Hand
Posts: 1249