Python練習(マージソート)
Pythonでマージソート
マージソートは配列を二つに分け、各々でソートし、最後にマージしてソートする。
2つに分けた後のソートも同様な処理を再帰させて行うことができる。(分割統治法)
マージソートは同じ値が存在した場合、配列の添字の順を維持することができる。
計算量はO(NlogN)
コード(Python)
#coding: UTF-8 #マージソート def mergesort(x, left, right): if right - left <= 1: return mid = left + (right - left) /2 mergesort(x, left, mid) mergesort(x, mid, right) marge(x, left, mid, right) def marge(x, left, mid, right): n = right - left work = [] iw = 0 il = left ir = mid #二つの配列から小さい方を選ぶ(同じ場合、1つめの配列から選ぶ) while il < mid and ir < right: if x[il] <= x[ir] : work.append(x[il]) iw += 1 il += 1 else: work.append(x[ir]) iw += 1 ir += 1 #選ばれていない要素を一時領域に入れる while il < mid: work.append(x[il]) iw += 1 il += 1 while ir < right: work.append(x[ir]) iw += 1 ir += 1 x[left:left+n] = work print x x = [4,50,3,10,88,39,2,15] mergesort(x, 0, len(x) ) print "-"*30 print x
出力
[4, 50, 3, 10, 88, 39, 2, 15] [4, 50, 3, 10, 88, 39, 2, 15] [3, 4, 10, 50, 88, 39, 2, 15] [3, 4, 10, 50, 39, 88, 2, 15] [3, 4, 10, 50, 39, 88, 2, 15] [3, 4, 10, 50, 2, 15, 39, 88] [2, 3, 4, 10, 15, 39, 50, 88] ------------------------------ [2, 3, 4, 10, 15, 39, 50, 88]