**Selection sort** is a comparison-based sorting technique in which the minimum or the maximum element (according to the sorting order i.e. ascending or descending order respectively) are found out from the unsorted array and are placed at its **proper**** ****sorted position** after each pass. From the next pass, that element is not considered again in the sorting. The sorting takes place from the next element of the array. In this technique, after 1st pass, the array gets divided into two parts. One is the sorted part and another is the unsorted part. It is an **in-place** sorting algorithm as it does not require any extra space for sorting.

**PROCEDURE WITH EXAMPLE:**

In the case of selection sort if the number of elements is **n** then **n - 1** passes are required to sort the elements of the array which is similar to the bubble sort. For example, if we consider the unsorted array as follows with **5**** elements** then we **will need 5 - 1= ****4**** passes** to sort the data (**in ascending order**).

__Pass 1:__

In the first pass, it is considered that the minimum element is -7 and also the first index is considered as the index of the **minimum element of the array** (i.e. 0). **-7** **will be compared with ****54**. But as **-7**** is lesser than ****54** so there will be **no change** in the min value. After that **-7**** will be compared with ****-9**. As **-9**** is lesser than ****-7** so the min value **will be changed to ****-9** and the index of the **minimum**** element will be ****changed to 2**. Now, **-9** **is compared with**** 76** and **23**** **but in both cases, -**9**** is smaller** so there will be no change.

After completing this pass we will get the **minimum**** ****element ****-9** and the **index**** 2** which will be swapped with the first element of the array and the after the first pass the array will be:

**-9**** is now placed in its sorted position**.

__Pass 2:__

In the second pass, the **1st element will not be taken** in the sorting, the 2nd element i.e. **54**** will be considered as the minimum element** for the first time and the index will be stored as 1. Now, in a similar way to the 1st pass, it will be compared the rest of the elements of the array and in this pass, **-7** will be found as the **minimum element** whose index is **2**. So in this pass, the element **54** will be swapped with **-7** and the array after swapping will be:

__Pass 3:__

In the third pass, the third element of the array is considered as the minimum element in this case which is again **54** but here the index value is **2**. Now **54**** is compared with ****76** but as **54**** is lesser than ****76** so there will be **no change** in the minimum value, after that **54** is again compared to the last element **23**. As **23** is lesser than **54**, so the **minimum value will be changed to ****23** and the index will be **4**.

Now **23**** is swapped with ****54** and we will get the array:

__Pass 4:__

This is the last pass of the sorting technique. Only two elements are left to be sorted. For this pass, element **76**** is considered as the minimum element** and the index is **3**. Now **76**** will be compared with ****54**, in this case, **54** is less than **76** so **the ****minimum value**** will be ****54** and the index value is **4** which will be swapped with **76**. After this swapping we will get the final sorted array as follows:

```
INPUT:An unsorted array a[6,2,4,1,…………….,n]
OUTPUT:An sorted array a[1,2,3,4,5,…………..,n] (in ascending order)
PROCESS:
Step 1: [Taking the number of elements from the user]
Read n
Step 2: [Take the unsorted elements from the user in an array]
For i=0 to n
Read arr[i]
Step 3: [Print the unsorted array]
For i=0 to n
Print arr[i]
Step 4:[Sorting the unsorted elements]
For i=0 to i<n repeat
Set min<-a[i]
Set pos<-i
For j=i+1 to j<n
If(a[j]<min) then
Set min<-a[j]
Set pos<-j
[End of inner ‘For’ loop]
Set ta[i]
Set a[i]<-a[pos]
Set a[pos]<-t
[End of outer ‘For’ loop]
Step 5: [Printing the sorted array]
For i=0 to n
Print arr[i]
Step 6: Stop.
```

__CHARACTERISTICS:__

**1.** It is a comparison-based sorting technique.

**2.** It is an **in-place sorting**.

**3.** The array is divided into two parts while sorting, the left part is the sorted part and the right part is the unsorted part.

**4.** It cannot work efficiently for a large amount of data.

__APPLICATIONS:__

**1.** It is used when the memory cost does not matter.

**2.** It is used to sort a small amount of data.

__ADVANTAGES:__

**1.** It works efficiently on a small amount of data.

**2.** It is an** in-place sorting algorithm** and space complexity is **O(1)**.

**3.** It is very easy and simple to understand.

**4.** The sorting does not depend on the initial arrangement of the array elements before sorting

__DISADVANTAGES:__

**1.** It cannot work efficiently for a large number of elements.

**2.** Its performance is worse than insertion sort.

**3.** It is not a stable algorithm.

__TIME COMPLEXITY:__

For this above algorithm the **best case****, ****average case**,** and the ****worst-case**** time complexity of selection sort** will be the **same.**

For n number of elements the number of **comparisons in the first pass is ****n - 1**, in the **second pass ****n - 2,** and so on, and **in the last pass the number of comparisons is ****1** as explained earlier through example.

Therefore for n number of elements, the total number of comparisons to **sort the array** is:

__SPACE COMPLEXITY:__

The **space complexity of this algorithm** is **O(1)** as it is an **in-place** algorithm and it does not require any extra space for performing the sorting.

Related

- Bubble Sort
- Insertion Sort
- Quick Sort using recursion
- Quicksort Iterative
- Merge Sort using recursion
- Merge Sort Iterative
- 3 way Merge Sort
- Heap Sort using recursion
- Heap Sort Iterative
- Radix Sort for positive integer
- Bucket Sort
- Counting Sort
- Cocktail Sort
- Intro Sort
- Minmax Sort
- List Sort
- Tree Sort
- Shell Sort
- Gnome sort
- Comb Sort
- Bitonic Sort
- Tim Sort