{"id":812,"date":"2018-03-17T14:57:13","date_gmt":"2018-03-17T05:57:13","guid":{"rendered":"https:\/\/dong1lkim.oboki.net\/?p=812"},"modified":"2019-09-01T22:21:42","modified_gmt":"2019-09-01T13:21:42","slug":"algorithm-python%ec%9c%bc%eb%a1%9c-%ea%b5%ac%ed%98%84%ed%95%9c-sort","status":"publish","type":"post","link":"https:\/\/oboki.net\/workspace\/python\/algorithm-python%ec%9c%bc%eb%a1%9c-%ea%b5%ac%ed%98%84%ed%95%9c-sort\/","title":{"rendered":"[Algorithm] Python\uc73c\ub85c \uad6c\ud604\ud55c sort"},"content":{"rendered":"<h1>[Algorithm] Python\uc73c\ub85c \uad6c\ud604\ud55c sort<\/h1>\n<p>Python\uc740 <code>list<\/code> \uc790\ub8cc\ud615\uc5d0 \ub300\ud574 <code>sort<\/code> \uba54\uc18c\ub4dc\ub97c \uae30\ubcf8\uc801\uc73c\ub85c \uc81c\uacf5\ud558\uc9c0\ub9cc \ud544\uc694\uc5d0 \ub530\ub77c \uc9c1\uc811 \uad6c\ud604\ud560 \ud544\uc694\ub3c4 \uc788\uace0, \ub610 Python \uc5b8\uc5b4\uc640 \uc54c\uace0\ub9ac\uc998 \uc774\ud574\ub97c \uc704\ud574 \uc791\uc131\ud55c\ub2e4.<\/p>\n<ul>\n<li>\uc624\ub984\ucc28\uc21c \uc815\ub82c\n<ul>\n<li><code>list_data.sort()<\/code><\/li>\n<\/ul>\n<\/li>\n<li>\ub0b4\ub9bc\ucc28\uc21c \uc815\ub82c\n<ul>\n<li><code>list_data.sort(reverse=True)<\/code><\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<h2>Sort Basic<\/h2>\n<ul>\n<li>\uc120\ud0dd \uc815\ub82c (Selection Sort)<\/li>\n<li>\uc0bd\uc785 \uc815\ub82c (Insertion Sort)<\/li>\n<li>\uac70\ud488 \uc815\ub82c (Bubble Sort)<\/li>\n<li>\ud035 \uc815\ub82c (Quick Sort)<\/li>\n<\/ul>\n<hr \/>\n<h3>\uc120\ud0dd \uc815\ub82c (Selection Sort)<\/h3>\n<p>selection sort\ub294 \uc815\ub82c\ud558\uace0\uc790 \ud558\ub294 array \uc6d0\uc18c\ub4e4 \uc911 \uac00\uc7a5 \uc791\uc740 \uac12\uc744 \ucc3e\uc544 \ub9e8 \uc55e\uc758 \uac12\uacfc \uad50\uccb4\ud558\uace0, \uc774\uc5b4\uc11c \ub9e8 \uc55e\uc758 \uac12\uc744 \uc81c\uc678\ud55c \ub098\uba38\uc9c0 array \uc6d0\uc18c\ub4e4\uc5d0 \uc55e \uacfc\uc815\uc744 \ubc18\ubcf5\ud558\uc5ec \uc815\ub82c\ud558\ub294 \uc54c\uace0\ub9ac\uc998\uc774\ub2e4.<br \/>\n\uc544\ub798\uc640 \uac19\uc740 \uc21c\uc11c\ub85c \uc815\ub82c\uc774 \uc9c4\ud589\ub41c\ub2e4.<\/p>\n<table>\n<thead>\n<tr>\n<th>&#8211;<\/th>\n<th>7 3 4 2 5 6 1<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<table>\n<thead>\n<tr>\n<th>&#8211;<\/th>\n<th><em>1<\/em> 3 4 2 5 6 <em>7<\/em><\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<table>\n<thead>\n<tr>\n<th>&#8211;<\/th>\n<th>1 <em>2<\/em> 4 <em>3<\/em> 5 6 7<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<table>\n<thead>\n<tr>\n<th>&#8211;<\/th>\n<th>1 2 <em>3<\/em> <em>4<\/em> 5 6 7<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>\uc804\uccb4 \uc6d0\uc18c\uc5d0 \ub300\ud574 \uadf8 \ub4a4 \uc6d0\uc18c\ub4e4\uacfc \ube44\uad50\ub97c \uc218\ud589\ud558\ubbc0\ub85c \uc2dc\uac04\ubcf5\uc7a1\ub3c4\ub294 $O(n^2)$\uc774\ub2e4.<br \/>\n\uc54c\uace0\ub9ac\uc998\uc774 \ub2e8\uc21c\ud558\uc5ec \uba54\ubaa8\ub9ac\uac00 \uc81c\ud55c\uc801\uc778 \uacbd\uc6b0 \uc0ac\uc6a9\ud588\uc744 \ub54c \uc774\uc810\uc774 \uc788\ub2e4.<\/p>\n<h4>selection_sort<\/h4>\n<pre><code class=\"py\">def selection_sort(arr):\n    for i in range(len(arr)):\n        sel = i\n        for j in range(i+1,len(arr)):\n            if arr[sel]&gt;arr[j]: sel = j\n        temp = arr[sel]\n        arr[sel] = arr[i]\n        arr[i] = temp\n    return arr\n<\/code><\/pre>\n<hr \/>\n<h3>\uc0bd\uc785 \uc815\ub82c (Insertion Sort)<\/h3>\n<p>insertion sort\ub294 \uc8fc\uc5b4\uc9c4 array\uc758 \ub370\uc774\ud130\ub97c index \uc21c\uc11c\ub300\ub85c \uac00\uc838\uc624\uba74\uc11c, \ud574\ub2f9 \uc6d0\uc18c\ub97c \uac00\uc838\ub2e4 \ub193\uc744 \ub54c\uc5d0 \ud06c\uae30 \ube44\uad50\ub97c \ud558\uc5ec \uc801\uc808\ud55c \uc704\uce58\uc5d0 \ubc30\uce58\uc2dc\ud0a4\ub294 \uc54c\uace0\ub9ac\uc998\uc774\ub2e4.<br \/>\n$n$\uac1c\uc758 \ub370\uc774\ud130\uac00 \uc788\uc744 \ub54c \ucd5c\uc545\uc758 \uacbd\uc6b0 \uc544\ub798\uc640 \uac19\uc740 \ud69f\uc218\uc758 \ube44\uad50\ub97c \uc218\ud589\ud558\uac8c \ub418\ubbc0\ub85c<br \/>\n$$\\sum_{n=1}^{n-1} 1+2+3+4+&#8230;+(n-1) = \\frac{n(n-1)}{2}$$<br \/>\n\uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 $O(n^2)$\uc774\ub2e4.<\/p>\n<h4>insertion_sort<\/h4>\n<pre><code class=\"py\">def insertion_sort(arr):\n    for i in range(len(arr)):\n        temp, j = arr[i], i - 1\n        for j in range(j,-1,-1):\n            if arr[j]&lt;temp: break\n            arr[j+1] = arr[j]\n        arr[j+1] = temp\n    return arr\n<\/code><\/pre>\n<hr \/>\n<h3>\uac70\ud488 \uc815\ub82c (Bubble Sort)<\/h3>\n<p>\uac70\ud488 \uc815\ub82c\uc740 \ub450 \uc778\uc811\ud55c \uc6d0\uc18c\ub97c \uac80\uc0ac\ud558\uc5ec \uc815\ub82c\ud558\ub294 \ubc29\ubc95\uc774\ub2e4. \uc6d0\uc18c\uc758 \uc774\ub3d9\uc774 \uac70\ud488\uc774 \uc218\uba74\uc73c\ub85c \uc62c\ub77c\uc624\ub294 \ub4ef\ud55c \ubaa8\uc2b5\uc744 \ubcf4\uc774\uae30 \ub54c\ubb38\uc5d0 \uc774\ub807\uac8c \uc774\ub984 \uc9c0\uc5b4\uc9c4 \uac70\ud488 \uc815\ub82c\uc740 \uc778\uc811\ud55c \ub450 \uc6d0\uc18c\ub97c \uac80\uc0ac\ud558\uc5ec \uc815\ub82c\ud55c\ub2e4.<br \/>\n\uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 $O(n^2)$\uc774\ub2e4.<\/p>\n<h4>bubble_sort<\/h4>\n<pre><code class=\"py\">def bubble_sort(arr):\n    for i in range(len(arr)):\n        for j in range(len(arr)-i-1):\n            if arr[j]&gt;arr[j+1]:\n                temp = arr[j]\n                arr[j] = arr[j+1]\n                arr[j+1] = temp\n    return arr\n<\/code><\/pre>\n<hr \/>\n<h3>\ud035 \uc815\ub82c (Quick Sort)<\/h3>\n<p>\uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 \ucd5c\uc545\uc758 \uacbd\uc6b0 $O(n^2)$\uc77c \uc218\ub3c4 \uc788\uc9c0\ub9cc \ub300\ubd80\ubd84 $O(n {\\log n})$\uc774\ub2e4.<\/p>\n<h4>quick_sort<\/h4>\n<pre><code class=\"py\">def quick_sort(arr,left=-1,right=-1):\n    left_temp = left if left!=-1 else 0\n    right_temp = right if right!=-1 else len(arr) - 1\n    pivot = arr[left]\n    while left&lt;right:\n        while arr[right]&gt;=pivot and left&lt;right: right -= 1\n        if left!=right: arr[left] = arr[right]\n        while arr[left]&lt;=pivot and left&lt;right: left += 1\n        if left!=right:\n            arr[right] = arr[left]\n            right -= 1\n    arr[left] = pivot\n    pivot = left\n    left = left_temp\n    right = right_temp\n    if (left&lt;pivot): quick_sort(arr,left,pivot-1)\n    if (right&gt;pivot): quick_sort(arr,pivot+1,right)\n    return arr\n<\/code><\/pre>\n<hr \/>\n<h2>Python Sample<\/h2>\n<p>\uc704\uc5d0\uc11c \uc124\uba85\ud55c sort \ud568\uc218\ub4e4\uc744 \ubaa8\ub450 \ud14c\uc2a4\ud2b8 \ud574\ubcf4\ub294 \ud504\ub85c\uadf8\ub7a8. python\uc758 function\uc740 <code>list<\/code> \uc790\ub8cc\ud615 \uc778\uc218\uc5d0 \ub300\ud574 \ubb34\uc870\uac74 <code>call by reference<\/code> \ubc29\uc2dd\uc73c\ub85c \ub370\uc774\ud130\ub97c \ubcc0\ud615\ud558\ubbc0\ub85c main\uc5d0\uc11c <code>data_original<\/code> \uc744 \uc774\uc6a9\ud574 \uacc4\uc18d\ud574\uc11c \ucd08\uae30\ud654\ud574 \uc904 \ud544\uc694\uac00 \uc788\ub2e4.<\/p>\n<pre><code class=\"py\">def selection_sort(arr):\n    for i in range(len(arr)):\n        sel = i\n        for j in range(i+1,len(arr)):\n            if arr[sel]&gt;arr[j]: sel = j\n        temp = arr[sel]\n        arr[sel] = arr[i]\n        arr[i] = temp\n    return arr\n\ndef insertion_sort(arr):\n    for i in range(len(arr)):\n        temp, j = arr[i], i - 1\n        for j in range(j,-1,-1):\n            if arr[j]&lt;temp: break\n            arr[j+1] = arr[j]\n        arr[j+1] = temp\n    return arr\n\ndef bubble_sort(arr):\n    for i in range(len(arr)):\n        for j in range(len(arr)-i-1):\n            if arr[j]&gt;arr[j+1]:\n                temp = arr[j]\n                arr[j] = arr[j+1]\n                arr[j+1] = temp\n    return arr\n\ndef quick_sort(arr,left=-1,right=-1):\n    left_temp = left if left!=-1 else 0\n    right_temp = right if right!=-1 else len(arr) - 1\n    pivot = arr[left]\n    while left&lt;right:\n        while arr[right]&gt;=pivot and left&lt;right: right -= 1\n        if left!=right: arr[left] = arr[right]\n        while arr[left]&lt;=pivot and left&lt;right: left += 1\n        if left!=right:\n            arr[right] = arr[left]\n            right -= 1\n    arr[left] = pivot\n    pivot = left\n    left = left_temp\n    right = right_temp\n    if (left&lt;pivot): quick_sort(arr,left,pivot-1)\n    if (right&gt;pivot): quick_sort(arr,pivot+1,right)\n    return arr\n\ndef main():\n    import random\n    data_original = [random.randint(1,100) for _ in range(random.randint(4,10))]\n    print(\"original data\")\n    print(data_original)\n\n    print(\"\\nselection sort test\")\n    data = data_original\n    print(selection_sort(data))\n\n    print(\"\\ninsertion sort test\")\n    data = data_original\n    print(insertion_sort(data))\n\n    print(\"\\nbubble sort test\")\n    data = data_original\n    print(bubble_sort(data))\n\n    print(\"\\nquick sort test\")\n    data = data_original\n    print(quick_sort(data))\n\nif __name__ == '__main__':\n    main()\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>[Algorithm] Python\uc73c\ub85c \uad6c\ud604\ud55c sort Python\uc740 list \uc790\ub8cc\ud615\uc5d0 \ub300\ud574 sort \uba54\uc18c\ub4dc\ub97c \uae30\ubcf8\uc801\uc73c\ub85c \uc81c\uacf5\ud558\uc9c0\ub9cc \ud544\uc694\uc5d0 \ub530\ub77c \uc9c1\uc811 \uad6c\ud604\ud560 \ud544\uc694\ub3c4 \uc788\uace0, \ub610 Python \uc5b8\uc5b4\uc640 \uc54c\uace0\ub9ac\uc998 \uc774\ud574\ub97c \uc704\ud574 \uc791\uc131\ud55c\ub2e4. \uc624\ub984\ucc28\uc21c \uc815\ub82c list_data.sort() \ub0b4\ub9bc\ucc28\uc21c \uc815\ub82c list_data.sort(reverse=True) Sort Basic \uc120\ud0dd \uc815\ub82c (Selection Sort) \uc0bd\uc785 \uc815\ub82c (Insertion Sort) \uac70\ud488 \uc815\ub82c (Bubble Sort) \ud035 \uc815\ub82c (Quick Sort) \uc120\ud0dd \uc815\ub82c (Selection Sort) selection sort\ub294 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[17,10],"tags":[150,34,151],"class_list":["post-812","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-python","tag-algorithm","tag-python","tag-sort"],"_links":{"self":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/812","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/comments?post=812"}],"version-history":[{"count":7,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/812\/revisions"}],"predecessor-version":[{"id":1286,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/812\/revisions\/1286"}],"wp:attachment":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/media?parent=812"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/categories?post=812"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/tags?post=812"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}