blue271828's misc :-)

マージソート

呼称

概要

マージソートは安定ソートであり、配列を分割統治法により並べ替えるアルゴリズムである。

アルゴリズム

  1. 配列を分割する (通常二等分する)
  2. 分割された各配列で、配列長が1個ならそのまま返し、配列長が2個以上なら再帰的に分割する。
  3. 分割された配列は、統合時に並び替えられる。

実装例

Python 3

def merge_sort(arr):
    arr = arr.copy()
    _merge_sort(arr, 0, len(arr))
    return arr


def _merge_sort(arr, l, r):
    if r - l == 1:
        return
    
    m = (l + r) // 2
    _merge_sort(arr, l, m)
    _merge_sort(arr, m, r)
    _merge(arr, l, m, r)
    

def _merge(arr, l, m, r):
    l_arr = arr[l:m]
    r_arr = arr[m:r]
    
    i = 0
    j = 0
    while i < len(l_arr) and j < len(r_arr):
        if l_arr[i] < r_arr[j]:
            arr[l+i+j] = l_arr[i]
            i += 1
        else:
            arr[l+i+j] = r_arr[j]
            j += 1
    
    while i < len(l_arr):
        arr[l+i+j] = l_arr[i]
        i += 1
    while j < len(r_arr):
        arr[l+i+j] = r_arr[j]
        j += 1

参考文献

Tags

#Ansible (3) #Bash (1) #Docker (1) #Git (2) #Hugo (2) #Molecule (1) #Python (1) #WSLtty (1) #アルゴリズム (4) #ビジネス用語 (1) #プログラミング (1) #位相空間論 (8) #初等数学 (20) #初等関数 (1) #実解析 (1) #幾何学 (3) #微分積分学 (18) #情報理論 (4) #抽象代数学 (14) #数理モデル (2) #数理論理学 (21) #機械学習 (3) #正規表現 (1) #測度論 (3) #特殊関数 (4) #確率論 (18) #組合せ論 (5) #統計学 (12) #線型代数学 (18) #複素解析学 (4) #解析学 (15) #論理学 (6) #順序集合論 (9)