Programming Forums > Application Development > Java

NightShade01 · Apr 29th, 2006, 6:31 PM

Hey everyone. I have to write a method that takes an array or intergers as its only argument. I then must manipulate the values in the array in such a way that the smaller numbers are on one side and the larger number are on the other side.

The example my professor gave was:

x = [19,42,38,-2,17,42,3,18,99,0,19,11]

amount of numbers = 12
random number from group = 19

the array of "x" must then trun into:

x = [1,-2,17,2,18,0,19,38,99,42,19,42]

essentially the middle number 19 is like a kid. Everyone smaller then him to the left everyone bigger to the right (they don't have to be sorted). The only resriction i have is that i can only be in one array and our only hint was that it can be done in about 15 lines of code.

My psuedo code is something like this:

start program
create new array named "x"
fill "x" with 12 random numbers
--not sure how he's moving the numbers--
display the output of the array

has anyone heard of such an alogrith or can someone give me some general clues on how to go about this? I don't want someone to do it for me though otherwise i'll never learn!

-NightShade

jaeusm · Apr 29th, 2006, 7:06 PM

Research sorting algorithms.

lectricpharaoh · Apr 29th, 2006, 7:11 PM

Quote:

Originally Posted by NightShade01

Hey everyone. I have to write a method that takes an array or intergers as its only argument. I then must manipulate the values in the array in such a way that the smaller numbers are on one side and the larger number are on the other side.

The example my professor gave was:

x = [19,42,38,-2,17,42,3,18,99,0,19,11]

amount of numbers = 12
random number from group = 19

the array of "x" must then trun into:

x = [1,-2,17,2,18,0,19,38,99,42,19,42]

Not sure if this is a typo, but you have two 19s with intervening numbers. Since the sequence is random, you must accept that you will sometimes (perhaps quite frequently, if the random range is small and the sequence is large) get duplicates. If a duplicate is chosen as the 'middle' number, it would make sense to put all instances of the duplicate together:

1, -2, 17, 2, 18, 0, 19, 19, 38, 99, 42, 42

Having said that, the simplest way I can think of would be a variant of the bubble sort. Basically, you'd iterate through the array, comparing each value to your middle value. You'd also need to know where it was in relation to this middle value (ie, before or after). If it was smaller, you would 'bubble' it to the left (unless it was already there), and if it was larger, you'd bubble it to the right (again, unless it was already there). If it was equal, you'd need to move it into an adjacent position, but I think you'd find it easier to do this after all the other numbers were handled, though you could make the algorithm a little smarter, and have it shuffle the other elements past all instances of the middle number (this would obviously require more work).

In case you're unfamiliar with what I mean by bubble sort and bubbling, think of it this way: you have a vertical stack of numbers, and the smaller ones rise (or bubble) to the top. Repeat this process enough, and the array becomes sorted. There are lots of variants, and you don't need to move the smallest to the top (you can use whatever comparison criteria you like, so long as you're consistent).

Jimbo · Apr 29th, 2006, 10:49 PM

From the example, this looks really similar to quicksort, only without the recursive calls.

Arevos · Apr 30th, 2006, 5:35 AM

Quote:

Originally Posted by NightShade01

--not sure how he's moving the numbers--

There are several ways to approach the problem of moving numbers in an array. One way is to swap one number with another:

(Toggle Plain Text)

int temp = array[x];
array[x] = array[y];
array[y] = temp;

Another way is to turn the array into a List object, and use the remove and add methods to move the list elements around:

(Toggle Plain Text)

List<Integer> list = Arrays.asList(array);
int temp = list.remove(x);
list.add(y, temp);
array = list.toArray();

Does that help any?

NSchnarr · May 18th, 2006, 10:36 AM

As previously mentioned, you want to use a quicksort algorithm without the recursive calls. THis algorithm uses the first number as the pivot and essentially, everything smaller goes on the left of it, everything bigger goes on the right.
The reason you dont need the recursive calls is that your teacher does not require the array to sort.

How this will work is you take the pivot (call it p), and starting from position 1 (call it n) compare it to p
IF n > p -> leave the number where it is. n = n+1
IF n < p -> shift all number starting from n-1, down to p to the right. and put n where p was. n= n+1.
IF n = p, (you didnt really specify where it needs to go.. but im guessing treat it as n > p.

So an example of this working is:

[5][4][6][11][3][1][7]
[4][5][6][11][3][1][7]
[4][5][6][11][3][1][7]
[4][5][6][11][3][1][7]
[4][3][5][6][11][1][7]
[4][3][1][5][6][11][7]
[4][3][1][5][6][11][7]

As far as i can remmeber, this is how 1 iteration of quicksort works... and will get the job done for you. Hope I helped

NSchnarr

Apr 29th, 2006, 6:31 PM	#1
NightShade01 Programmer Join Date: Oct 2005 Posts: 52 Rep Power: 4	Possible Alogrithm?? Hey everyone. I have to write a method that takes an array or intergers as its only argument. I then must manipulate the values in the array in such a way that the smaller numbers are on one side and the larger number are on the other side. The example my professor gave was: x = [19,42,38,-2,17,42,3,18,99,0,19,11] amount of numbers = 12 random number from group = 19 the array of "x" must then trun into: x = [1,-2,17,2,18,0,19,38,99,42,19,42] essentially the middle number 19 is like a kid. Everyone smaller then him to the left everyone bigger to the right (they don't have to be sorted). The only resriction i have is that i can only be in one array and our only hint was that it can be done in about 15 lines of code. My psuedo code is something like this: start program create new array named "x" fill "x" with 12 random numbers --not sure how he's moving the numbers-- display the output of the array has anyone heard of such an alogrith or can someone give me some general clues on how to go about this? I don't want someone to do it for me though otherwise i'll never learn! -NightShade

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Apr 29th, 2006, 7:06 PM	#2
jaeusm Programmer Join Date: Feb 2006 Location: Columbus, OH Posts: 84 Rep Power: 3	Research sorting algorithms.

Apr 29th, 2006, 10:49 PM	#4
Jimbo Battle Programmer Join Date: Feb 2006 Location: Bellevue, WA, USA Posts: 769 Rep Power: 3	From the example, this looks really similar to quicksort, only without the recursive calls.

May 18th, 2006, 10:36 AM	#6
NSchnarr Newbie Join Date: May 2006 Posts: 28 Rep Power: 0	As previously mentioned, you want to use a quicksort algorithm without the recursive calls. THis algorithm uses the first number as the pivot and essentially, everything smaller goes on the left of it, everything bigger goes on the right. The reason you dont need the recursive calls is that your teacher does not require the array to sort. How this will work is you take the pivot (call it p), and starting from position 1 (call it n) compare it to p IF n > p -> leave the number where it is. n = n+1 IF n < p -> shift all number starting from n-1, down to p to the right. and put n where p was. n= n+1. IF n = p, (you didnt really specify where it needs to go.. but im guessing treat it as n > p. So an example of this working is: [5][4][6][11][3][1][7] [4][5][6][11][3][1][7] [4][5][6][11][3][1][7] [4][5][6][11][3][1][7] [4][3][5][6][11][1][7] [4][3][1][5][6][11][7] [4][3][1][5][6][11][7] As far as i can remmeber, this is how 1 iteration of quicksort works... and will get the job done for you. Hope I helped NSchnarr

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > Java

Possible Alogrithm??