Sorting Lists

Weekly Challenge 197

Challenge, My solutions

Task 1: Move Zero

Task

You are given a list of integers, @list.

Write a script to move all zero, if exists, to the end while maintaining the relative order of non-zero elements.

My solution

This is probably the most straight forward task on the year! Outside the boiler plate code, my Python solution has only three statements, and only two statements in Perl. Both could be done in a single statement, but this reduces readability for no gain.

I generate a list called solutions that has all the non zero numbers from the original list, appended by all the zero numbers. This ensures that order of the non-zero numbers remains in the correct order.

Examples

$ ./ch-1.py 1 0 3 0 0 5
1, 3, 5, 0, 0, 0

$ ./ch-1.py 1 6 4
1, 6, 4

$ ./ch-1.py 0 1 0 2 0
1, 2, 0, 0, 0

Task 2: Wiggle Sort

Task

You are given a list of integers, @list.

Write a script to perform Wiggle Sort on the given list. Wiggle sort would be such as list[0] < list[1] > list[2] < list[3]….

My solution

On the other hand, my whiteboard got a bit of a work out in solving this one. It is apparent that not all lists can produce a working solution, 1, 2, 2 being an obvious one.

This is the approach I took in solving the change:

1. list is a reserved word in Python, so I chose the value n. The Perl solution used @list.
2. Sort the list numerical, in reverse order (i.e. n[0] is the largest number).
3. Split the list in two, big_n and small_n. If there is an odd number of elements, small_n will have the median number.
4. Use zip_longest (from Python's itertools) or mesh (from Perl's List::Util) to merge the lists together, taking values from big_n and small_n for each iteration. I also remove the None value (undef in Perl) in the case where there is an odd number of elements.
5. Iterate through the list to check there are not two adjacent values that are equal. Such as case would fail both the greater than and the less that checks. If this occurs, I display an error message.
6. Print the result.

Examples

$ ./ch-2.py 1 5 1 1 6 4
1, 6, 1, 5, 1, 4

$ ./ch-2.py 1 3 2 2 3 1
2, 3, 1, 3, 1, 2