Introduction to Selection Sort

Free AI web copilot to create summaries, insights and extended knowledge, download it at here

1133

Abstract

)</p><figure id="b5d5"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/1*_T30njQ_j-udFb_DnFWuBA.png"><figcaption>Image by author</figcaption></figure><p id="2071">Initially, the entire array will be the unsorted subarray as shown in the figure above. We find the minimum value 1 and swap it with 8, which is the first element of the unsorted subarray. The sorted subarray is colored in yellow. The next minimum value in the unsorted subarray is 3. We swap it with 4 which is the first element of the unsorted subarray. Thus, in the <i>i</i>ᵗʰ iteration, we swap the minimum value with the <i>i</i>ᵗʰ element of the array. After <i>m</i> number of iterations, the first <i>m </i>elements of the array will be in sorted order.</p><h2 id="b09c">Implementation in C</h2> <figure id="9089"> <div> <div>

            <iframe class="gist-iframe" src="/gist/Gunavaran/03c6734dabc281b959686fac983b179f.js" allowfullscreen="" frameborder="0" height="undefined" width="undefined">
          </div>
        </div>
    </figure></iframe></div></div></figure><h2 id

Options

="9274">Analysis of Selection Sort</h2><ol><li>Selection sort is an in-place algorithm which means it does not require additional memory space to perform sorting.</li><li>The time complexity is O(n²). Suppose the number of elements to be sorted is n, initially, the minimum value should be found among n elements which requires (n-1) comparisons. In the next iteration, it requires (n-2) comparisons. The following figure shows the number of comparisons required in each iteration.</li></ol><figure id="d0c2"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/1*HGJkWls2PCXT-AF21ExeEw.png"><figcaption>Image by author</figcaption></figure><p id="bbb0">Hence, the total number of comparisons required would be (n-1) + (n-2) + ….. + 2 + 1 which can be simplified as n(n-1)/2 → O(n²)</p><p id="2e35">Since its time complexity is quadratic, selection sort would be very inefficient when a large number of elements has to be sorted. However, since its space complexity is O(1), selection sort can be useful when the amount of memory available is very limited.</p><p id="dae5">Hope you enjoyed the article!</p></article></body>

Sorting algorithm 01

Image by author

Selection sort is one of the basic sorting algorithms which is easy to understand and implement. The idea is simple: given an array of elements to be sorted,

Divide the array into two subarrays: sorted and unsorted subarrays

In each iteration, find the maximum/minimum element in the unsorted subarray and swap it with the first element of the unsorted subarray. After swapping, the first element of the unsorted subarray will be appended to the sorted subarray. Swapping the minimum value will sort the elements in ascending order while swapping the maximum value will sort the elements in descending order.

Continue the iteration until the last element

Let’s look at an example for better understanding.

Suppose the array of numbers to be sorted in ascending order is (8,4,6,3,1,9,5)

Image by author

Initially, the entire array will be the unsorted subarray as shown in the figure above. We find the minimum value 1 and swap it with 8, which is the first element of the unsorted subarray. The sorted subarray is colored in yellow. The next minimum value in the unsorted subarray is 3. We swap it with 4 which is the first element of the unsorted subarray. Thus, in the iᵗʰ iteration, we swap the minimum value with the iᵗʰ element of the array. After m number of iterations, the first m elements of the array will be in sorted order.

Analysis of Selection Sort

Selection sort is an in-place algorithm which means it does not require additional memory space to perform sorting.

The time complexity is O(n²). Suppose the number of elements to be sorted is n, initially, the minimum value should be found among n elements which requires (n-1) comparisons. In the next iteration, it requires (n-2) comparisons. The following figure shows the number of comparisons required in each iteration.

Image by author

Hence, the total number of comparisons required would be (n-1) + (n-2) + ….. + 2 + 1 which can be simplified as n(n-1)/2 → O(n²)

Since its time complexity is quadratic, selection sort would be very inefficient when a large number of elements has to be sorted. However, since its space complexity is O(1), selection sort can be useful when the amount of memory available is very limited.

Hope you enjoyed the article!