Sort the Array in reverse order

[Shaan Shar]

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 ....

Thanks in Advance..
Early help will be appreciated....

[Jesper de Jong]

Tell us what you tried and why it failed.

[Rajasekar Elango]

public class ArrayReverse {
 
public static void main(String[] args) {
char arr[] = {'r','a','j','a', 's', 'e', 'f'};

int j = arr.length - 1;
for(int i = 0 ; i < j; i++, j--){
char t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}

System.out.println(Arrays.toString(arr));
}
}

[Shaan Shar]

Thanks,

Rajasekar Elango

[Shaan Shar]

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]

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]

Ok,

Now I display my code which is as following:

 [B]public static int[] sortArray(int arr[]) {
for (int i = 0; i < arr.length; i++) {
for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
int t = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = t;
}
}
return arr;
}[/B]   

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.



Thanks for early reply....

[Ernest Friedman-Hill]

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]

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"

[B]public class Sample {
public static void main(String[] args) {
int arr[] = { 1, 3, 2, 7, 9, 5, 6, 11, 12, 54, 0, 3, 3 };
arr = sortArray(arr);
arr = reverse(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
public static int[] sortArray(int arr[]) {
for (int i = 0; i < arr.length; i++) {
for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
int t = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = t;
}
}
return arr;
}
public static int[] reverse(int arr[]) {
int j = arr.length - 1;
for (int i = 0; i < j; i++, j--) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
 
return arr;
}
}[/B]

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]

I know that this can be somehow reduced by

changing this code as

 
public class Sample {
public static void main(String[] args) {
int arr[] = { 1, 3, 2, 7, 9, 5, 6, 11, 12, 54, 0, 3, 3 };
arr = sortArray(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
public static int[] sortArray(int arr[]) {
for (int i = 0; i < arr.length; i++) {
[B]for (int j = i; j > 0 && arr[j - 1] < arr[j]; j--)[/B] {
int t = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = t;
}
}
return arr;
}
}

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

What you say about this Ernest Friedman-Hill........


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



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

[Justin Fox]

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..

    
public static int[] reverse(int [] array)
{
for(int i = 0; int j = array.length; i<j; i++; j--)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}
return array;
}

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

this.

hope this helps..

-Justin-

[Justin Fox]

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]

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]

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]

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]

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]

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]

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

about retarded..

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..

    
public class A
{
public static void main (String [] args)
{
int[] array = {1,4,2,6,7};
int i = 0;
int j = array.length-1;
int temp = 0;
for (int k = 0; k<array.length;k++)
{
System.out.println(array[k]);
}
 

 
while(i < j)
{
 
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
 
}
 
for (int k = 0; k < array.length; k++)
{
System.out.println(array[k]);
}
 
}
}

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-

[Shyam Prasad Murarka]

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]

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]

Hey no updates from a long time...

I am waiting for new updates....

[Ernest Friedman-Hill]

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]

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]

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]

and sorry for the confusion, I just wasn't paying good enough attention i guess..

-Justin-

[Ernest Friedman-Hill]

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]

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]

Right, just found it. Got to love quiet Fridays. :-)

[Justin Fox]

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]

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]

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]

No updates till now...

[Ernest Friedman-Hill]

Ankur --

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!