{"id":555,"date":"2013-08-07T20:49:09","date_gmt":"2013-08-08T03:49:09","guid":{"rendered":"http:\/\/192.168.1.2\/wordpress\/?p=555"},"modified":"2021-04-04T23:10:42","modified_gmt":"2021-04-05T06:10:42","slug":"sorting-selection-sort","status":"publish","type":"post","link":"http:\/\/cywang.no-ip.org\/wordpress\/?p=555","title":{"rendered":"Sorting – Selection Sort"},"content":{"rendered":"

Time complexity:<\/p>\n

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

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

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

Find the smallest element and move it to the front. Then, find the second smallest and move it.<\/p>\n

<\/p>\n

void SelectionSort(int *list, int size)\r\n{\r\n    int i, j, minIndex, swapCount = 0, runningCount = 0;\r\n    for(i=0;i<size;i++)\r\n    {\r\n        minIndex = i;\r\n        for(j=i+1;j<size;j++)\r\n        {\r\n            runningCount++;\r\n            if(list[minIndex] > list[j])\r\n                minIndex = j;\r\n        }\r\n        if(minIndex != i)\r\n        {\r\n            swap(&list[i], &list[minIndex]);\r\n            swapCount++;\r\n        }\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 = 3 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 =\u00a021<\/p>\n
Case III: Average-case<\/strong><\/p>\n
int averageList[] = {20, 6, 23, 3, 18, 14, 10};<\/pre>\n
swapCount = 3 and runningCount =\u00a021<\/p>\n
 <\/p>\n
Unsorted Array: 20, 6, 23, 3, 18, 14, 10<\/p>\n
Step01<\/span>. 20<\/u>, 6, 23, (3), 18, 14, 10 \u00a0->\u00a0\u00a03<\/span>, 6, 23, (20), 18, 14, 10<\/span><\/p>\n
Step02.\u00a0<\/span>3<\/span>, (6<\/span>)<\/u>, 23, 20<\/span>, 18, 14, 10\u00a0\u00a0-> \u00a0without swapping<\/span><\/p>\n
Step03.\u00a0<\/span>3<\/span>, 6<\/span>, 23<\/u>,\u00a020, 18, 14, (10)\u00a0\u00a0-> \u00a03<\/span>,\u00a06<\/span>, 10<\/span>, 20<\/span>, 18, 14, (23)<\/span><\/p>\n
Step04.\u00a03<\/span>,\u00a06<\/span>,\u00a010<\/span>, 20<\/u>, 18, (14), 23\u00a0 -> \u00a03<\/span>,\u00a06<\/span>,\u00a010<\/span>, 14<\/span><\/span>, 18, (20), 23<\/span><\/p>\n
Step05.\u00a03<\/span>,\u00a06<\/span>,\u00a010<\/span>,\u00a014<\/span>, (18<\/span>)<\/u>, 20,\u00a023\u00a0\u00a0-> \u00a0without swapping<\/span><\/p>\n
Step06.\u00a0<\/span>3<\/span>,\u00a0<\/span>6<\/span>,\u00a0<\/span>10<\/span>,\u00a0<\/span>14<\/span>, <\/span>18<\/span>, (<\/span>20<\/u><\/span>)<\/span>,\u00a023<\/span>\u00a0\u00a0-> \u00a0<\/span>without swapping<\/span><\/p>\n
—————————————————————————————––<\/span><\/span>\u200b<\/span><\/span><\/p>\n
Sorted Array: 3, 6, 10, 14, 18, 20, 23\u00a0<\/span><\/span><\/p>\n","protected":false},"excerpt":{"rendered":"
Time complexity: Worst-case: Best-case: Average-case: Find the smallest element and move it to the front. Then, find the second smallest and move it.<\/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-555","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\/555","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=555"}],"version-history":[{"count":4,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/555\/revisions"}],"predecessor-version":[{"id":863,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/555\/revisions\/863"}],"wp:attachment":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=555"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=555"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=555"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}