{"id":2958,"date":"2017-11-14T15:30:52","date_gmt":"2017-11-14T15:30:52","guid":{"rendered":"http:\/\/www.csestack.org\/?p=2958"},"modified":"2019-03-22T18:46:15","modified_gmt":"2019-03-22T13:16:15","slug":"python-selection-sort","status":"publish","type":"post","link":"https:\/\/www.csestack.org\/python-selection-sort\/","title":{"rendered":"Complete Python Selection Sort Algorithm | Code Complexity"},"content":{"rendered":"<p>As we know, sorting is a technique to arrange the elements in the array either\u00a0in ascending or descending\u00a0order. And there are multiple sorting algorithms such as <a href=\"https:\/\/www.csestack.org\/bubble-sort-in-c-with-explanation-algorithm-program-complexity\/\">bubble sort<\/a>, insertion sort,\u00a0<a href=\"https:\/\/www.csestack.org\/quicksort\/\">quick sort<\/a>, selections sort&#8230;<\/p>\n<p>Here we will see Python selection sort.<\/p>\n<div class=\"toc\"><strong>Table of Contents<\/strong><\/p>\n<ul>\n<li><a href=\"#algorithm\">What is Selection Sort Algorithm?<\/a><\/li>\n<li><a href=\"#python-program\">Selection Sort in Python<\/a><\/li>\n<li><a href=\"#time-complexity\">Time Complexity of Selection Sort<\/a><\/li>\n<li><a href=\"#memory-complexity\">Memory Complexity of Selection Sort<\/a><\/li>\n<\/ul>\n<\/div>\n<p>Before writing the code&#8230;<\/p>\n<h3 style=\"text-align: center;\" id=\"algorithm\">What is Selection Sort Algorithm?<\/h3>\n<p>Here is pseudo-algorithm for selection sorting.<\/p>\n<ul>\n<li>Take the array (containing elements to sort) as an input<\/li>\n<li>Iterate through all the elements in the array (says element as i)<\/li>\n<li>Find the smallest elements from rest of the array (array elements next to i&#8217;s)<\/li>\n<li>Swap the smallest element with i<\/li>\n<\/ul>\n<p>If you understand the pseudo-algorithm, I would like if you minimize the browser and try to write code yourself.<\/p>\n<h3 style=\"text-align: center;\" id=\"python-program\">Python Selection Sort Program<\/h3>\n<pre class=\"brush: python\">#swap two elements in nArr at postion i and j\r\ndef swap(i, j, nArr):\r\n\u00a0\u00a0\u00a0 if i!=j:\u00a0\u00a0\u00a0\u00a0\u00a0\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 temp = nArr[j]\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 nArr[j] = nArr[i]\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 nArr[i] = temp\r\n\r\n#function to sort elements in the list\r\ndef selectionSort(nArr):\u00a0\u00a0\u00a0\u00a0\r\n\u00a0\u00a0\u00a0 for i in range(0, len(nArr)):\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 small = i\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 for j in range(i+1, len(nArr)):\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 if nArr[j] &lt; nArr[small]:\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 small = j\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 swap(i, small, nArr)\r\n\r\n#list containing elements to sort\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\r\nnArr = [34,456, 5, 5,67]\r\nselectionSort(nArr)\r\nprint(nArr)\r\n<\/pre>\n<p>Here in the above program, I have a hardcoded list. You can even take the <a href=\"http:\/\/www.csestack.org\/how-to-get-user-input-in-python\/\">list elements as user input<\/a>.<\/p>\n<h4><strong>Output:<\/strong><\/h4>\n<p><samp>[5, 5, 34, 67, 456]<\/samp><\/p>\n<p>In the first pass, the first element in the array will be in sorted position. After the second pass, two elements in the array will be sorted.<\/p>\n<p>Likewise&#8230;<\/p>\n<p>If you have n elements, after n-1 pass, n-1 elements will be sorted. If you arrange first n-1 elements in the array in the right position, the last element automatically will be in the right position.<\/p>\n<p>So in each pass, you need to swap the elements at most one time. So in selection sort, you <strong>need a maximum n-1 pass and so the swaps<\/strong> to sort all the elements in the array.<\/p>\n<p>If you compare with the bubble sort, in every pass we swap the elements multiple times. So you can consider the selection sort as improvement in bubble sort.<\/p>\n<p>Above code, sort the elements in ascending order. If you want the same program to sort elements in descending order, replace <code>&lt;<\/code> with <code>&gt;<\/code>\u00a0inside\u00a0the function\u00a0<code>selectioSort()<\/code>.<\/p>\n<p>For sorting, you need to take <a href=\"http:\/\/www.csestack.org\/python-numeric-data-types-examples\/\">Numeric data types values<\/a>. Just to give little tweak, you can also use a list containing characters to sort.<\/p>\n<h3 style=\"text-align: center;\" id=\"time-complexity\">Time complexity of Selection Sort<\/h3>\n<p>As you have to compare each element with other elements from an array list, it has a time complexity of <code>o(n^2)<\/code> in all three cases (best, average and worst case).<\/p>\n<p>As it takes <code>O(n^2)<\/code> time, it is not considered as an efficient algorithm for sorting if you have minimal time.<\/p>\n<h3 style=\"text-align: center;\" id=\"memory-complexity\">Memory Complexity of Selection Sort<\/h3>\n<p>Selection sort does not require any extra memory (except for swapping). So, it takes constant time <code>O(1)<\/code>, despite the number of elements in the array.<\/p>\n<p>You need to swap the elements, only if it is required. If your array is already sorted, there will be zero numbers of swapping.<\/p>\n<p><strong>Just to clarify&#8230;<\/strong><\/p>\n<p>Here we are using the list to sort. As <a href=\"http:\/\/www.csestack.org\/difference-between-mutable-and-immutable-in-python\/\">tuple is an immutable data structure<\/a> in Python, you can not use tuple for sorting. For more, you can read\u00a0<a href=\"http:\/\/www.csestack.org\/difference-tuple-list-python\/\">List vs Tuple in Python<\/a>.<\/p>\n<p>If you understand the logic behind Python selection sort, it is easy to implement in any programming language. Any doubt? Write in the comment section.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Write the complete code for Python selection sort. Explain the algorithm with time and memory complexity.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7,73],"tags":[72],"class_list":["post-2958","post","type-post","status-publish","format-standard","hentry","category-code","category-python","tag-python"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.3 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Complete Python Selection Sort Algorithm | Code Complexity<\/title>\n<meta name=\"description\" content=\"Write the complete code for Python selection sort. Explain the algorithm with time and memory complexity.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.csestack.org\/python-selection-sort\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Complete Python Selection Sort Algorithm | Code Complexity\" \/>\n<meta property=\"og:description\" content=\"Write the complete code for Python selection sort. Explain the algorithm with time and memory complexity.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.csestack.org\/python-selection-sort\/\" \/>\n<meta property=\"og:site_name\" content=\"CSEstack\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/aniruddha.ca\" \/>\n<meta property=\"article:author\" content=\"https:\/\/www.facebook.com\/aniruddha.ca\" \/>\n<meta property=\"article:published_time\" content=\"2017-11-14T15:30:52+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2019-03-22T13:16:15+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.csestack.org\/wp-content\/uploads\/2024\/01\/csestack-blog.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1280\" \/>\n\t<meta property=\"og:image:height\" content=\"720\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"Aniruddha Chaudhari\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@ani_chaudhari\" \/>\n<meta name=\"twitter:site\" content=\"@ani_chaudhari\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Aniruddha Chaudhari\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/www.csestack.org\\\/python-selection-sort\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.csestack.org\\\/python-selection-sort\\\/\"},\"author\":{\"name\":\"Aniruddha Chaudhari\",\"@id\":\"https:\\\/\\\/www.csestack.org\\\/#\\\/schema\\\/person\\\/634ef1a9c4f38b0d340c6d45fa771218\"},\"headline\":\"Complete Python Selection Sort Algorithm | Code Complexity\",\"datePublished\":\"2017-11-14T15:30:52+00:00\",\"dateModified\":\"2019-03-22T13:16:15+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/www.csestack.org\\\/python-selection-sort\\\/\"},\"wordCount\":520,\"commentCount\":2,\"publisher\":{\"@id\":\"https:\\\/\\\/www.csestack.org\\\/#\\\/schema\\\/person\\\/634ef1a9c4f38b0d340c6d45fa771218\"},\"keywords\":[\"Python\"],\"articleSection\":[\"Code\",\"Python\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/www.csestack.org\\\/python-selection-sort\\\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/www.csestack.org\\\/python-selection-sort\\\/\",\"url\":\"https:\\\/\\\/www.csestack.org\\\/python-selection-sort\\\/\",\"name\":\"Complete Python Selection Sort Algorithm | Code Complexity\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.csestack.org\\\/#website\"},\"datePublished\":\"2017-11-14T15:30:52+00:00\",\"dateModified\":\"2019-03-22T13:16:15+00:00\",\"description\":\"Write the complete code for Python selection sort. Explain the algorithm with time and memory complexity.\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/www.csestack.org\\\/python-selection-sort\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/www.csestack.org\\\/python-selection-sort\\\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/www.csestack.org\\\/python-selection-sort\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/www.csestack.org\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Complete Python Selection Sort Algorithm | Code Complexity\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/www.csestack.org\\\/#website\",\"url\":\"https:\\\/\\\/www.csestack.org\\\/\",\"name\":\"CSEstack\",\"description\":\"Computer Science &amp; Programming Portal\",\"publisher\":{\"@id\":\"https:\\\/\\\/www.csestack.org\\\/#\\\/schema\\\/person\\\/634ef1a9c4f38b0d340c6d45fa771218\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/www.csestack.org\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\\\/\\\/www.csestack.org\\\/#\\\/schema\\\/person\\\/634ef1a9c4f38b0d340c6d45fa771218\",\"name\":\"Aniruddha Chaudhari\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/www.csestack.org\\\/wp-content\\\/uploads\\\/2019\\\/03\\\/Aniruddha-Chaudhari.jpg\",\"url\":\"https:\\\/\\\/www.csestack.org\\\/wp-content\\\/uploads\\\/2019\\\/03\\\/Aniruddha-Chaudhari.jpg\",\"contentUrl\":\"https:\\\/\\\/www.csestack.org\\\/wp-content\\\/uploads\\\/2019\\\/03\\\/Aniruddha-Chaudhari.jpg\",\"width\":634,\"height\":634,\"caption\":\"Aniruddha Chaudhari\"},\"logo\":{\"@id\":\"https:\\\/\\\/www.csestack.org\\\/wp-content\\\/uploads\\\/2019\\\/03\\\/Aniruddha-Chaudhari.jpg\"},\"description\":\"I am a Python enthusiast who loves Linux and Vim. I hold a Master of Computer Science degree from NIT Trichy and have 10 years of experience in the IT industry, focusing on the Software Development Lifecycle from Requirements Gathering, Design, Development to Deployment. I have worked at IBM, Ericsson, and NetApp, and I share my knowledge on CSEstack.org.\",\"sameAs\":[\"https:\\\/\\\/www.csestack.org\",\"https:\\\/\\\/www.facebook.com\\\/aniruddha.ca\",\"pythonwithani\",\"https:\\\/\\\/www.linkedin.com\\\/in\\\/aniruddha28\\\/\",\"https:\\\/\\\/x.com\\\/ani_chaudhari\",\"https:\\\/\\\/www.youtube.com\\\/channel\\\/UCw0a__B0eJsvCujkSIfLTAA\"],\"url\":\"https:\\\/\\\/www.csestack.org\\\/author\\\/anicse\\\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Complete Python Selection Sort Algorithm | Code Complexity","description":"Write the complete code for Python selection sort. Explain the algorithm with time and memory complexity.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.csestack.org\/python-selection-sort\/","og_locale":"en_US","og_type":"article","og_title":"Complete Python Selection Sort Algorithm | Code Complexity","og_description":"Write the complete code for Python selection sort. Explain the algorithm with time and memory complexity.","og_url":"https:\/\/www.csestack.org\/python-selection-sort\/","og_site_name":"CSEstack","article_publisher":"https:\/\/www.facebook.com\/aniruddha.ca","article_author":"https:\/\/www.facebook.com\/aniruddha.ca","article_published_time":"2017-11-14T15:30:52+00:00","article_modified_time":"2019-03-22T13:16:15+00:00","og_image":[{"width":1280,"height":720,"url":"https:\/\/www.csestack.org\/wp-content\/uploads\/2024\/01\/csestack-blog.jpg","type":"image\/jpeg"}],"author":"Aniruddha Chaudhari","twitter_card":"summary_large_image","twitter_creator":"@ani_chaudhari","twitter_site":"@ani_chaudhari","twitter_misc":{"Written by":"Aniruddha Chaudhari","Est. reading time":"3 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/www.csestack.org\/python-selection-sort\/#article","isPartOf":{"@id":"https:\/\/www.csestack.org\/python-selection-sort\/"},"author":{"name":"Aniruddha Chaudhari","@id":"https:\/\/www.csestack.org\/#\/schema\/person\/634ef1a9c4f38b0d340c6d45fa771218"},"headline":"Complete Python Selection Sort Algorithm | Code Complexity","datePublished":"2017-11-14T15:30:52+00:00","dateModified":"2019-03-22T13:16:15+00:00","mainEntityOfPage":{"@id":"https:\/\/www.csestack.org\/python-selection-sort\/"},"wordCount":520,"commentCount":2,"publisher":{"@id":"https:\/\/www.csestack.org\/#\/schema\/person\/634ef1a9c4f38b0d340c6d45fa771218"},"keywords":["Python"],"articleSection":["Code","Python"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/www.csestack.org\/python-selection-sort\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/www.csestack.org\/python-selection-sort\/","url":"https:\/\/www.csestack.org\/python-selection-sort\/","name":"Complete Python Selection Sort Algorithm | Code Complexity","isPartOf":{"@id":"https:\/\/www.csestack.org\/#website"},"datePublished":"2017-11-14T15:30:52+00:00","dateModified":"2019-03-22T13:16:15+00:00","description":"Write the complete code for Python selection sort. Explain the algorithm with time and memory complexity.","breadcrumb":{"@id":"https:\/\/www.csestack.org\/python-selection-sort\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.csestack.org\/python-selection-sort\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.csestack.org\/python-selection-sort\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.csestack.org\/"},{"@type":"ListItem","position":2,"name":"Complete Python Selection Sort Algorithm | Code Complexity"}]},{"@type":"WebSite","@id":"https:\/\/www.csestack.org\/#website","url":"https:\/\/www.csestack.org\/","name":"CSEstack","description":"Computer Science &amp; Programming Portal","publisher":{"@id":"https:\/\/www.csestack.org\/#\/schema\/person\/634ef1a9c4f38b0d340c6d45fa771218"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.csestack.org\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":["Person","Organization"],"@id":"https:\/\/www.csestack.org\/#\/schema\/person\/634ef1a9c4f38b0d340c6d45fa771218","name":"Aniruddha Chaudhari","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.csestack.org\/wp-content\/uploads\/2019\/03\/Aniruddha-Chaudhari.jpg","url":"https:\/\/www.csestack.org\/wp-content\/uploads\/2019\/03\/Aniruddha-Chaudhari.jpg","contentUrl":"https:\/\/www.csestack.org\/wp-content\/uploads\/2019\/03\/Aniruddha-Chaudhari.jpg","width":634,"height":634,"caption":"Aniruddha Chaudhari"},"logo":{"@id":"https:\/\/www.csestack.org\/wp-content\/uploads\/2019\/03\/Aniruddha-Chaudhari.jpg"},"description":"I am a Python enthusiast who loves Linux and Vim. I hold a Master of Computer Science degree from NIT Trichy and have 10 years of experience in the IT industry, focusing on the Software Development Lifecycle from Requirements Gathering, Design, Development to Deployment. I have worked at IBM, Ericsson, and NetApp, and I share my knowledge on CSEstack.org.","sameAs":["https:\/\/www.csestack.org","https:\/\/www.facebook.com\/aniruddha.ca","pythonwithani","https:\/\/www.linkedin.com\/in\/aniruddha28\/","https:\/\/x.com\/ani_chaudhari","https:\/\/www.youtube.com\/channel\/UCw0a__B0eJsvCujkSIfLTAA"],"url":"https:\/\/www.csestack.org\/author\/anicse\/"}]}},"_links":{"self":[{"href":"https:\/\/www.csestack.org\/wp-json\/wp\/v2\/posts\/2958","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.csestack.org\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.csestack.org\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.csestack.org\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.csestack.org\/wp-json\/wp\/v2\/comments?post=2958"}],"version-history":[{"count":9,"href":"https:\/\/www.csestack.org\/wp-json\/wp\/v2\/posts\/2958\/revisions"}],"predecessor-version":[{"id":4955,"href":"https:\/\/www.csestack.org\/wp-json\/wp\/v2\/posts\/2958\/revisions\/4955"}],"wp:attachment":[{"href":"https:\/\/www.csestack.org\/wp-json\/wp\/v2\/media?parent=2958"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.csestack.org\/wp-json\/wp\/v2\/categories?post=2958"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.csestack.org\/wp-json\/wp\/v2\/tags?post=2958"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}