Forums Register Login

Code review for a sorting algorithm

+Pie Number of slices to send: Send
I cooked up an algorithm that seems to work initially but fails a hidden test on Code Fights. Can you give me a hint as to what's wrong?
Here is the complete (this time) problem statement.
Some people are standing in a row in a park. There are trees between them which cannot be moved. Your task is to rearrange the people by their heights in a non-descending order without moving the trees.

Example

For a = [-1, 150, 190, 170, -1, -1, 160, 180], the output should be
sortByHeight(a) = [-1, 150, 160, 170, -1, -1, 180, 190].

Input/Output

   [time limit] 3000ms (java)

   [input] array.integer a

   If a[i] = -1, then the ith position is occupied by a tree. Otherwise a[i] is the height of a person standing in the ith position.

   Constraints:
   5 ≤ a.length ≤ 15,
   -1 ≤ a[i] ≤ 200.

   [output] array.integer

   Sorted array a with all the trees untouched.

My implementation:

+Pie Number of slices to send: Send
 

Sergiu Dobozi wrote:Your task is to rearrange the people by their heights in a non-descending order
...
For a = [-1, 150, 190, 170, -1, -1, 160, 180],
the output should be
sortByHeight(a) = [-1, 150, 160, 170, -1, -1, 180, 190].


Let's understand what is being asked first. How do you know this output you showed is correct?

For me looks, that 170, -1, ... is descending, while you are asked to sort in non-descending.
+Pie Number of slices to send: Send
 

Liutauras Vilda wrote:

Sergiu Dobozi wrote:Your task is to rearrange the people by their heights in a non-descending order
...
For a = [-1, 150, 190, 170, -1, -1, 160, 180],
the output should be
sortByHeight(a) = [-1, 150, 160, 170, -1, -1, 180, 190].


Let's understand what is being asked first. How do you know this output you showed is correct?

For me looks, that 170, -1, ... is descending, while you are asked to sort in non-descending.



Because -1 should not be moved. It's like a tree. Every other number is like a person, they can be moved around the trees.
+Pie Number of slices to send: Send
Ah, yes, didn't see that, sorry.

Fails on this case: A= {-1, 150, -1, -1, 190, 170, -1, -1, 160, 180, -1}
Output after sorting: [-1, 150, -1, -1, 160, 170, -1, -1, 190, 180, -1]

Write down your internal test cases first to see if you can pass all locally.
+Pie Number of slices to send: Send
 

Liutauras Vilda wrote:Ah, yes, didn't see that, sorry.

Fails on this case: A= {-1, 150, -1, -1, 190, 170, -1, -1, 160, 180, -1}
Output after sorting: [-1, 150, -1, -1, 160, 170, -1, -1, 190, 180, -1]

Write down your internal test cases first to see if you can pass all locally.



Thanks a lot! I wrote a new code and it worked on all test cases.
+Pie Number of slices to send: Send
I just created two new arrays: one as a copy of the original, which I then sorted using Arrays.sort, and another one to hold the results. Then I iterated over the original, moving trees to the results and putting in the next sorted person otherwise. This gave a functional solution that did not mutate the original input array. I think it was about 8 or 9 lines of code.
+Pie Number of slices to send: Send
I wish you a long stay and many lessons to be learnt on this forum, Indu.
+Pie Number of slices to send: Send
 

Junilu Lacar wrote:I just created two new arrays: one as a copy of the original, which I then sorted using Arrays.sort, and another one to hold the results. Then I iterated over the original, moving trees to the results and putting in the next sorted person otherwise. This gave a functional solution that did not mutate the original input array. I think it was about 8 or 9 lines of code.


Your post led me to think in a different way for sure!
Here is my implementation, mine is a little more than 9 lines, hope I got it right.
+Pie Number of slices to send: Send
That's almost exactly what I have. Looks like my primary method was about 9 lines; I extracted some of that to another method so I actually had 19 lines in all, including blank lines and method headers and closing braces.
+Pie Number of slices to send: Send
Just for fun, a two (or four) liner:
Tongue wrestling. It's not what you think. And here, take this tiny ad. You'll need it.
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com


reply
reply
This thread has been viewed 3967 times.
Similar Threads
Sorting Asciibetically
Having trouble with my Sorting Program
Comparing values
NavigableSet Descending Order Haze
Insertion sort - arrayOutOffBoundException.
More...

All times above are in ranch (not your local) time.
The current ranch time is
Mar 28, 2024 15:24:14.