Sorting Arrays: Largest Value in Middle

Arrays

  • (2 Pages)
  • +
  • 1
  • 2

18 Replies - 3554 Views - Last Post: 14 July 2010 - 06:38 PM Rate Topic: -----

#1 adhish94  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 4
  • View blog
  • Posts: 45
  • Joined: 12-July 10

Sorting Arrays: Largest Value in Middle

Posted 14 July 2010 - 03:33 AM

Write a program to do the following:

Input n integers in an array of size n.

Rearrange these integers in the following manner:
- Put the maximum value in the centre of the array
- Next largest value to its right
- Next largest value to its left, and so on.

Example:

Input- 1, 3, 5, 9, 4, 7; Output- 1, 3, 5, 9, 7, 4, 2

I wrote this code:


class sort
    {
        public static void main(int n)throws IOException
        {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int arr[] = new int[n];
            for(int i=0; i<n; i++)
            {
                arr[i] = Integer.parseInt(br.readLine());
            }
            int g = arr[0];
            int it = 0;
            int loc = 1;
            sort: for(int i=0; i<n; i++)
            {
                if(arr[i] > g && i != loc) g = arr[i];
            }
            if(n%2 != 0)
            {
                it++;
                int c = (n+1) / 2;
                int arr[c] = g;
                if(it%2 != 0) n += 2;
                if(it%2 == 0) n -= 3;
                loc = i;
            }
            else if(n%2 == 0)
            {
                System.out.println("Array length is even");
                System.exit(1);
            }
            if(it <= arr.length) continue sort;
            for(int i=0; i<arr.length; i++) System.out.println(a[i] + " ");
        }
}




When I compiled it, it said: ']' expected at line number 22. Please temme how to resolve this error. And would this code sort the array in the desired manner?

This post has been edited by adhish94: 14 July 2010 - 04:02 AM


Is This A Good Question/Topic? 0
  • +

Replies To: Sorting Arrays: Largest Value in Middle

#2 eZACKe  Icon User is offline

  • Garbage Collector

Reputation: 120
  • View blog
  • Posts: 1,278
  • Joined: 01-June 09

Re: Sorting Arrays: Largest Value in Middle

Posted 14 July 2010 - 05:47 AM

The problem I'm noticing is this:

Towards the top of your main method you have this:

int arr[] = new int[n];



The a little bit further down(line 22) still within the main method you have this:
int arr[c] = g;



You will get an error on line 22 because you have a duplicate local variable. arr is initialized at the top of the main method, so it shouldn't be again further down. You just want:

arr[c] = g;



To go on to your next question, no this code is not going to work. You have further errors which I think are possibly just a result of you messing up your logic a little bit. Take a closer look at this line:
loc = i;



Where is i coming from? You have an error there because i cannot be resolved. Was this suppose to be part of the above for loop perhaps?

Also, here:
System.out.println(a[i] + " ")



What is a? I'm assuming you meant arr?


Hope this helps!
Was This Post Helpful? 0
  • +
  • -

#3 adhish94  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 4
  • View blog
  • Posts: 45
  • Joined: 12-July 10

Re: Sorting Arrays: Largest Value in Middle

Posted 14 July 2010 - 06:58 AM

Ohh yes, I realized my mistakes; they were just silly. The new code:


import java.io.*;
class sort
    {
        public static void main(int n)throws IOException
        {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int arr[] = new int[n];
            int i;
            for(i=0; i<n; i++)
            {
                arr[i] = Integer.parseInt(br.readLine());
            }
            int g = arr[0];
            int it = 0;
            int loc = 1;
            sort: for(i=0; i<n; i++)
            {
                if(arr[i] > g && i!= loc) g = arr[i];
            }
            if(n%2 != 0)
            {
                it++;
                int c = (n+1) / 2;
                arr[c] = g;
                if(it%2 != 0) n += 2;
                if(it%2 == 0) n -= 3;
                loc = i;
            }
            else if(n%2 == 0)
            {
                System.out.println("Array length is even");
                System.exit(1);
            }
            if(it <= arr.length) continue sort;
            for(int i=0; i<arr.length; i++) System.out.println(arr[i] + " ");
        }
}




Now it gives an error at line 34, saying "undefined label: sort". And if all these compile-time errors in the code are resolved, will the code do what it is supposed to do (sorting), I mean, is the logic of the program correct?
Was This Post Helpful? 0
  • +
  • -

#4 eZACKe  Icon User is offline

  • Garbage Collector

Reputation: 120
  • View blog
  • Posts: 1,278
  • Joined: 01-June 09

Re: Sorting Arrays: Largest Value in Middle

Posted 14 July 2010 - 07:56 AM

From what I can tell, your approach is not going to work. I have a question for you though: are you allowed to use ArrayLists? I believe it would be a lot easier this way.

Here's an algorithm I thought up (no code, just an algorithm to help you get going):

-Get the input and put them into an array list.
-Sort the array list of ints.
-Get the size and find out if it is even or odd.
-Assign values to variables right and left, right being the size and left being 0.
-Put the contents of the sorted array list into another array list.
-If the sorted arraylists size is even, then put the first element in right, if it's odd put the first element in left.
-Increment left and decrement right after each iteration.

So let me draw this out as well:

Say you take in 1, 3, 5, 9, 4, 7.
The sorted version of this is: 1, 3, 4, 5, 7, 9.
It's even so : - - - - - 1
Next: 3 - - - - 1
Next: 3 - - - 4 1
Next: 3 5 - - 4 1
Next: 3 5 - 7 4 1
Next: 3 5 9 7 4 1

That is sorted how you wanted it because if you do it by hand you'd put 9 in the middle, 7 on the right, 5 on the left, 4 on the right, 3 on the left, and 1 on the right.


Hope this helps!
Was This Post Helpful? 0
  • +
  • -

#5 adhish94  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 4
  • View blog
  • Posts: 45
  • Joined: 12-July 10

Re: Sorting Arrays: Largest Value in Middle

Posted 14 July 2010 - 08:13 AM

Really thanks for your effort, but we havn't covered arrayLists in school yet, so the teacher expects us to write the code using some other logic! But perhaps I can implement your logic into the code without using arrayList; I don't quite see what difference it would make if we use a sorted array here rather than an arrayList. Lemme try.
Was This Post Helpful? 0
  • +
  • -

#6 eZACKe  Icon User is offline

  • Garbage Collector

Reputation: 120
  • View blog
  • Posts: 1,278
  • Joined: 01-June 09

Re: Sorting Arrays: Largest Value in Middle

Posted 14 July 2010 - 08:16 AM

I see, well that is a problem then haha.

But yes you could probably manage a similar algorithm using a normal array, though it will require a bit more code.

Just for future reference though, if you ever want to read up on using ArrayLists:
http://www.java2s.co...__ArrayList.htm
Was This Post Helpful? 0
  • +
  • -

#7 adhish94  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 4
  • View blog
  • Posts: 45
  • Joined: 12-July 10

Re: Sorting Arrays: Largest Value in Middle

Posted 14 July 2010 - 08:27 AM

Okay, and thanks for the help!
Was This Post Helpful? 0
  • +
  • -

#8 eZACKe  Icon User is offline

  • Garbage Collector

Reputation: 120
  • View blog
  • Posts: 1,278
  • Joined: 01-June 09

Re: Sorting Arrays: Largest Value in Middle

Posted 14 July 2010 - 09:06 AM

Glad I could help, if you need further assistance just let me know.
Was This Post Helpful? 0
  • +
  • -

#9 adhish94  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 4
  • View blog
  • Posts: 45
  • Joined: 12-July 10

Re: Sorting Arrays: Largest Value in Middle

Posted 14 July 2010 - 09:17 AM

As you'd said, I wrote the code:


import java.io.*;
class sortArray
    {
        public static void main(int n)throws IOException
        {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int arr[] = new int[n];
            int i;
            for(i=0; i<n; i++) arr[i] = Integer.parseInt(br.readLine());
            int l = 5;
            int p;
            for(i=0; i<n; i++)
            {
                for(int j=i; j<n; j++)
                {
                    if(arr[i] > arr[j])
                    {
                        arr[i] = arr[j];
                        p = j;
                    }
                    int t = arr[i];
                    arr[i] = arr[p];
                    arr[p] = t;
                }
            }
            boolean even;
            if(n%2 == 0) even = true;
            else even = false;
            int a[] = new int[n];
            for(i=0; i<n; i++) a[i] = arr[i];
            if(even == true) 
            {
                a[n--] = arr[i += 2];
                a[0++] = arr[(i+1) += 2];
            }
            if(even == false)
            {
                a[0++] = arr[i += 2];
                a[n--] = arr[(i+1) += 2];
            }
                
        }
    }




But it gives an error during compilation: "unexpected type" at line 34. Please explain.
Was This Post Helpful? 0
  • +
  • -

#10 eZACKe  Icon User is offline

  • Garbage Collector

Reputation: 120
  • View blog
  • Posts: 1,278
  • Joined: 01-June 09

Re: Sorting Arrays: Largest Value in Middle

Posted 14 July 2010 - 09:44 AM

Well before we get to the error you're having, can you explain to me what you are doing in this line?:
for(i=0; i<n; i++) a[i] = arr[i];



You are putting every element in arr into a in the same order. Is there a reason you are doing this? Which part of my algorithm above made you perform this step?
Was This Post Helpful? 0
  • +
  • -

#11 adhish94  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 4
  • View blog
  • Posts: 45
  • Joined: 12-July 10

Re: Sorting Arrays: Largest Value in Middle

Posted 14 July 2010 - 09:48 AM

Yeah, for that reason only. I'm putting the contents of the sorted array into another array.
Was This Post Helpful? 0
  • +
  • -

#12 eZACKe  Icon User is offline

  • Garbage Collector

Reputation: 120
  • View blog
  • Posts: 1,278
  • Joined: 01-June 09

Re: Sorting Arrays: Largest Value in Middle

Posted 14 July 2010 - 10:03 AM

Well the easier way would be to not put the elements into your "a" array unless you are putting them in the correct position.

So lets' look at it this way: You have a sorted array "arr". You want to put things into the right and the left side. Let's try having actual variables for right and left instead of relying on constants like "0".

Here's what I wrote up, with comments to walk you through.

            int a[] = new int[n];
            int right = n;//right side is the size of the array
            int left = 0;//left side is the first element
            
            for(i=0; i<n; i++).//lets loop through the whole array 1 element at a time 
            {
                   if(even == true) //if it's even...
                   {
                        a[right] = arr[i];//put the first element into the right side
                         a[left] = arr[i+1];//put the next into the left
                   }
                   if(even == false)//if it's odd...
                   {
                         a[left] = arr[i];//put the first element into the left side
                         a[right] = arr[i+1];//put the next into the right
                   }
            
            i++;//we've already used the next i, so we need to increase it again here so next time through the loop we'll be at correct element
            right--;//decrement right
            left++;//increment left
            }




This is pretty much the exact code you wrote, with minor fixes. Do you understand exactly what's going on?

This post has been edited by eZACKe: 14 July 2010 - 10:06 AM

Was This Post Helpful? 0
  • +
  • -

#13 adhish94  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 4
  • View blog
  • Posts: 45
  • Joined: 12-July 10

Re: Sorting Arrays: Largest Value in Middle

Posted 14 July 2010 - 10:07 AM

Yeah, understanding it really exactly! :innocent:

Thank you again!
Was This Post Helpful? 0
  • +
  • -

#14 eZACKe  Icon User is offline

  • Garbage Collector

Reputation: 120
  • View blog
  • Posts: 1,278
  • Joined: 01-June 09

Re: Sorting Arrays: Largest Value in Middle

Posted 14 July 2010 - 10:13 AM

No problem, glad I can help.

Here's a little heads up though: I don't know if your teacher or whoever would allow you to use this, but there's a much easier way to sort an array. Using:

Arrays.sort(arr);



In order to use this you just have to have this import statement:
import java.util.Arrays;


Was This Post Helpful? 0
  • +
  • -

#15 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2069
  • View blog
  • Posts: 4,307
  • Joined: 11-December 07

Re: Sorting Arrays: Largest Value in Middle

Posted 14 July 2010 - 03:26 PM

Here's my attempt. I've kinda cheated and hard coded an array in reverse order, but I think that's the but you were OK with.

I've implemented it as per your original specification. I start off in the center and work my way outside. First, I calculate and store my center point. Then the loop calculates an offset that increases by 0.5 per number. (or because I'm working in ints 1 1 2 2 3 3 4 4.....) I also have a ariable sgn which flips between 1 and -1 to change sides from the center.

import java.util.Arrays;


public class FunnyNumberSorter {
	
	public static void main(String[] args) {
		
		int[] n = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};	
		int[] sorted = new int[n.length]; 
	
		final int center = (n.length / 2) - 1 + (n.length % 2);
		for(int i = 1, sgn = -1; i <= n.length; i++, sgn *= -1) {
			sorted[center + (sgn*i/2)] = n[i-1];
		}
		
		System.out.println(Arrays.toString(sorted));
		
	}

}

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2