# Selection Sort Algorithm

Selection Sort is an in-place sorting algorithm. The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. This algorithm is called selection sort since it repeatedly selects the smallest element.

**Selection Sort Algorithm**

In selection sort we maintain two subarray in the given array.

- The subarray which is
**already sorted**. - Remaining subarray which is
**unsorted**.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

**Program of Selection Sort**

#include<stdio.h> void printArray(int arr[], int size){ for(int i = 0; i < size; i++){ printf("%d ", arr[i]); } printf("\n"); } void swap(int *xp, int *yp){ int temp = *xp; *xp = *yp; *yp = temp; } void SelectionSort(int arr[], int size){ int i, j, min_index; //one by one boundary of the unsorted array decrease for(i = 0; i < size-1; i++){ min_index = i; //find the minimum element in the unsorted array for(j = i+1; j < size; j++){ if(arr[j] < arr[min_index]){ min_index = j; } } //swap the minimum element with the first element of //unsorted array. swap(&arr[i], &arr[min_index]); } } // Driver Program int main(){ int arr[] = {4,6,7,5,9,3,1,8,2}; int size = sizeof(arr)/sizeof(arr[0]); SelectionSort(arr, size); printf("======Sorted Array is======\n"); printArray(arr, size); return 0; }

**Output:**

======Sorted Array is====== 1 2 3 4 5 6 7 8 9

**Performance**

In selection sort perform two operation:

- Traverse the array to find the minimum array
- Swap the element

We traverse the array \((n-1)\) times. In first iteration we traverse \(n\) element, in second iteration \((n-1)\) element and so on.

So total traversal = \((n-1) + (n-2) + (n-3) + … + 1\)

**Hence traversal time is:** \( n*\frac{(n-1)}{2}\)

In each iteration we perform one swap operation. Hence maximum number of swap operation is \(n\).

**So time complexity of the selection sort is** \(\mathcal O(n^2)\).

**Space Complexity:**

Selection sort require \(\mathcal O(1)\) auxiliary space.

**Application of Selection Sort**

- The good thing about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation.
- Selection sort works well for small files. It is used for sorting the files with very large values and small keys. This is because of the fact that selection is made based on the keys and swaps are made only when required.

This article is contributed by Ram Kripal. If you like eLgo Academy and would like to contribute, you can mail your article to admin@elgoacademy.org. See your article appearing on the eLgo Academy page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.