# Reorder list such that each element is followed by the value closest to it

I just started playing with Python and was hoping to get some feedback regarding the quality of the following snippet. Does this look like proper Python? What would you change? Is this small script well structured?

Quick description of functional goal: reorder list such that each element is followed by the value closest to it, starting from 20 (AKA shortest-seek-first algorithm).

example: [15, 24, 12, 13, 48, 56, 2]
becomes: [24, 15, 13, 12, 2, 48, 56]

better example: [22, 19, 23, 18, 17, 16]
becomes: [19, 18, 17, 16, 22, 23]

fcfs_working = [15, 24, 12, 13, 48, 56, 2]
fcfs_track = []
track_number = 20
while len(fcfs_working) > 0:
track_number = min(fcfs_working, key=lambda x:abs(x-track_number))
fcfs_working.remove(track_number)
fcfs_track.append(track_number)

-

## migrated from stackoverflow.comOct 24 '11 at 2:17

This question came from our site for professional and enthusiast programmers.

add comment

## 3 Answers

while len(fcfs_working) > 0:


is the same as

while fcfs_working:

-
@GarethRees, you're right. I don't recall what I was thinking at the time. –  Winston Ewert Nov 20 '12 at 14:58
add comment

From the algorithmic perspective, I'd like to suggest another solution (regardless to Python as a language).

Here goes:

let's assume that all items in the given array are different. the other case has a similar solution, so let's focus on the algorithm itself.

1. Find the nearest number, in terms of distance, from the array to the given external number (20).
2. sort the given array.
3. find the value in (1) in the array. it can be done using a binary search.
4. now, to the main point: the next value would be either to the left of the current value or to the right of the current value, since the distance is now between the next value to the current one, and the array is sorted (!).
5. so all you have to do is to hold two additional indexes: inner-left and inner-right. these indexes represent the inner boundaries of the "hole" that is being created while constructing the new list.

Demonstration:

original array:

[22, 19, 23, 18, 17, 8]


sorted:

[8, 17, 18, 19, 22, 23]


first element is 19, since abs(20-19) = 1 is the nearest distance to 20.
let's find 19 in the sorted array:

[8, 17, 18, 19, 22, 23]
^


now the next element would be either 18 or 22, since the array is already sorted:

[8, 17, 18, 19, 22, 23]
?  ^   ?


so now we have those inner-left and inner-right indexes, let's label them as "il" and "ir".

[8, 17, 18, 19, 22, 23]
il  ^  ir

result list: [19]


since 18 is closer to 19 than 22, we take it, and shift il to the left:

[8, 17, 18, 19, 22, 23]
il  ^       ir

result list: [19, 18]


again, now 17 is closer to 18 than 22

[8, 17, 18, 19, 22, 23]
il  ^          ir

result list: [19, 18, 17]


now 22 is closer to 17 than 8, so we'd shift the right-index:

[8, 17, 18, 19, 22, 23]
il             ^   ir

result list: [19, 18, 17, 22]


and the rest is obvious.

Again, this has nothing to do with Python in particular. It's purely an algorithm to be implemented in any language.

This algorithm takes O(n log(n)) in time, while the one suggested by the original poster takes O(n^2) in time.

-
add comment

I'm not familiar with the shortest-seek-first algorithm. However, it may work to calculate the distances of each number in the list from the current position, sort that and then output the results. Consequently:

working = [15, 24, 12, 13, 48, 56, 2]
position = 20
distances = [(abs(position-x), x) for x in working]
>> [(5, 15), (4, 24), (8, 12), (7, 13), (28, 48), (36, 56), (18, 2)]
distances.sort()
>> [(4, 24), (5, 15), (7, 13), (8, 12), (18, 2), (28, 48), (36, 56)]
[x[1] for x in distances]
>> [24, 15, 13, 12, 2, 48, 56]

-
not working as expected, for example: working = [15, 24, 12, 13, 25, 56, 2] results with [24, 15, 25, 13, 12, 2, 56] –  Ron Klein Nov 24 '12 at 16:42
add comment