Geek Answers Handbook

What is the most efficient way to sort a list of numbers into alternating sequences with low treble?

Suppose you are given an unsorted list of positive integers, and you want to arrange them so that the elements alternate as: (less than the previous item) (more than the previous item) (less than the previous item), etc. The very first item in the output list may ignore the rule. For example, suppose your list is: 1,4,9,2,7,5,3,8,6.

One correct conclusion would be ... 1,9,2,8,3,7,4,6,5

Another will be ... 3,4,2,7,5,6,1,9,8

Suppose that the list does not contain duplicates, is arbitrarily large and not yet sorted.

What is the most efficient processing algorithm to achieve this?

Now, the standard approach would be to simply sort the list first in ascending order, and then undo items from the ends of the list in alternation. However, I would like to know: is there a more time-efficient way to do this without first sorting the list?

My reason for asking: (read this only if you're interested)

Apparently, this is a question that my sister-boyfriend presents to people at an interview in San Francisco. My sister asked me a question and I immediately came up with a standard answer. This is what everyone answers. However, apparently, one girl came up with a completely different solution that does not require sorting the list, and it seems to work. My sister could not explain this decision to me, but this idea scared me from last night. I would be grateful for any help! Thanks!

+4
2

O (n), .

,

1,4,9,2,7,5,3,8,6
Place 1 at end, current list [1]
4>1 true so place 4 at end, current list [1,4]
9<4 false so place 9 at penultimate position [1,9,4]
2>4 false so place 2 at penultimate [1,9,2,4]
7<4 false so place 7 at penultimate [1,9,2,7,4]
5>4 true so place 5 at end [1,9,2,7,4,5]
3<5 true so place 3 at end [1,9,2,7,4,5,3]
8>3 true so place 8 at end [1,9,2,7,4,5,3,8]
6<8 true so place 6 at end [1,9,2,7,4,5,3,8,6]

, , , , , .

Python

A=[1,4,9,2,7,5,3,8,6]
B=[]
for i,a in enumerate(A):
    if i==0 or (i&1 and a>B[-1]) or (i&1==0 and a<B[-1]):
        B.insert(i,a)
    else:
        B.insert(i-1,a)
print B
+8

. .

, nums , nums .

nums   = [list of numbers]

if nums[0] < nums[1]: last_state = INCREASING else: last_state = DECREASING

for i = 2 to len(nums - 1):
   if last_state = INCREASING:
      if nums[i] > nums[i-1]:
        swap (nums[i], nums[i-1])
      last_state = DECREASING
   else
      if nums[i] < nums[i-1]:
        swap (nums[i], nums[i-1])
      last_state = INCREASING

:

i nums , last_state i th i-1 th .

, , 3 . ( ) , i- i-1 - , i-2 - i-1- .

0

More articles:


All Articles