{"id":1788,"date":"2023-03-29T11:03:00","date_gmt":"2023-03-29T02:03:00","guid":{"rendered":"https:\/\/ksrd.jp\/koubou\/wordpress\/?p=1788"},"modified":"2023-04-23T12:57:55","modified_gmt":"2023-04-23T03:57:55","slug":"%e4%b8%a6%e3%81%b9%e6%9b%bf%e3%81%88%ef%bc%88%e3%82%a2%e3%83%ab%e3%82%b4%e3%83%aa%e3%82%ba%e3%83%a0%ef%bc%89","status":"publish","type":"post","link":"https:\/\/ksrd.jp\/koubou\/wordpress\/2023\/03\/%e4%b8%a6%e3%81%b9%e6%9b%bf%e3%81%88%ef%bc%88%e3%82%a2%e3%83%ab%e3%82%b4%e3%83%aa%e3%82%ba%e3%83%a0%ef%bc%89\/","title":{"rendered":"\u4e26\u3079\u66ff\u3048\uff08\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\uff09"},"content":{"rendered":"\n

\u3000\u3000Python\u3067\uff16\u7a2e\u985e\u306e\u4e26\u3079\u66ff\u3048\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u8abf\u3079\u308b
\u3000\u3000\u3000\u3000\u6607\u9806\u306b\u4e26\u3079\u66ff\u3048\u308b\u3053\u3068\u3092\u524d\u63d0\u3068\u3059\u308b\uff08\u964d\u9806\u306f\u5185\u5bb9\u3092\u8aad\u307f\u66ff\u3048\u3066\u304f\u3060\u3055\u3044\uff09<\/p>\n\n\n\n

\uff11\uff0e\u30d0\u30d6\u30eb\u30bd\u30fc\u30c8<\/strong><\/h4>\n\n\n\n

\u3000\u96a3\u540c\u58eb\u306e\u5024\u3092\u6bd4\u8f03\u3001\u5fc5\u8981\u304c\u3042\u308c\u3070\u5165\u308c\u66ff\u3048\u3001\u3092\u7e70\u308a\u8fd4\u3057\u3066\u6574\u5217\u3055\u305b\u308b
\u3000\u3000\u3000\u8a08\u7b97\u56de\u6570\u306f\u3001O(n^2)<\/strong>

\u3000\u30b5\u30f3\u30d7\u30eb\u30b3\u30fc\u30c9<\/p>\n\n\n\n

def bubble_sort(arr):\n    n = len(arr)\n    for i in range(n):\n        for j in range(0, n-i-1):\n            if arr[j] > arr[j+1]:\n                arr[j], arr[j+1] = arr[j+1], arr[j]\n\n# \u4f7f\u7528\u4f8b\narr = [64, 34, 25, 12, 22, 11, 90]\nbubble_sort(arr)\nprint("\u30bd\u30fc\u30c8\u6e08\u307f\u914d\u5217\uff1a")\nfor i in range(len(arr)):\n    print("%d" %arr[i]),<\/code><\/pre><\/div>\n\n\n\n
\uff12\uff0e\u30af\u30a4\u30c3\u30af\u30bd\u30fc\u30c8<\/strong><\/h4>\n\n\n\n
\u3000\u57fa\u6e96\u5024\u3092\u8a2d\u3051\u3066\u3001\u57fa\u6e96\u5024\u3088\u308a\u5927\u304d\u3044\u30d6\u30ed\u30c3\u30af\u3068\u5c0f\u3055\u3044\u30d6\u30ed\u30c3\u30af\u306b\u5206\u3051\u3066\u4e26\u3073\u66ff\u3048\u308b
\u3000\u3000\u3000\u8a08\u7b97\u56de\u6570\u306f\u3001O(n log n)<\/strong>

\u3000\u30b5\u30f3\u30d7\u30eb\u30b3\u30fc\u30c9<\/p>\n\n\n\n
def quick_sort(arr, low, high):\n    if low < high:\n        # pivot\u3092\u6c7a\u5b9a\u3059\u308b\n        pivot_index = partition(arr, low, high)\n\n        # pivot\u3092\u4e2d\u5fc3\u306b\u5de6\u5074\u3092\u30bd\u30fc\u30c8\u3059\u308b\n        quick_sort(arr, low, pivot_index - 1)\n        # pivot\u3092\u4e2d\u5fc3\u306b\u53f3\u5074\u3092\u30bd\u30fc\u30c8\u3059\u308b\n        quick_sort(arr, pivot_index + 1, high)\n\ndef partition(arr, low, high):\n    # pivot\u3092\u6700\u5f8c\u306e\u8981\u7d20\u306b\u8a2d\u5b9a\u3059\u308b\n    pivot = arr[high]\n    # pivot\u3088\u308a\u5c0f\u3055\u3044\u8981\u7d20\u3092\u5de6\u5074\u306b\u3001\u5927\u304d\u3044\u8981\u7d20\u3092\u53f3\u5074\u306b\u914d\u7f6e\u3059\u308b\n    i = low - 1\n    for j in range(low, high):\n        if arr[j] < pivot:\n            i += 1\n            arr[i], arr[j] = arr[j], arr[i]\n    # pivot\u3092\u9069\u5207\u306a\u4f4d\u7f6e\u306b\u914d\u7f6e\u3059\u308b\n    arr[i+1], arr[high] = arr[high], arr[i+1]\n    return i+1\n\n# \u4f7f\u7528\u4f8b\narr = [64, 34, 25, 12, 22, 11, 90]\nn = len(arr)\nquick_sort(arr, 0, n-1)\nprint("\u30bd\u30fc\u30c8\u6e08\u307f\u914d\u5217\uff1a")\nfor i in range(n):\n    print("%d" % arr[i]),<\/code><\/pre><\/div>\n\n\n\n
\uff13\uff0e\u30de\u30fc\u30b8\u30bd\u30fc\u30c8<\/strong><\/h4>\n\n\n\n
\u3000\u5bfe\u8c61\u306e\u30c7\u30fc\u30bf\u3092\u5206\u5272\u3057\u3001\u5206\u5272\u5f8c\u306e\u5c0f\u3055\u3044\u30d6\u30ed\u30c3\u30af\u5185\u3067\u6574\u5217\u3001\u518d\u5ea6\u7d71\u5408\u3059\u308b
\u3000\u3000\u3000\u8a08\u7b97\u56de\u6570\u306f\u3001O(n log n)<\/strong>

\u3000\u30b5\u30f3\u30d7\u30eb\u30b3\u30fc\u30c9<\/p>\n\n\n\n
def merge_sort(arr):\n    if len(arr) > 1:\n        # \u4e2d\u592e\u306e\u4f4d\u7f6e\u3092\u6c42\u3081\u308b\n        mid = len(arr) \/\/ 2\n\n        # \u5de6\u5074\u3068\u53f3\u5074\u306b\u5206\u5272\u3059\u308b\n        left_half = arr[:mid]\n        right_half = arr[mid:]\n\n        # \u5de6\u5074\u3068\u53f3\u5074\u3092\u518d\u5e30\u7684\u306b\u30bd\u30fc\u30c8\u3059\u308b\n        merge_sort(left_half)\n        merge_sort(right_half)\n\n        # \u30bd\u30fc\u30c8\u6e08\u307f\u306e\u5de6\u5074\u3068\u53f3\u5074\u3092\u30de\u30fc\u30b8\u3059\u308b\n        i = j = k = 0\n        while i < len(left_half) and j < len(right_half):\n            if left_half[i] < right_half[j]:\n                arr[k] = left_half[i]\n                i += 1\n            else:\n                arr[k] = right_half[j]\n                j += 1\n            k += 1\n\n        # \u5de6\u5074\u306b\u6b8b\u3063\u305f\u8981\u7d20\u3092\u914d\u5217\u306b\u30b3\u30d4\u30fc\u3059\u308b\n        while i < len(left_half):\n            arr[k] = left_half[i]\n            i += 1\n            k += 1\n\n        # \u53f3\u5074\u306b\u6b8b\u3063\u305f\u8981\u7d20\u3092\u914d\u5217\u306b\u30b3\u30d4\u30fc\u3059\u308b\n        while j < len(right_half):\n            arr[k] = right_half[j]\n            j += 1\n            k += 1\n\n# \u4f7f\u7528\u4f8b\narr = [64, 34, 25, 12, 22, 11, 90]\nmerge_sort(arr)\nprint("\u30bd\u30fc\u30c8\u6e08\u307f\u914d\u5217\uff1a")\nfor i in range(len(arr)):\n    print("%d" %arr[i]),<\/code><\/pre><\/div>\n\n\n\n
\uff14\uff0e\u9078\u629e\u30bd\u30fc\u30c8<\/strong><\/h4>\n\n\n\n
\u3000\u30c7\u30fc\u30bf\u5185\u306e\u6700\u5c0f\u5024\uff08\u6700\u5927\u5024\uff09\u306e\u5024\u3092\u898b\u3064\u3051\u3066\u3001\u5de6\u304b\u3089\u9806\u756a\u306b\u4e26\u3073\u66ff\u3048\u308b
\u3000\u3000\u3000\u8a08\u7b97\u56de\u6570\u306f\u3001o(n^2)<\/strong>

\u3000\u30b5\u30f3\u30d7\u30eb\u30b3\u30fc\u30c9<\/p>\n\n\n\n
def selection_sort(arr):\n    n = len(arr)\n    # \u914d\u5217\u306e\u5148\u982d\u304b\u3089\u672b\u5c3e\u307e\u3067\u3001\u6700\u5c0f\u5024\u3092\u9078\u629e\u3057\u3066\u914d\u7f6e\u3059\u308b\n    for i in range(n):\n        min_index = i\n        for j in range(i+1, n):\n            if arr[j] < arr[min_index]:\n                min_index = j\n        arr[i], arr[min_index] = arr[min_index], arr[i]\n\n# \u4f7f\u7528\u4f8b\narr = [64, 34, 25, 12, 22, 11, 90]\nselection_sort(arr)\nprint("\u30bd\u30fc\u30c8\u6e08\u307f\u914d\u5217\uff1a")\nfor i in range(len(arr)):\n    print("%d" %arr[i]),<\/code><\/pre><\/div>\n\n\n\n
\uff15\uff0e\u633f\u5165\u30bd\u30fc\u30c8<\/strong><\/h4>\n\n\n\n
\u3000\u5de6\u304b\u3089\u9806\u756a\u306b\u8981\u7d20\u3092\u6bd4\u8f03\u3057\u306a\u304c\u3089\u5165\u308c\u66ff\u3048\u3066\u3044\u304f\u65b9\u6cd5
\u3000\u3000\u3000\u8a08\u7b97\u56de\u6570\u306f\u3001\u6700\u5927\u3067n(n-1)\/2<\/strong>

\u3000\u30b5\u30f3\u30d7\u30eb\u30b3\u30fc\u30c9<\/p>\n\n\n\n
def insertion_sort(arr):\n    n = len(arr)\n    # \u914d\u5217\u306e\u5148\u982d\u304b\u3089\u672b\u5c3e\u307e\u3067\u3001\u8981\u7d20\u3092\u633f\u5165\u3057\u3066\u914d\u7f6e\u3059\u308b\n    for i in range(1, n):\n        key = arr[i]\n        j = i - 1\n        while j >= 0 and key < arr[j]:\n            arr[j+1] = arr[j]\n            j -= 1\n        arr[j+1] = key\n\n# \u4f7f\u7528\u4f8b\narr = [64, 34, 25, 12, 22, 11, 90]\ninsertion_sort(arr)\nprint("\u30bd\u30fc\u30c8\u6e08\u307f\u914d\u5217\uff1a")\nfor i in range(len(arr)):\n    print("%d" %arr[i]),<\/code><\/pre><\/div>\n\n\n\n
\uff16\uff0e\u30d2\u30fc\u30d7\u30bd\u30fc\u30c8<\/strong><\/h4>\n\n\n\n
\u3000\u4e8c\u5206\u6728\uff08\u89aa\uff11\u306b\u5bfe\u3057\u3066\u5b50\uff12\u306e\u30c4\u30ea\u30fc\u69cb\u9020\uff09\u306e\u4e00\u7a2e\u3092\u69cb\u7bc9\u3057\u3066\u4e26\u3079\u66ff\u3048\u3092\u304a\u3053\u306a\u3046
\u3000\u3000\u3000\u8a08\u7b97\u56de\u6570\u306f\u3001O(n log n)<\/strong>

\u3000\u30b5\u30f3\u30d7\u30eb\u30b3\u30fc\u30c9<\/p>\n\n\n\n
def heapify(arr, n, i):\n    largest = i  # \u89aa\u30ce\u30fc\u30c9\n    l = 2*i + 1  # \u5de6\u306e\u5b50\u30ce\u30fc\u30c9\n    r = 2*i + 2  # \u53f3\u306e\u5b50\u30ce\u30fc\u30c9\n\n    # \u5de6\u306e\u5b50\u30ce\u30fc\u30c9\u304c\u89aa\u30ce\u30fc\u30c9\u3088\u308a\u5927\u304d\u3044\u5834\u5408\n    if l < n and arr[largest] < arr[l]:\n        largest = l\n\n    # \u53f3\u306e\u5b50\u30ce\u30fc\u30c9\u304c\u89aa\u30ce\u30fc\u30c9\u3088\u308a\u5927\u304d\u3044\u5834\u5408\n    if r < n and arr[largest] < arr[r]:\n        largest = r\n\n    # \u89aa\u30ce\u30fc\u30c9\u304c\u6700\u5927\u5024\u3067\u306a\u3044\u5834\u5408\u3001\u89aa\u30ce\u30fc\u30c9\u3068\u6700\u5927\u5024\u3092\u4ea4\u63db\u3059\u308b\n    if largest != i:\n        arr[i], arr[largest] = arr[largest], arr[i]\n\n        # \u5b50\u30ce\u30fc\u30c9\u306e\u30d2\u30fc\u30d7\u3082\u4fee\u6b63\u3059\u308b\n        heapify(arr, n, largest)\n\ndef heap_sort(arr):\n    n = len(arr)\n\n    # \u6700\u521d\u306b\u3001\u914d\u5217\u3092\u30d2\u30fc\u30d7\u69cb\u9020\u306b\u3059\u308b\n    for i in range(n \/\/ 2 - 1, -1, -1):\n        heapify(arr, n, i)\n\n    # \u30d2\u30fc\u30d7\u304b\u3089\u4e00\u3064\u305a\u3064\u6700\u5927\u5024\u3092\u53d6\u308a\u51fa\u3057\u3066\u3001\u914d\u5217\u306e\u672b\u5c3e\u306b\u914d\u7f6e\u3059\u308b\n    for i in range(n-1, 0, -1):\n        arr[i], arr[0] = arr[0], arr[i]  # \u6700\u5927\u5024\u3092\u672b\u5c3e\u306b\u914d\u7f6e\n        heapify(arr, i, 0)  # \u672a\u30bd\u30fc\u30c8\u90e8\u5206\u306e\u30d2\u30fc\u30d7\u3092\u518d\u69cb\u7bc9\u3059\u308b\n\n# \u4f7f\u7528\u4f8b\narr = [64, 34, 25, 12, 22, 11, 90]\nheap_sort(arr)\nprint("\u30bd\u30fc\u30c8\u6e08\u307f\u914d\u5217\uff1a")\nfor i in range(len(arr)):\n    print("%d" %arr[i]),<\/code><\/pre><\/div>\n\n\n\n
\u3000<\/p>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
\u4e26\u3079\u66ff\u3048\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u89e3\u8aac\u3059\u308b\u3002<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[11,2],"tags":[20],"class_list":["post-1788","post","type-post","status-publish","format-standard","hentry","category-11","category-2","tag-python"],"_links":{"self":[{"href":"https:\/\/ksrd.jp\/koubou\/wordpress\/wp-json\/wp\/v2\/posts\/1788","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ksrd.jp\/koubou\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/ksrd.jp\/koubou\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/ksrd.jp\/koubou\/wordpress\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/ksrd.jp\/koubou\/wordpress\/wp-json\/wp\/v2\/comments?post=1788"}],"version-history":[{"count":6,"href":"https:\/\/ksrd.jp\/koubou\/wordpress\/wp-json\/wp\/v2\/posts\/1788\/revisions"}],"predecessor-version":[{"id":1794,"href":"https:\/\/ksrd.jp\/koubou\/wordpress\/wp-json\/wp\/v2\/posts\/1788\/revisions\/1794"}],"wp:attachment":[{"href":"https:\/\/ksrd.jp\/koubou\/wordpress\/wp-json\/wp\/v2\/media?parent=1788"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/ksrd.jp\/koubou\/wordpress\/wp-json\/wp\/v2\/categories?post=1788"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/ksrd.jp\/koubou\/wordpress\/wp-json\/wp\/v2\/tags?post=1788"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}