{"id":349,"date":"2016-12-19T21:45:01","date_gmt":"2016-12-19T13:45:01","guid":{"rendered":"http:\/\/blog.messi.moe\/?p=349"},"modified":"2017-02-09T00:16:46","modified_gmt":"2017-02-08T16:16:46","slug":"sort-approaches","status":"publish","type":"post","link":"https:\/\/blog.messi.moe\/?p=349","title":{"rendered":"Sorting Algorithms"},"content":{"rendered":"<pre><code class=\"python\">#-*-coding:utf-8-*-\n'''\nCreated on 2016\/12\/19\nLast updated on 2016\/12\/21\n@author: Camp Nou\n'''\n\n'''\nSorting Algorithms\n    Bubble Sort      stable    T(n)=\u0398(n^2)\n    Selection Sort   unstable  T(n)=\u0398(n^2)\n    Insert Sort      stable    T(n)=\u0398(n^2)\n    Merge Sort       stable    T(n)=\u0398(nlogn)\n    Quick Sort       unstable  T(n)=\u0398(nlogn)\n    Shell Sort       unstable  T(n)=\u0398(n^1.3) on average\n    Heap Sort        unstable  T(n)=\u0398(nlogn)\n    Bucket Sort      stable    T(n)=\u0398(n)\n    Count Sort       stable    T(n)=\u0398(n)\n'''\nfrom math import ceil\n\ndef BubbleSort(a):\n    array=a\n    l=len(array)\n    while l&gt;0:\n        for i in range(l-1):\n            if array[i]&gt;array[i+1]:\n                array[i],array[i+1]=swap(array[i],array[i+1])\n        l-=1\n    return array\n\ndef SelectionSort(a):\n    # T(n)=\u0398(n^2), unstable\n    array=a\n    for i in range(len(array)):\n        min=array[i]\n        index=i\n        for j in range(i,len(array)):\n            if array[j]&lt;min:\n                min=array[j]\n                index=j\n        t=array[i]\n        array[i]=array[index]\n        array[index]=t\n    return array\n\ndef InsertSort(a):\n    # T(n)=\u0398(n^2)\n    array=a\n    for i in range(1,len(array)):\n        for j in range(0,i):\n            if array[j]&gt;array[i]:\n                tmp=array[i]\n                index=j\n                array[index+1:i+1]=array[index:i]\n                array[index]=tmp\n    return array\n\ndef MergeSort(a):\n    # T(n)=\u0398(nlogn)\n    array=a \n    if len(array)&lt;=1:\n        return array\n    mid=int(len(array)\/2)\n    left=MergeSort(array[:mid])\n    right=MergeSort(array[mid:])\n\n    def Merge(left,right):\n        result=[]\n        while left and right:\n            if left[0]&lt;=right[0]:\n                result.append(left[0])\n                left.pop(0)\n            else:\n                result.append(right[0])\n                right.pop(0)\n        result+=left \n        result+=right\n        return result\n\n    return Merge(left,right)\n\n\ndef QuickSort(a):\n    # T(n)=\u0398(nlogn), unstable\n    array=a\n    less=[]\n    more=[]\n    pivotlist=[]\n    if len(array)&lt;=1:\n        return array\n    else:\n        pivot=array[0]\n        for i in range(len(array)):\n            if array[i]&lt;pivot:\n                less.append(array[i])\n            if array[i]&gt;pivot:\n                more.append(array[i])\n            if array[i]==pivot:\n                pivotlist.append(array[i])\n        less=QuickSort(less)\n        more=QuickSort(more)\n    return less+pivotlist+more \n\ndef ShellSort(a):\n    # T(n)=\u0398(n^1.3) on average, not stable\n    array=a\n    n=len(array)\n    group=int(ceil(n\/2)) \n    #print group\n    while group&gt;=1:\n        ary=[]\n        for i in range(group):\n            ary.append([])\n        for i in range(n):\n            ary[i%group].append(array[i])\n        for i in ary:\n            i=InsertSort(i)\n        array=[]\n        for i in ary:\n            array.extend(i)\n        #print array \n        group=int(ceil(group\/2))\n    return array \n\ndef HeapSort(array):\n    # T(n)=\u0398(nlogn), not stable\n    length=len(array)\n    sortedarray=[]\n    def maxHeapify(array):\n        n=len(array)\/2-1\n        while n&gt;=0:\n            if 2*n+1&lt;len(array):\n                [array[n],array[2*n+1]].sort()\n            else:\n                [array[n],array[2*n+1],array[2*n+2]].sort()\n            n=n-1\n    while len(sortedarray)&lt;length:\n        maxHeapify(array)\n        sortedarray.append(array.pop(0))\n    return sortedarray[::1]\n\ndef BucketSort(a):\n    array=a \n    result=[]\n    # 10 buckets\n    if len(array)&lt;=1:\n        return array \n    buckets=[[],[],[],[],[],[],[],[],[],[]]\n    #buckets[1].append(1)\n    for i in array:\n        index=i\/10\n        buckets[index].append(i) \n        #print i,index,buckets[index]\n        #print buckets[index]\n    for i in buckets:\n        #print i,\n        result.extend(QuickSort(i))\n    return result \n\ndef CountSort(a):\n    array=a \n    MAX=max(a)\n    MIN=min(a)\n    count=[0]*(MAX-MIN+1)\n    for i in array:\n        count[i-MIN]+=1\n    result=[]\n    for j in range(len(count)):\n        if count[j]!=0:\n            for k in range(count[j]):\n                result.append(j+MIN)\n    return result \n\na=[13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10]\nprint \"QuickSort:    \",QuickSort(a)\nprint \"BubbleSort:   \",BubbleSort(a)\nprint \"SelectionSort:\",SelectionSort(a)\nprint \"InsertSort:   \",InsertSort(a)\nprint \"MergeSort:    \",MergeSort(a)\nprint \"ShellSort:    \",ShellSort(a)\nprint \"BucketSort:   \",BucketSort(a)\nprint \"CountSort:    \",CountSort(a)\nprint \"HeapSort:     \",HeapSort(a)\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<pre><code class=\"python\">#-*-coding:utf-8-*-\n'''\nCreated on 2016\/12\/19\nLast updated on 2016\/12\/21\n@author: Camp Nou\n'''\n\n'''\nSorting Algorithms\n    Bubble Sort      stable    T(n)=\u0398(n^2)\n    Selection Sort   unstable  T(n)=\u0398(n^2)\n    Insert Sort      stable    T(n)=\u0398(n^2)\n    Merge Sort       stable    T(n)=\u0398(nlogn)\n    Quick Sort       unstable  T(n)=\u0398(nlogn)\n    Shell Sort       unstable  T(n)=\u0398(n^1.3) on average\n    Heap Sort        unstable  T(n)=\u0398(nlogn)\n    Bucket Sort      stable    T(n)=\u0398(n)\n    Count Sort       stable    T(n)=\u0398(n)\n'''\nfrom math import ceil\n\ndef BubbleSort(a):\n    array=a\n    l=len(array)\n    while l&gt;0:\n        for i in range(l-1):\n            if array[i]&gt;array[i+1]:\n                array[i],array[i+1]=swap(array[i],array[i+1])\n        l-=1\n    return array\n\ndef SelectionSort(a):\n    # T(n)=\u0398(n^2), unstable\n    array=a\n    for i in range(len(array)):\n        min=array[i]\n        index=i\n        for j in range(i,len(array)):\n            if array[j]&lt;min:\n                min=array[j]\n                index=j\n        t=array[i]\n        array[i]=array[index]\n        array[index]=t\n    return array\n\ndef InsertSort(a):\n    # T(n)=\u0398(n^2)\n    array=a\n    for i in range(1,len(array)):\n        for j in range(0,i):\n            if array[j]&gt;array[i]:\n                tmp=array[i]\n                index=j\n                array[index+1:i+1]=array[index:i]\n                array[index]=tmp\n    return array\n\ndef MergeSort(a):\n    # T(n)=\u0398(nlogn)\n    array=a \n    if len(array)&lt;=1:\n        return array\n    mid=int(len(array)\/2)\n    left=MergeSort(array[:mid])\n    right=MergeSort(array[mid:])\n\n    def Merge(left,right):\n        result=[]\n        while left and right:\n            if left[0]&lt;=right[0]:\n                result.append(left[0])\n                left.pop(0)\n            else:\n                result.append(right[0])\n                right.pop(0)\n        result+=left \n        result+=right\n        return result\n\n    return Merge(left,right)\n\n\ndef QuickSort(a):\n    # T(n)=\u0398(nlogn), unstable\n    array=a\n    less=[]\n    more=[]\n    pivotlist=[]\n    if len(array)&lt;=1:\n        return array\n    else:\n        pivot=array[0]\n        for i in range(len(array)):\n            if array[i]&lt;pivot:\n                less.append(array[i])\n            if array[i]&gt;pivot:\n                more.append(array[i])\n            if array[i]==pivot:\n                pivotlist.append(array[i])\n        less=QuickSort(less)\n        more=QuickSort(more)\n    return less+pivotlist+more \n\ndef ShellSort(a):\n    # T(n)=\u0398(n^1.3) on average, not stable\n    array=a\n    n=len(array)\n    group=int(ceil(n\/2)) \n    #print group\n    while group&gt;=1:\n        ary=[]\n        for i in range(group):\n            ary.append([])\n        for i in range(n):\n            ary[i%group].append(array[i])\n        for i in ary:\n            i=InsertSort(i)\n        array=[]\n        for i in ary:\n            array.extend(i)\n        #print array \n        group=int(ceil(group\/2))\n    return array \n\ndef HeapSort(array):\n    # T(n)=\u0398(nlogn), not stable\n    length=len(array)\n    sortedarray=[]\n    def maxHeapify(array):\n        n=len(array)\/2-1\n        while n&gt;=0:\n            if 2*n+1&lt;len(array):\n                [array[n],array[2*n+1]].sort()\n            else:\n                [array[n],array[2*n+1],array[2*n+2]].sort()\n            n=n-1\n    while len(sortedarray)&lt;length:\n        maxHeapify(array)\n        sortedarray.append(array.pop(0))\n    return sortedarray[::1]\n\ndef BucketSort(a):\n    array=a \n    result=[]\n    # 10 buckets\n    if len(array)&lt;=1:\n        return array \n    buckets=[[],[],[],[],[],[],[],[],[],[]]\n    #buckets[1].append(1)\n    for i in array:\n        index=i\/10\n        buckets[index].append(i) \n        #print i,index,buckets[index]\n        #print buckets[index]\n    for i in buckets:\n        #print i,\n        result.extend(QuickSort(i))\n    return result \n\ndef CountSort(a):\n    array=a \n    MAX=max(a)\n    MIN=min(a)\n    count=[0]*(MAX-MIN+1)\n    for i in array:\n        count[i-MIN]+=1\n    result=[]\n    for j in range(len(count)):\n        if count[j]!=0:\n            for k in range(count[j]):\n                result.append(j+MIN)\n    return result \n\na=[13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10]\nprint \"QuickSort:    \",QuickSort(a)\nprint \"BubbleSort:   \",BubbleSort(a)\nprint \"SelectionSort:\",SelectionSort(a)\nprint \"InsertSort:   \",InsertSort(a)\nprint \"MergeSort:    \",MergeSort(a)\nprint \"ShellSort:    \",ShellSort(a)\nprint \"BucketSort:   \",BucketSort(a)\nprint \"CountSort:    \",CountSort(a)\nprint \"HeapSort:     \",HeapSort(a)\n<\/code><\/pre>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/posts\/349"}],"collection":[{"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=349"}],"version-history":[{"count":5,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/posts\/349\/revisions"}],"predecessor-version":[{"id":405,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=\/wp\/v2\/posts\/349\/revisions\/405"}],"wp:attachment":[{"href":"https:\/\/blog.messi.moe\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=349"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=349"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.messi.moe\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=349"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}