programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Code review for a sorting algorithm

Sergiu Dobozi
Ranch Hand
Posts: 107
2
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:

Liutauras Vilda
Sheriff
Posts: 4923
334
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.

Sergiu Dobozi
Ranch Hand
Posts: 107
2
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.

Liutauras Vilda
Sheriff
Posts: 4923
334
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.

Sergiu Dobozi
Ranch Hand
Posts: 107
2
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.

Junilu Lacar
Sheriff
Posts: 11494
180
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.

Sergiu Dobozi
Ranch Hand
Posts: 107
2
I wish you a long stay and many lessons to be learnt on this forum, Indu.

Sergiu Dobozi
Ranch Hand
Posts: 107
2
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.

Junilu Lacar
Sheriff
Posts: 11494
180
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.

Piet Souris
Master Rancher
Posts: 2044
75
Just for fun, a two (or four) liner:

 Don't get me started about those stupid light bulbs.