Efficiency between two sorting functions

Question

I have created a two functions which sorts integers from lowest value to highest then back to low. Does this type of sort exist? Anyways, I have the following two sorting functions which I have created which produce the same output. I was wondering which is the most efficient of the two? Are there any improvements I can make to either?

sortMiddleMax1
- Create a new reverse sorted list of original
- Start from index 1 to length of list step by 2
sortMiddleMax2
- Sorts the list in-place
- Start from last index to 0 step by 2

I tried to make the second more efficient than the first. I did not create a new list in memory and I appended to the end instead of pushing the whole list right. Am I correct in this assumption?

Functions

def sortMiddleMax1(aList=None, verbose=False):
  if aList == None or len(aList) < 2:
    return aList
  else:
    sList = sorted(x, key=None, reverse=True)
    if verbose: print sList
    index = 1
    while index < len(sList):
      tmp = sList[index]
      del sList[index]
      sList.insert(0, tmp)
      index+=2
      if verbose: print sList
    return sList

def sortMiddleMax2(aList=None, verbose=False):
  if aList == None or len(aList) < 2:
    return aList
  else:
    aList.sort()
    if verbose: print aList
    index = len(aList)-1
    while index > 0:
      tmp = aList[index]
      del aList[index]
      aList.append(tmp)
      index-=2
      if verbose: print aList
    return aList

Main

x = [1,4,6,8,3,5,7,1,5,8,3,9,2,8]
print '############# sortMiddleMax1 #############'
x1 = sortMiddleMax1(x, True)
print '############# sortMiddleMax2 #############'
x2 = sortMiddleMax2(x, True)

Output

############# sortMiddleMax1 #############
[9, 8, 8, 8, 7, 6, 5, 5, 4, 3, 3, 2, 1, 1]
[8, 9, 8, 8, 7, 6, 5, 5, 4, 3, 3, 2, 1, 1]
[8, 8, 9, 8, 7, 6, 5, 5, 4, 3, 3, 2, 1, 1]
[6, 8, 8, 9, 8, 7, 5, 5, 4, 3, 3, 2, 1, 1]
[5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 3, 2, 1, 1]
[3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 2, 1, 1]
[2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 1, 1]
[1, 2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 1]
############# sortMiddleMax2 #############
[1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 8, 9]
[1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 8, 9]
[1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 9, 8]
[1, 1, 2, 3, 3, 4, 5, 5, 6, 8, 8, 9, 8, 7]
[1, 1, 2, 3, 3, 4, 5, 6, 8, 8, 9, 8, 7, 5]
[1, 1, 2, 3, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4]
[1, 1, 2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3]
[1, 2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 1]

I'm not sure if your definition of the sort is well defined. Would [1,2,3,4,5,10,9,8,7,6] be a valid result? It goes up, then it goes down! If it's not valid, you need to specify exactly how the first and second halves of the output are related. — Blckknght
– Blckknght, Commented Feb 28, 2013 at 2:36
@David I have not timed them. I am not looking for speed as much as I am looking for memory footprint. — Mr. Polywhirl
– Mr. Polywhirl, Commented Feb 28, 2013 at 2:52
@Blckknght I thought about sorting like that at first but I want to evenly spread the lowest values in the left and right. Basically I have the lowest on one end and the second lowest on the other... — Mr. Polywhirl
– Mr. Polywhirl, Commented Feb 28, 2013 at 2:53

John La Rooy · Accepted Answer · 2013-02-28 02:59:35Z

1

You can use Python's extended slicing. [::2] means take every second element. [::-2] means take every second element from the end and work backwards. Here the first slice starts at 0 for even length list and 1 for odd length lists

>>> x = [1, 4, 6, 8, 3, 5, 7, 1, 5, 8, 3, 9, 2, 8]
>>> x = sorted(x)
>>> x[len(x)%2::2] + x[::-2]
[1, 2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 1]

edited Feb 28, 2013 at 2:59

answered Feb 28, 2013 at 2:54

John La Rooy

306k54 gold badges378 silver badges514 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Mr. Polywhirl Over a year ago

Awesome! The slice every 2 is great. Never tried that as I am an aspiring Pythonista.

HYRY · Accepted Answer · 2013-02-28 02:48:39Z

1

You can use list slice to get the result without for loop:

x = sorted([1,4,6,8,3,5,7,1,5,8,3,9,2,8])
x2 = x[::2] + x[1::2][::-1]

answered Feb 28, 2013 at 2:48

HYRY

97.8k28 gold badges197 silver badges192 bronze badges

Comments

Blckknght · Accepted Answer · 2013-02-28 02:59:09Z

1

I suspect your two current versions perform exactly the same. However, they both can be improved by using slices to get at the values in the list, rather than by deleting and inserting values.

Each del and each insert is O(N) and you're doing N/2 of each, so the sort will be O(N^2). Slicing is O(N) as well, but only needs to be done twice. The time taken for the sort O(N log N) will dominate, asymptotically.

def sortMiddle3(aList):
    s = sorted(aList) # sort the provided list

    # now take the even indexed items, followed by the odd indexes in reverse
    if len(s) % 2 == 0: # is the number of items even?
        return s[::2] + s[-1::-2] # if so, the last item has an odd index
    else:
        return s[::2] + s[-2::-2]

Example output:

>>> x = [1,4,6,8,3,5,7,1,5,8,3,9,2,8]
>>> sortMiddle3(x)
[1, 2, 3, 5, 6, 8, 8, 9, 8, 7, 5, 4, 3, 1]

edited Feb 28, 2013 at 2:59

answered Feb 28, 2013 at 2:48

Blckknght

106k11 gold badges135 silver badges188 bronze badges

3 Comments

Blckknght Over a year ago

Oh you're right. I keep forgetting that it's one of the few functions that still does in Python 3 (rather than being a generator). I'll update my code.

Mr. Polywhirl Over a year ago

Great explanation. I forgot to check for even/odd length in my original, but it still worked out.

Blckknght Over a year ago

@Mr.Polywhirl: It's O(2N)*N/2. But even if the multiples of two didn't cancel, you usually ignore constant factors when using Big O notation.

Collectives™ on Stack Overflow

Efficiency between two sorting functions

3 Answers 3

1 Comment

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related