Hits: 47

# Selection Sort Algorithm

#### In this tutorial, you will learn how selection sort works. Also, you will find working examples of selection sort in Python.

Selection sort is an algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list.

## How Selection Sort Works?

- Set the first element as
`minimum`

.

- Compare
`minimum`

with the second element. If the second element is smaller than`minimum`

, assign the second element as`minimum`

.Compare`minimum`

with the third element. Again, if the third element is smaller, then assign`minimum`

to the third element otherwise do nothing. The process goes on until the last element.

- After each iteration,
`minimum`

is placed in the front of the unsorted list.

- For each iteration, indexing starts from the first unsorted element. Step 1 to 3 are repeated until all the elements are placed at their correct positions.

## Selection Sort Algorithm

selectionSort(array, size) repeat (size - 1) times set the first unsorted element as the minimum for each of the unsorted elements if element < currentMinimum set element as new minimum swap minimum with first unsorted position end selectionSort

## Python Examples

```
/* Selection sort in Python */
def selectionSort(array, size):
for step in range(size):
min_idx = step
for i in range(step + 1, size):
/* to sort in descending order, change > to < in this line
select the minimum element in each loop */
if array[i] < array[min_idx]:
min_idx = i
/* put min at the correct position */
(array[step], array[min_idx]) = (array[min_idx], array[step])
data = [-2, 45, 0, 11, -9]
size = len(data)
selectionSort(data, size)
print('Sorted Array in Ascending Order:')
print(data)
```

## Complexity

Cycle | Number of Comparison |
---|---|

1st | (n-1) |

2nd | (n-2) |

3rd | (n-3) |

… | … |

last | 1 |

Number of comparisons: `(n - 1) + (n - 2) + (n - 3) + ..... + 1 = n(n - 1) / 2`

nearly equals to `n`

.^{2}

**Complexity** = `O(n`

^{2})

Also, we can analyze the complexity by simply observing the number of loops. There are 2 loops so the complexity is `n*n = n`

.^{2}

**Time Complexities:**

**Worst Case Complexity:**`O(n`

^{2})

If we want to sort in ascending order and the array is in descending order then, the worst case occurs.**Best Case Complexity:**`O(n`

^{2})

It occurs when the array is already sorted**Average Case Complexity:**`O(n`

^{2})

It occurs when the elements of the array are in jumbled order (neither ascending nor descending).

The time complexity of the selection sort is the same in all cases. At every step, you have to find the minimum element and put it in the right place. The minimum element is not known until the end of the array is not reached.

**Space Complexity:**

Space complexity is `O(1)`

because an extra variable `temp`

is used.

## Selection Sort Applications

The selection sort is used when:

- a small list is to be sorted
- cost of swapping does not matter
- checking of all the elements is compulsory
- cost of writing to a memory matters like in flash memory (number of writes/swaps is
`O(n)`

as compared to`O(n`

of bubble sort)^{2})

# Python Example for Beginners

## Two Machine Learning Fields

There are two sides to machine learning:

**Practical Machine Learning:**This is about querying databases, cleaning data, writing scripts to transform data and gluing algorithm and libraries together and writing custom code to squeeze reliable answers from data to satisfy difficult and ill defined questions. It’s the mess of reality.**Theoretical Machine Learning**: This is about math and abstraction and idealized scenarios and limits and beauty and informing what is possible. It is a whole lot neater and cleaner and removed from the mess of reality.

**Data Science Resources: Data Science Recipes and Applied Machine Learning Recipes**

**Introduction to Applied Machine Learning & Data Science for Beginners, Business Analysts, Students, Researchers and Freelancers with Python & R Codes @ Western Australian Center for Applied Machine Learning & Data Science (WACAMLDS) !!!**

Latest end-to-end Learn by Coding Recipes in Project-Based Learning:

**Applied Statistics with R for Beginners and Business Professionals**

**Data Science and Machine Learning Projects in Python: Tabular Data Analytics**

**Data Science and Machine Learning Projects in R: Tabular Data Analytics**

**Python Machine Learning & Data Science Recipes: Learn by Coding**

**R Machine Learning & Data Science Recipes: Learn by Coding**

**Comparing Different Machine Learning Algorithms in Python for Classification (FREE)**

Disclaimer: The information and code presented within this recipe/tutorial is only for educational and coaching purposes for beginners and developers. Anyone can practice and apply the recipe/tutorial presented here, but the reader is taking full responsibility for his/her actions. The author (content curator) of this recipe (code / program) has made every effort to ensure the accuracy of the information was correct at time of publication. The author (content curator) does not assume and hereby disclaims any liability to any party for any loss, damage, or disruption caused by errors or omissions, whether such errors or omissions result from accident, negligence, or any other cause.The information presented here could also be found in public knowledge domains.