• Post Reply Bookmark Topic Watch Topic
  • New Topic

Code review for a sorting algorithm  RSS feed

 
Sergiu Dobozi
Ranch Hand
Posts: 107
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I wish you a long stay and many lessons to be learnt on this forum, Indu.
 
Sergiu Dobozi
Ranch Hand
Posts: 107
2
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Just for fun, a two (or four) liner:
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!