SWEA 5204連結ソート

質問する

https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AWUYFsQq11kDFAVT#

に答える

マージソートにより,全長の中間値中間値を基準として左右に分割征服を行う.
再帰呼び出しにより,左を左と右に分割し続け,同様に右も左と右に分割し,分割値の長さが1の場合にマージ処理を行う.
マージ中に、左と右の両方が存在する場合は、左の最初の値と右の最初の値を比較して小さな値を追加し、この部分を削除します.リストから直接削除するには時間がかかるため、ポインタを使用して直接削除する必要はありません.次の値を検索できます.
上の過程で、左だけ残っている場合は左を全部付けて、関数を閉じて、右だけ残っていても全部右を付けて、関数を閉じます.
将来の集計ソートに関する内容を整理し、アルゴリズムシリーズにアップロードします.

コード#コード#

def merge(left, right):
    result = []
    # left, right 둘 중 하나라도 존재
    l_idx = 0                                   # 왼쪽 오른쪽을 포인터로 이동하자
    r_idx = 0
    l_check = len(left)                         # 중복 연산을 피하기 위해 왼쪽과 오른쪽의 길이를 미리 구해놓음
    r_check = len(right)
    while l_idx < l_check and r_idx < r_check:  
                                                # left, right 모두 존재
        if left[l_idx] < right[r_idx]:          # 왼쪽이 첫 번쨰 값이 오른쪽의 첫번째 값보다 작으면 result에 추가 후 left 포인터를 1만큼 이동
            result.append(left[l_idx])
            l_idx += 1
        else:
            result.append(right[r_idx])         # 오른쪽의 첫 번쨰 값이 왼쪽의 첫번째 값보다 작으면 result에 추가 right 포인터를 1만큼 이동
            r_idx += 1
                                                # left만 존재
    if l_idx < l_check:
        result.extend(left[l_idx:])             # 왼쪽 값을 전부 result에 추가
    else:                                       # right만 존재
        result.extend(right[r_idx:])            # 오른쪽 값을 전부 result에 추가

    return result

def merge_sort(a):  # 병합 정렬
    global cnt
    # 기본 파트
    if len(a) == 1:
        return a
    # 유도 파트
    else:
        mid = len(a)//2                     # 중간 값 찾기
        left = a[:mid]                      # 중간 값부터 왼쪽
        right = a[mid:]                     # 중간 값부터 오른쪽

        left = merge_sort(left)             # 왼쪽을 계속해서 중간 값으로 나누어서 왼쪽 오른쪽 만들기
        right = merge_sort(right)           # 오른쪽을 계속해서 중간 값으로 나누어서 왼쪽 오른쪽 만들기

        if left[-1] > right[-1]:            # 왼쪽의 마지막이 오른쪽의 마지막 보다 크면 cnt +1
            cnt += 1
        return merge(left, right)           # 합병

T = int(input())
for tc in range(T):
    N = int(input())
    cnt = 0
    arr = list(map(int, input().split()))
    arr = merge_sort(arr)

    print(f'#{tc+1} {arr[N//2]} {cnt}')

結果

涙を流した.
初めてタイムアウトが発生したとき、インデックスとして処理するのではなく、左右の部分をすべてextendに追加し、関数を閉じて解決できると思うのは傲慢な考えです.
したがって,遅くてもpopによる削除はポインタで修正される.さらに時間を短縮するために,2つの関数を1つに統合するプロセスも行った.しかし,時間の減少に比べて可読性の部分がかなり劣っているため,あまり有効ではないと思われ,また関数を2つに分類した.
以前学習した内容ですが、appendでリストの後ろに追加するのにあまり時間がかかりませんが、pop(0)はリストのすべての要素を1つずつ前に引くので、リストのサイズが大きくなると多くの時間がかかることを改めて注意します.したがって,後でpop(0)を用いる際に時間に関する問題を考慮する必要がある場合は,ポインタを直ちに思い出す.