Python - Searching and Sorting(binary search, sort, time)

Practical Programming
An Introduction to Computer Science
Using Python 3
(Pragmatic Programmers)
(Pragmatic Bookshelf)
Paul Gries (著) Jennifer Campbell (著)
Jason Montojo (著) Lynn Beighley (編集)

開発環境

• OS X Yosemite - Apple (OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Python 3.4 (プログラミング言語)

Practical Programming: An Introduction to Computer Science Using Python 3 (Pragmatic Programmers) (Paul Gries (著)、Jennifer Campbell (著)、Jason Montojo (著)、Lynn Beighley (編集)、Pragmatic Bookshelf)のChapter 13(Searching and Sorting)、13.7(Exercises) 8.を解いてみる。

13.7(Exercises) 8.

1. [9, 0, 8, 1, 7, 2, 6, 3, 5, 4], []
2. [0, 8, 1, 7, 2, 6, 3, 5, 4], [9]
3. [8, 1, 7, 2, 6, 3, 5, 4], [0, 9]
4. [1, 7, 2, 6, 3, 5, 4], [0, 8, 9]
5. [7, 2, 6, 3, 5, 4], [0, 1, 8, 9]
6. [2, 6, 3, 5, 4], [0, 1, 7, 8, 9]
7. [6, 3, 5, 4], [0, 1, 2, 7, 8, 9]
8. [3, 5, 4], [0, 1, 2, 6, 7, 8, 9]
9. [5, 4], [0, 1, 2, 3, 6, 7, 8, 9]
10. [4], [0, 1, 2, 3, 5, 6, 7, 8, 9]
11. [], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

binary searchが約log_2 N、よって、長さNのリストをソートするのに、bin_sortは最大で約N log_2 Nとなる。