## About the article

In this article, we are going to take you through the one of the sorting algorithms, Selection sort step by step and perform a complete analysis of it. In this technique, we find the smallest element in each pass and place it in the appropriate positions to get the element in ascending or descending order. Number of passes required would be (n-1). For instance if we have 5 elements, it would require 4 passes. And in each pass we have n-k comparisons, where n is the number of elements and k is the pass number.

## Algorithm

Consider an example of array having 5 elements and we need to arrange them in ascending order. Since we have 5 elements, we require 4 passes to get the sorted array.

**5 4 3 1 2**

Pass 1 of 4, Here the smallest element would be 1 and exchange that with the swap position

Now, In pass 2 the swap position will be in 4 and the smallest number will be 2. Interchanging them will yield the following result.

In pass 3, The swap position and the smallest element lie in 3. So we cannot swap but proceed to the next swap.

In the final pass, the swap position lies in 5 and the smallest element is in 4. So we swap them in order to get the array arranged in ascending order.

## Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
package com.algorithm; public class SelectionSort { void selectionSort(int[] inputArr) { // Function getting the input array int n = inputArr.length; // Storing the length of the array in n for (int i = 0; i < n - 1; i++)// running the loop from 0 till n-1 { int minIndex = i; // Storing the index of the smallest number for (int j = i + 1; j < n; j++) { // loop for the numbers if (inputArr[j] < inputArr[minIndex]) // If the number is less than the minimum number { minIndex = j; // Finding lowest index } } // Swap the minimum found element with lowest index element int temp = inputArr[minIndex]; inputArr[minIndex] = inputArr[i]; inputArr[i] = temp; } } void printArray(int inputArr[]) { int n = inputArr.length; // Storing the length of the array in n for (int i = 0; i < n; ++i) // running the loop from 0 till the length of the array. System.out.print(inputArr[i] + " "); // printing it out System.out.println(); // new line } public static void main(String a[]) { // main function SelectionSort obj = new SelectionSort(); // creation of an object int inputArr[] = { 25, 10, 30, 15, 20, 10, 5 }; // giving elements as input System.out.println("Input Array before Selection Sort."); obj.printArray(inputArr); // calling the print function along with input. long then = System.nanoTime(); obj.selectionSort(inputArr); // calling the sort function along with input. long now = System.nanoTime(); System.out.println("\nSorted Array after Selection Sort."); obj.printArray(inputArr); // after sorting, you print the array. System.out.println("Time taken for sorting: "+(now-then)+" ns"); } } |

On execution of the above code, we get the output as shown below

1 2 3 4 5 6 |
Input Array before Selection Sort. 25 10 30 15 20 10 5 Sorted Array after Selection Sort. 5 10 10 15 20 25 30 Time taken for sorting: 4443 ns |

**Time complexity**

For n elements array,

In 1^{st} pass we have, (n-1) comparisons

In 2^{nd} pass we have, (n-2) comparisons

Similarly, in kth pass we have (n-k) comparisons.

Therefore, total comparisons are :

F(n)= (n-1) + (n-2)+ (n-3)+ .. +3+2+1 = n(n-1)/2 = O(n^{2})