** Selection Sort Algorithm **is one of the easiest

*sorting algorithms*in

*Data Structures*. It is a comparison-based

*sorting algorithm*. It is used to arrange the elements of an array (in ascending order). In this article, we’re going to see how we can implement selection sort in data structures using the Python programming language.

__For Example__

__For Example__

**INPUT Array – **16 12 96 42 21

**OUTPUT Array – ** 12 16 21 42 96

*Table of Contents:*

*Table of Contents:*

- How does the Selection sort algorithm work?
- Algorithm
- Pseudocode of selection sort
*Selection sort algorithm*in Python*Selection sort algorithm*in C++- Time Complexity of Selection sort
- Space Complexity of Selection Sort
- In-place behavior
- Is Selection sort an in-place sorting algorithm?
- Is the Selection sort show adaptive nature?
- Features

*Working of Selection Sort Algorithm*

*Working of Selection Sort Algorithm*

In Selection Sort, the given array is divided into two parts – the sorted part and the unsorted part. The sorted part is at the left end of the array and the unsorted part is at the right end of the array respectively.

At the beginning of the algorithm, the sorted part is completely empty and the unsorted part consists of the whole array. But as algo proceeds, the elements that are being sorted becomes a part of the sorted array, and the remaining subarray comes under the unsorted part.

In this sorting algorithm, with every passing iteration, the least valued or the minimum element from the unsorted array is selected, using the **linear search technique** after that the selected element is swapped with the first element of that array. The new element added at the beginning becomes a part of the sorted array.

**Let us understand this with an example.**

**Consider the given array of elements – 12 45 67 2 3**

*Algorithm*

*Algorithm*

Selection_Sort ( array a, length n)

Step 1: Start loop from i = 0 to n-2

Step 2: Select smallest element among a[i] , … a[n-1]

Step 3: Swap element with a[i]

*Pseudocode*

*Pseudocode*

function selection sort A[] : array of elements n : number of elements of an array for i=1 to n-1 /* fix first element of the array as minimum */ min=i /*check for the smallest element by comparing with all the other elements */ for j=i+1 to n if A[j] < A[min] then min=j end if end for /* swap the minimum element with the first element of the array */ if index_min!=i then swap A[min] amd A[i] end if end for end function

*Selection sort python code*

*Selection sort python code*

### Code:

#Code by Copyassignment.com # function def selection_sort(A): for i in range(len(A)): # Finding the minimum element in remaining unsorted array min_idx = i for j in range(i+1, len(A)): if A[min_idx] > A[j]: min_idx = j # Swapping A[i] with minimum element A[i], A[min_idx] = A[min_idx], A[i] #Driver Code arr = [12,45,67,2,3,9] selection_sort(arr) #Calling Function print("Final array after sorting :\n") for i in range(len(arr)): print(arr[i]) #Printing array after sorting

### Output:

Final array after sorting : 2 3 9 12 45 67

*Selection sort algorithm in C++*

*Selection sort algorithm in C++*

### Code:

// Code by copyassignment.com #include <iostream> using namespace std; void swap(int *xp, int *yp) { int temp = *xp; *xp = *yp; *yp = temp; } void Selection_Sort(int arr[], int n) { int min_idx; // moving boundary of unsorted sub array for (int i = 0; i < n - 1; i++) { // Find the minimum element in unsorted array min_idx = i; for (int j = i + 1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; // Swapping A[i] element with minimum element swap(&arr[min_idx], &arr[i]); } } // Driver program to test above functions int main() { int n; cout << "Enter the size of array : " << endl; //Taking size of array cin >> n; int arr[n]; cout << "Enter " << n << " elements:\n"; for (int i = 0; i < n; i++) cin >> arr[i]; //Taking elements of array Selection_Sort(arr, n); //Calling Function cout << "Sorted array: \n"; for (int i = 0; i < n; i++) cout << arr[i] << " "; //Printing sorted array return 0; }

### Output:

Enter the size of array : 4 Enter 4 elements: 32 54 76 87 Sorted array: 32 54 76 87

*Time complexity of selection sort*

*Time complexity of selection sort*

**Time Complexity –** In an algorithm, the time complexity is defined as the amount of time taken by the algorithm to completely run and execute all its operations is known as the time complexity of an algorithm.

*Selection Sort Algorithm *has a time complexity of **O(n ^{2}) **for all the three cases as explained below.

**Best-Case Complexity –**Best case is when all the elements of the original array are already sorted. But, even in this case, the algorithm will perform all the comparison operations for each and every element of the array. Thus, its time complexity will remain the same i.e.,**O(n**.^{2})**Average-Case Complexity –**This is the generalized amount of time taken by the algorithm for all the possible averaged inputs. Here, again some of the swapping operations and all the comparison operations will be performed for the elements of the array. As a result, the time complexity will remain the same i.e.,**O(n**.^{2})**Worst-Case Complexity –**Worst case is considered when the given array is reversely sorted i.e., all the elements in descending order. This is the case where all the sorting operations and all the comparison operations will be performed for all the elements of the array. Thus, time complexity, in this case, will be again**O(n**.^{2})

*Space complexity*

*Space complexity*

**Space Complexity –** For an algorithm, space complexity is defined as the memory space occupied by it to run and execute all its operations.

In this algorithm, all the elements are swapped within the space of a single array, given initially and does not require any extra memory space or array or any other data structure for its execution except one variable **temp,** which is used to store the element being swapped at a temporary location. Thus, it has a space complexity of **O(1)**.

*In-place sorting algorithm?*

*In-place sorting algorithm?*

Yes, Selection sort is an in-place sorting algorithm because it does not require any other array or data structure to perform its operations. All the swapping operations are done within a single array.

*Stable sorting algorithm?*

*Stable sorting algorithm?*

No, Selection Sort is an unstable sorting algorithm because it works on the principle of initially finding the minimum element from the list and then putting it at its correct position by swapping it with the element which is present at the beginning of the unsorted array. Due to this swapping, the element present in the later part of the array will come at the beginning even if they have the same value.

*Let us understand this with an example –*

**Input – **4_{A} 5 3 2 4_{B} 1

**Output – **1 2 3 4_{B} 4_{A} 5

If it would have been a stable sorting algorithm then the output would be **1 2 3 4 _{A} 4_{B} 5 **

**Note: **Subscripts are added only for the purpose of understanding.

*Adaptive sorting algorithm?*

*Adaptive sorting algorithm?*

No, it is a non-adaptive sorting algorithm because even if some of the elements of the array are sorted itself, the *Selection Sort Algorithm *will not take into account the ‘already sorted’ elements and it will reorder them as all the comparisons would be made to confirm their sortedness.

*Features of selection sort*

*Features of selection sort*

- It is the second slowest sorting algorithm after bubble sort because it occupies memory space for a longer time. Therefore, it is not suitable for large data sets.
*Selection Sort Algorithm*can be applied on linked list data structure as well.- It is preferably used when the cost of performing writing operations to memory is taken into consideration like in the case of flash memory.

*Thanks for reading!*

*If you found this article useful please support us by commenting “nice article” and don’t forget to share it with your friends and enemies*!

*Happy Coding!*

Introduction to Searching Algorithms: Linear Search Algorithm

Bubble Sort Algorithm In Data Structures & Algorithms using Python

Merge Sort Algorithm in Python

Sorting Algorithms and Searching Algorithms in Python

Shutdown Computer with Voice in Python