wiki:PythonExerciseMergeSort

Version 6 (modified by sgk, 13 years ago) (diff)

--

Python:練習問題:マージソート

Python情報 >> Python練習問題

マージソートを行うプログラムを作ってください。

かなり古典的な問題です。こんな問題で、Pythonの練習になるんでしょうか? でも、やってみると案外、人それぞれの答案が出てきて面白いです。 C言語やJavaでやる練習問題はあちこちでみかけます。 Pythonらしい答案を期待したいところです。 Pythonのリスト(配列)の範囲指定機能を使うといいですね。 そうそう。再帰呼び出しを使ってくださいね。 再帰呼び出しを使わないマージソートの練習問題は別に用意しています。

マージソートのアルゴリズムについては、ネット上のあちこちで見かけるので、ここでは語りません。

doctestを含んだスケルトンを置いておきます。 解答例は、敢えてリンクしません。 このページ上部のナビゲーションバーの「Browse Source」の中のどこかにあります。

#!/usr/bin/python
# coding:utf-8

'''マージソート
練習問題「マージソートを作る」。

>>> mergeSort((3, 1, 100, 5, 8, 4, 3, 9, 2, 0, 7, 10))
[0, 1, 2, 3, 3, 4, 5, 7, 8, 9, 10, 100]
>>> mergeSort(())
[]
>>> mergeSort((3,))
[3]
>>> mergeSort((4,3))
[3, 4]
>>> mergeSort([7,6])
[6, 7]
'''

def mergeSort(a):
  '''マージソート
  タプルまたはリストを与える。
  リストを返す。
  '''

if __name__ == '__main__':
  import doctest
  doctest.testmod()