<p><strong><span style="color: #008000;">Selection sort</span></strong> is a simple sorting algorithm. It sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.</p>
<p>1) The subarray which is already sorted.<br />
2) Remaining subarray which is unsorted.</p>
<p>Initially, the sorted part is empty and the unsorted part is the entire list.</p>
<p>In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.</p>
<h4><strong><span style="color: #000080;">How Selection Sort Works?</span></strong></h4>
<pre><strong><span style="color: #008000;">arr[] = 66 24 16 20 17</span></strong>

<strong>// Find the minimum element in arr[0...4]
// and place it at beginning
<span style="color: #0000ff;">16 </span>24 66 20 17

// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
16 <span style="color: #0000ff;">17 </span><span style="color: #0000ff;"><span style="color: #000000;">66</span></span> 20 24

// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
16 17 <span style="color: #0000ff;">20</span> 66 24

// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
16 17 <span style="color: #000000;">20 </span><span style="color: #0000ff;">24 </span>66</strong></pre>
<p> ;</p>
<h4><strong><span style="color: #000080;">Algorithm</span></strong></h4>
<ul>
<li class="result notranslate"><span style="color: #0000ff;"><b>Step 1</b></span> − Set SMALL to location 0</li>
<li class="result notranslate"><span style="color: #0000ff;"><b>Step 2</b></span> − Search the minimum element in the list</li>
<li class="result notranslate"><span style="color: #0000ff;"><b>Step 3</b></span> − Swap with value at location SMALL</li>
<li class="result notranslate"><span style="color: #0000ff;"><b>Step 4</b></span> − Increment SMALL to point to next element</li>
<li class="result notranslate"><span style="color: #0000ff;"><b>Step 5</b></span> − Repeat until list is sorted</li>
</ul>
<p>Let’s take a look at the implementation.</p>
<!-- WP QUADS Content Ad Plugin v. 2.0.98.1 -->
<div class="quads-location quads-ad2" id="quads-ad2" style="float:none;margin:0px;">

</div>

<pre style="padding-left: 60px;"><code><strong>public class Sort {</strong>
<strong>
public static void selectionSort(int arr[],int small,int pos) {</strong>
<strong>
int temp;</strong>
<strong>
 for(int i=0;i<;=arr.length-2;i++)</strong>
<strong><span style="color: #0000ff;"> //set current element as minimum or small</span>
 {</strong>
<strong>
 small = arr[i];</strong>
<strong>
 pos = i;</strong>
<strong>
 for(int j=i+1;j<;=arr.length-1;j++)
</strong><strong> {</strong>
<strong><span style="color: #0000ff;"> //check the element to be small
</span> if(arr[j]<;small)</strong><strong>{</strong>
<strong>
 small = arr[j];</strong>
<strong>
 pos = j;</strong>
<strong>
 }</strong>
<strong>
 }</strong>
<strong><span style="color: #0000ff;"> //swap the minimum element with the current element
</span> temp=arr[i];</strong>
<strong>
 arr[i]=arr[pos];</strong>
<strong>
 arr[pos]=temp;</strong>
<strong>
 }</strong>
<strong>
}

public static void main(String[] strr) {

int small, pos;

int arr[] = {3, 2, 10, 17, 13, 9, 330, 42, 21, 90, 100};

small = arr[0];

pos = 0;

System.out.println(" Before sorting");

for(int j=0;j<;=arr.length-1;j++)

{

System.out.print(" "+arr[j]);

}

selectionSort(arr,small,pos);

System.out.println("\nAfter Sorting");

for(int j=0;j<;=arr.length-1;j++)

{

System.out.print(" "+arr[j]);

}

}</strong>
<strong>
}</strong>
</code></pre>
<h4><span style="color: #000080;"><strong>output:</strong> </span></h4>
<p><strong><span style="color: #0000ff;">Before sorting 3 2 10 17 13 9 330 42 21 90 100 </span></strong></p>
<p><strong><span style="color: #0000ff;">After Sorting 2 3 9 10 13 17 21 42 90 100 330</span></strong></p>
<h4><span style="color: #000080;"><strong>Time Complexity:</strong></span></h4>
<p>The time complexity of selection sort is <span style="color: #008000;"><strong>O(<i>n</i><sup>2</sup>)</strong></span> as there are two nested loops. One loop is for comparisons and another loop is for swapping between the elements.