Backjun/1517(Bubble Sot)/python

9637 ワード
テキストリンク
これはBubble Sotのswap回数を探す問題です.
mergeの場合は、まず左から右に区切られた部分から右に区切られた部分を挿入します.
答えは左のリストの数とともに増加します.
swapは何番ですか?
まずbubble sortでswapが何回だったか見てみましょう.私の前の数字の中で私より大きいのは何個ですか.これは確認の問題です.
しかしmerge sortを行うと,この過程は自然に実現する.
6 5 4 3 2 1これなら
最後に.
[45.6][1.23]こうなりました
[4 5 6][2 3]
新しいシナリオ:[1]
これで挿入できます.
1を挿入すると、左側に4、5、6個の自分より大きい数がどれくらいあるかを見つけることができます.
狭い範囲の
三二一にあります.
[3][2]/[1]はこのように分離して統合する.
このとき,前面に2より大きい数3,左側に1つの数がある.
[2 3]/[1]
これにより、1より大きい数字が左の数字の並びになります.
この方法で得ることができます.しかも同じ場合はswapはできません.
mergeでは、比較する部分には、等号をつけることに少し注意する必要があります.

from sys import stdin
import sys
sys.setrecursionlimit(10**9)


answer =0 
def merge(left, mid, right, a, tmp):
    global answer
    if left >= right:
        return
    i = left
    j = mid +1
    p = left

    
    while 1:
        if a[i]<=a[j]: # 같을 때!! 이렇게 해서
            tmp[p] = a[i]
            p+=1
            i+=1
        else:
            tmp[p] = a[j]
            p+=1
            j+=1
            answer  += (mid- i + 1)
        
        # 밀어 넣기
        if i >mid:
            while j<=right:
                tmp[p] = a[j]
                p+=1
                j+=1
                break
            break
        
        if j>right:
            while i<=mid:
                tmp[p] = a[i]
                p+=1
                i+=1
            break
    
    # 복사하기
    for w in range(left, right+1):
        a[w] = tmp[w]
    
        

def merge_sort(left : int, right : int, a, tmp):
    if left >=right:
        return
    
    mid = (left + right)//2
    
    merge_sort(left, mid, a, tmp) # left side
    merge_sort(mid+1, right, a, tmp) # right side
    merge(left, mid, right, a, tmp) # merge
    
    
if __name__ =='__main__':
    n = int(input())
    li = list(map(int, stdin.readline().split()))
    tmp = [0]*len(li)
    merge_sort(0, len(li)-1, li, tmp)

    print(answer)
CSS grid, flex
NodeでのSequelize操作MySQLソリューション