{"id":547,"date":"2013-08-07T16:34:38","date_gmt":"2013-08-07T23:34:38","guid":{"rendered":"http:\/\/192.168.1.2\/wordpress\/?p=547"},"modified":"2021-04-04T23:10:36","modified_gmt":"2021-04-05T06:10:36","slug":"sorting-bubble-sort","status":"publish","type":"post","link":"http:\/\/cywang.no-ip.org\/wordpress\/?p=547","title":{"rendered":"Sorting – Bubble Sort"},"content":{"rendered":"

Time complexity:<\/p>\n

Worst-case: \\(O(n^2)\\)<\/p>\n

Best-case: \\(O(n)\\)<\/p>\n

Average-case: \\(O(n^2)\\)<\/p>\n

Sort array elements in ascending order. If the first element is greater than the second element, swap the first two elements.<\/p>\n

Then, we go to the “next pair” and so on.<\/p>\n

<\/p>\n

void BubbleSort(int *list, int size)\r\n{\r\n    int i, j, swapCount = 0, runningCount = 0, isSwapped = 0;\r\n    for(i=0;i<size;i++)\r\n    {\r\n        isSwapped = 0;\r\n        for(j=0;j<size-i-1;j++)\r\n        {\r\n            runningCount++;\r\n            if(list[j] > list[j+1])\r\n            {\r\n                swap(&list[j], &list[j+1]);\r\n                swapCount++;\r\n                isSwapped++;\r\n            }\r\n        }\r\n        if(isSwapped == 0)\r\n            break;\r\n    }\r\n}\r\n\r\nvoid swap(int *x, int *y)\r\n{\r\n    int tmp = *x;\r\n    *x = *y;\r\n    *y = tmp;\r\n}<\/pre>\n
For example, to sort an array of size 7.<\/p>\n
Case I: Worst-case<\/strong><\/p>\n
int worstList[] = {23,20,18,14,10,6,3};<\/pre>\n
swapCount = 21 and runningCount =\u00a021<\/p>\n
Case II: Best-case<\/strong><\/p>\n
int bestList[] = {3, 6, 10, 14, 18, 20, 23};<\/pre>\n
swapCount = 0 and runningCount =\u00a06<\/p>\n
Case III: Average-case<\/strong><\/p>\n
int averageList[] = {20, 6, 23, 3, 18, 14, 10};<\/pre>\n
swapCount = 13 and runningCount =\u00a020<\/p>\n
 <\/p>\n
Unsorted Array: 20, 6, 23, 3, 18, 14, 10<\/p>\n
Step01<\/span>. (20, 6), 23, 3, 18, 14, 10 \u00a0->\u00a0\u00a0(6, 20), 23, 3, 18, 14, 10<\/span><\/p>\n
Step02.\u00a06, (20, 23), 3, 18, 14, 10\u00a0\u00a0-> \u00a0without swapping<\/span><\/p>\n
Step03.\u00a0<\/span>6, 20<\/span>, (23, 3), 18, 14, 10<\/span>\u00a0\u00a0-> \u00a06, 20, (3, 23), 18, 14, 10<\/span><\/p>\n
Step04.\u00a0<\/span>6,\u00a020<\/span>, 3, (23, 18), 14, 10<\/span>\u00a0\u00a0-> \u00a06, 20, 3, (18, 23), 14, 10<\/span><\/p>\n
Step05.\u00a0<\/span>6,\u00a020<\/span>, 3, 18, (23, 14), 10<\/span>\u00a0\u00a0-> \u00a06, 20,\u00a03, 18, (14, 23), 10<\/span><\/p>\n
Step06.\u00a0<\/span>6,\u00a020<\/span>, 3, 18, 14, (23, 10)<\/span>\u00a0\u00a0-> \u00a06, 20,\u00a03,\u00a018, 14, (10, 23<\/span>)<\/span><\/p>\n
——————————————————————————————<\/span><\/p>\n
Step07. (<\/span>6,\u00a020)<\/span>, 3, 18,\u00a014, 10, 23<\/span><\/span>\u00a0 -> \u00a0without swapping<\/span><\/p>\n
Step08. <\/span>6, (20<\/span>, 3), 18,\u00a014, 10,\u00a023<\/span>\u00a0 -> \u00a06, (3<\/span>, 20), 18,\u00a014, 10,\u00a023<\/span><\/span><\/p>\n
Step09.\u00a0<\/span>6, <\/span>3, (20, 18),\u00a014, 10,\u00a023<\/span>\u00a0 -> \u00a06, 3<\/span>, (18, 20),\u00a014, 10,\u00a023<\/span><\/span><\/p>\n
Step10.\u00a06,\u00a03<\/span>, 18, (20,\u00a014), 10,\u00a023<\/span>\u00a0 -> \u00a06, 3, 18, (14, 20), 10,\u00a023<\/span><\/span><\/p>\n
Step11.\u00a06,\u00a0<\/span>3<\/span>, 18<\/span>, 14, (20, 10),\u00a0<\/span>23<\/span>\u00a0 -> \u00a06,\u00a0<\/span>3<\/span>, 18<\/span>,\u00a014, (10, 20<\/span>),\u00a0<\/span>23<\/span><\/p>\n
——————————————————————————————<\/span>\u200b<\/span><\/p>\n
Step12. (6,\u00a0<\/span>3)<\/span>, 18<\/span>,\u00a014, 10, 20<\/span>,\u00a0<\/span>23<\/span>\u00a0 -> \u00a0(3,\u00a0<\/span>6)<\/span>, 18<\/span>,\u00a014,\u00a010,\u00a020<\/span>,\u00a0<\/span>23<\/span><\/p>\n
Step13.\u00a03, (<\/span>6<\/span>, 18)<\/span>,\u00a014,\u00a010,\u00a020<\/span>,\u00a0<\/span>23<\/span>\u00a0 -> \u00a0without swapping<\/span><\/p>\n
Step14.\u00a03, <\/span>6<\/span>, (18<\/span>,\u00a014),\u00a010,\u00a020<\/span>,\u00a0<\/span>23<\/span>\u00a0 -> \u00a03,\u00a0<\/span>6<\/span>, (14<\/span>,\u00a018),\u00a010,\u00a020<\/span>,\u00a0<\/span>23<\/span><\/p>\n
Step15.\u00a03,\u00a0<\/span>6<\/span>, 14<\/span>, (18,\u00a010),\u00a020<\/span>,\u00a0<\/span>23<\/span>\u00a0 -> \u00a03,\u00a0<\/span>6<\/span>,\u00a014<\/span>, (10,\u00a018<\/span>),\u00a020<\/span>,\u00a0<\/span>23<\/span><\/p>\n
——————————————————————————————<\/span>\u200b<\/span><\/p>\n
Step16. (3,\u00a0<\/span>6)<\/span>,\u00a014<\/span>, 10,\u00a018<\/span>,\u00a020<\/span>,\u00a0<\/span>23<\/span>\u00a0 -> \u00a0without swapping<\/span><\/p>\n
Step17. 3, (<\/span>6<\/span>,\u00a014)<\/span>,\u00a010,\u00a018<\/span>,\u00a020<\/span>,\u00a0<\/span>23<\/span>\u00a0 -> \u00a0without swapping<\/span><\/p>\n
Step18.\u00a03, <\/span>6<\/span>, (14<\/span>,\u00a010),\u00a018<\/span>,\u00a020<\/span>,\u00a0<\/span>23<\/span>\u00a0 -> \u00a03,\u00a0<\/span>6<\/span>, (10<\/span>,\u00a014<\/span>),\u00a018<\/span>,\u00a020<\/span>,\u00a0<\/span>23<\/span><\/p>\n
——————————————————————————————<\/span>\u200b<\/span><\/p>\n
Step19. (3,\u00a0<\/span>6)<\/span>, 10<\/span>,\u00a014<\/span>,\u00a018<\/span>,\u00a020<\/span>,\u00a0<\/span>23<\/span>\u00a0 -> \u00a0without swapping<\/span><\/p>\n
Step20. 3, (<\/span>6<\/span>,\u00a010<\/span>)<\/span>,\u00a014<\/span>,\u00a018<\/span>,\u00a020<\/span>,\u00a0<\/span>23<\/span>\u00a0 -> \u00a0without swapping -> Break!!<\/span><\/p>\n
—————————————————————————————––<\/span><\/span>\u200b<\/span><\/span><\/p>\n
Sorted Array: 3, 6, 10, 14, 18, 20, 23\u00a0<\/span><\/span><\/p>\n
 <\/p>\n
Python:<\/p>\n
def BubbleSort(data):\r\n   data_len = len(data)\r\n   print(\"Data Length: \",data_len)\r\n   for i in range(0,data_len):\r\n      swapped = 0;\r\n      for j in range(0,data_len-i-1):\r\n         if data[j] > data[j+1]:\r\n            tmp = data[j]\r\n            data[j] = data[j+1]\r\n            data[j+1] = tmp\r\n            swapped += 1;\r\n      if swapped == 0:\r\n         break;<\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
Time complexity: Worst-case: Best-case: Average-case: Sort array elements in ascending order. If the first element is greater than the second element, swap the first two elements. Then, we go to the “next pair” and so on.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":""},"categories":[24,21],"tags":[],"class_list":["post-547","post","type-post","status-publish","format-standard","hentry","category-chapter-11-sorting-and-searching","category-data-structures-and-algorithms"],"_links":{"self":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/547","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=547"}],"version-history":[{"count":6,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/547\/revisions"}],"predecessor-version":[{"id":862,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/547\/revisions\/862"}],"wp:attachment":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=547"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=547"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=547"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}