Selection sort in Python
Tags: python, programming, programmers
Published: 2024-04-14 17:43:34

<p>Selection sort is a simple comparison-based sorting algorithm. It is relatively inefficient compared to other sorting algorithms making it not suitable for sorting large sets of data. However, understanding how it works is a foundational step for understanding more sophisticated sorting algorithms and generally how sorting algorithms operates.</p>

<p>This algorithm has an <strong>average </strong>and <strong>worst </strong>time complexities of <strong>O(n<sup>2</sup>)</strong>&nbsp;where&nbsp;<code>n</code> is the number of elements in the array/list.</p>

<p>Selection sort works <strong>in-place</strong> meaning that it reorders the elements in the original list rather than creating a new list. This makes it <strong>memory-efficient</strong>.</p>

<h2>Algorithm Description</h2>

<p>In selection sort, an array/list is divided into two segments; the&nbsp;&nbsp;<strong>sorted segment</strong>&nbsp;on the left and the&nbsp;<strong>unsorted segment&nbsp;</strong>on the right. Initially, the sorted segment is empty while the unsorted segment consists of the entire list. At each step,&nbsp; the algorithm&nbsp;<strong>selects&nbsp;</strong>the smallest unsorted element&nbsp;and exchanges it with the first element of the<strong> unsorted segment</strong>. This gradually increases the size of the sorted segment while reducing that of the unsorted segment and eventually the entire list becomes sorted.</p>

<p>The algorithm can be achieved through the following steps:</p>

<div class="tip">
<ol>
	<li>Set <code>MIN</code> to position <code>0</code>.</li>
	<li>Find the&nbsp;smallest element in the list.</li>
	<li>Swap it with the value at <code>MIN</code>.</li>
	<li>Increment <code>MIN</code>.</li>
	<li>Repeat steps <code>1-4 </code>until the list is sorted.</li>
</ol>
</div>

<h3>Example</h3>

<p>Consider if we start with the following unsorted list.</p>

<p><img alt="unsorted list" src="https://res.cloudinary.com/dgc50iktu/image/upload/v1713053240/39ed33b3-4bcb-47ca-9558-c553b1a1a094_xxdhbn.png" style="height:56px; width:432px" /></p>

<p>Elements in the sorted segment are in color green while those in the unsorted segment are in red.Two upper arrows will be used to indicate a swap operation.</p>

<p>At&nbsp; first step, the unsorted segment consists of the entire list. The <code>MIN </code>pointer is at the beginning of the list&nbsp;where the&nbsp; value is <code>4</code>,&nbsp; the smallest value in the list is <code>0</code>, so need to swap 4 and 0.</p>

<p><img alt="compare the first element" src="https://res.cloudinary.com/dgc50iktu/image/upload/v1713053241/29cdc7ae-1d73-42ee-81b4-0243917db157_l0ajtz.png" style="height:225px; width:432px" /></p>

<p>In the above step <code>0</code> and <code>4 </code>are swapped. The sorted segment now contains a single element. In the next step, the smallest unsorted element is<code> 1,&nbsp;</code>so we need to swap it with the value at the second position which is <code>6</code>.</p>

<p><img alt="compare 6 and 1" src="https://res.cloudinary.com/dgc50iktu/image/upload/v1713053240/d120b94a-e056-4172-9b7e-7976d9a9f069_bfpzll.png" /></p>

<p>And we go on like that with&nbsp; the next pairs i. <code>6</code> and <code>3.</code></p>

<p><img alt="Compare 6 and 3" src="https://res.cloudinary.com/dgc50iktu/image/upload/v1713053240/38d52134-a8e8-4b67-bf46-26e4b7111c24_uuz1gl.png" /></p>

<p>The sorted segment is becoming larger while the unsorted segment is diminishing.</p>

<p><img alt="4 is already sorted" src="https://res.cloudinary.com/dgc50iktu/image/upload/v1713053240/63c40207-cd45-42ab-b491-3b07753da839_z57whi.png" /></p>

<p>In the above step,<code> 4</code> is already sorted so we just move to the next element.</p>

<p><img alt="The last step" src="https://res.cloudinary.com/dgc50iktu/image/upload/v1713053240/109ebef6-556f-4a4a-882d-8d76a5f21c58_kuuyat.png" /></p>

<p>And finally, after the last step, the list is now sorted.</p>

<h2>Selection sort implementation</h2>

<p>The selection sort algorithm can be implemented with nested loops.</p>

<div class="autorun example">
<p>with for loops</p>

<pre>
<code class="language-python">def selection_sort(lst):
  for i in range(len(lst)):
    smallest = i

    for j in range(i + 1, len(lst)):
      if lst[j] &lt; lst[smallest]:
        smallest = j

    lst[i], lst[smallest] = lst[smallest], lst[i] #swap the elements

#sort a list
L = [99, 9, 0, 2, 1, 0, 1, 100, -2, 8, 7, 4, 3, 2]
selection_sort(L)

print("The sorted list is: ", L)</code></pre>
</div>

<p>In the above implementation, the sorted segment of the list starts at <code>0</code> and ends at<code> i </code>while the unsorted segment starts at<code> i + 1</code> and ends at<code> n-1</code> where <code>n</code> is the length of the list.&nbsp;</p>

<p>The outer loop traverses through all elements of the list. While inner loop&#39;s only traverses the unsorted segment (beginning at i.e&nbsp;<code>i + 1</code>&nbsp;) , it finds the position of the smallest unsorted element and assigns it to the <code>smallest </code>variable. The smallest element is then swapped with the outer loops current value in the<code>&nbsp;lst[i], lst[smallest] = lst[smallest], lst[i]</code>&nbsp;statement.</p>

<h4>with nested while loops</h4>

<p>We can also implement the selection sort algorithm using nested while loops, as shown below:</p>

<div class="autorun example">
<pre>
<code class="language-python">def selection_sort(lst):
  i = 0
  while i &lt; len(lst):

    smallest = i
    j = i + 1
    while j &lt; len(lst):
      if lst[j] &lt; lst[smallest]:
        smallest = j
      j += 1
    
    lst[i], lst[smallest] = lst[smallest], lst[i] #swap the elements
    i += 1

#sort a list
L = [99, 9, 0, 2, 1, 0, 1, 100, -2, 8, 7, 4, 3, 2]

selection_sort(L)
print("The sorted list is: ", L)</code></pre>
</div>

<h2>Descending selection sort</h2>

<p>To make the selection sort algorithm to sort the elements in descending order,&nbsp; we simply need to change the sign from <code>&lt;</code> to<code> &gt;</code> in the comparison line i.e from&nbsp;<code>&nbsp;if lst[j] &lt; lst[smallest]:</code> . to <code>if lst[j] &gt; lst[smallest]:&nbsp;</code>.This is as&nbsp; shown below:</p>

<div class="autorun example">
<pre>
<code class="language-python">#descending selection sort
def selection_sort(lst):
  for i in range(len(lst)):
    smallest = i

    for j in range(i + 1, len(lst)):
      if lst[j] &gt; lst[smallest]:
        smallest = j

    lst[i], lst[smallest] = lst[smallest], lst[i] #swap the elements

#sort a list
L = [99, 9, 0, 2, 1, 0, 1, 100, -2, 8, 7, 4, 3, 2]
selection_sort(L)

print("The sorted list is: ", L)</code></pre>
</div>

<h2>Complexity&nbsp; Analysis</h2>

<h4>space complexity</h4>

<p>The selection sort algorithm has a space complexity of<code> O(1)</code> . This means that it is memory-efficient as it does extra extra memory except for holding the basic variables e.g&nbsp;<code>smallest</code>.</p>

<h4>time complexity</h4>

<p>The presence of nested loops in the selection sort algorithm implies that it has a time complexity of <code>O(n<sup>2</sup>)</code>, this is for both average case and worst case scenarios.</p>
<div class="related"><h3>Related articles</h3><hr><ul><li><p><a class="text-success" href="https://www.pynerds.com/data-structures/implement-stack-data-structure-in-python/">Implement Stack data structure in Python</a><li><p><a class="text-success" href="https://www.pynerds.com/data-structures/implement-queue-data-structure-in-python/">Implement Queue data structure in Python</a><li><p><a class="text-success" href="https://www.pynerds.com/data-structures/implement-fixed-length-stack-in-python/">Implement Fixed-length stack in Python</a><li><p><a class="text-success" href="https://www.pynerds.com/data-structures/implement-inorder-tree-traversal-python/">Implement Inorder Tree Traversal - Python</a><li><p><a class="text-success" href="https://www.pynerds.com/data-structures/implement-bubble-sort-algorithm-in-python/">Implement bubble sort algorithm in Python</a></ul></div>