두 개의 정렬 함수 사이의 효율성

Question

정수를 가장 낮은 값부터 가장 높은 값 순으로 정렬 한 다음 다시 낮은 순으로 정렬하는 두 가지 함수를 만들었습니다. 이런 종류의 정렬이 있습니까? 어쨌든 동일한 출력을 생성하는 다음 두 가지 정렬 함수가 있습니다. 나는 그 중 가장 효율적인 것이 무엇인지 궁금 해서요? 어느 개선점이 있습니까?

1. sortMiddleMax1
   • 새로운 역 2
2. sortMiddleMax2
   • 정렬에 의해 목록 단계의 길이 인덱스 1에서 원래
   • 시작의 목록을 분류 만들기 예고 있음
   • 시작 마지막 인덱스에서

2에 의해 단계 0에 나는 처음보다 두 번째가 더 효율적으로 만들기 위해 노력했다. 나는 메모리에 새로운리스트를 만들지 않았고 전체리스트를 밀어 넣는 대신 끝에 추가했다. 이 가정에서 나는 맞습니까?

기능

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 

홈페이지

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) 

당신은 결과 위스콘신 얻을 목록 슬라이스를 사용할 수 있습니다

############# 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] 

Answer 1

당신은 파이썬의 확장 슬라이스를 사용할 수 있습니다. [::2]은 모든 두 번째 요소를 취한다는 것을 의미합니다. [::-2]은 끝에서 두 번째 요소를 취하여 뒤로 작업한다는 것을 의미합니다. 여기에서 첫 번째 슬라이스는 짝수 길이 목록의 경우 0에서 시작하고 홀수 길이 목록의 경우 1에서 시작합니다.

>>> 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] 

Answer 2

출력 thout for 루프 :

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

Answer 3

두 개의 현재 버전이 정확히 동일한 것으로 판단됩니다. 그러나 값을 삭제하고 삽입하는 대신 목록의 값을 가져 오는 슬라이스를 사용하여 둘 모두를 향상시킬 수 있습니다.

각 del

각 insert는 O(N)이며 각의 N/2을하고있는, 그래서 종류의 O(N^2) 될 것입니다. 슬라이스는 O(N)이지만 두 번만 수행하면됩니다. 정렬 시간은 O(N log N)이며, 점근 ​​적으로 우세합니다.

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] 

예 출력 :

>>> 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]