Selection sort algorithm python

Selection Sort: Algorithm explained with Python Code Example

SELECTION SORT is a comparison sorting algorithm that is used to sort a random list of items in ascending order. The comparison does not require a lot of extra space. It only requires one extra memory space for the temporal variable.

This is known as in-place sorting. The selection sort has a time complexity of O(n 2 ) where n is the total number of items in the list. The time complexity measures the number of iterations required to sort the list. The list is divided into two partitions: The first list contains sorted items, while the second list contains unsorted items.

By default, the sorted list is empty, and the unsorted list contains all the elements. The unsorted list is then scanned for the minimum value, which is then placed in the sorted list. This process is repeated until all the values have been compared and sorted.

In this Algorithm tutorial, you will learn:

• What is Selection Sort?
• How does selection sort work?
• Problem Definition
• Solution (Algorithm)
• Visual Representation
• Selection Sort Program using Python 3
• Code Explanation
• Time Complexity Of Selection Sort
• When to use selection sort?
• Advantages of Selection Sort
• Disadvantages of Selection Sort

How does selection sort work?

The first item in the unsorted partition is compared with all the values to the right-hand side to check if it is the minimum value. If it is not the minimum value, then its position is swapped with the minimum value.

Example:

• For example, if the index of the minimum value is 3, then the value of the element with index 3 is placed at index 0 while the value that was at index 0 is placed at index 3. If the first element in the unsorted partition is the minimum value, then it returns its positions.
• The element that has been determined as the minimum value is then moved to the partition on the left-hand side, which is the sorted list.
• The partitioned side now has one element, while the unpartitioned side has (n – 1) elements where n is the total number of elements in the list. This process is repeated over and over until all items have been compared and sorted based on their values.

Problem Definition

A list of elements that are in random order needs to be sorted in ascending order. Consider the following list as an example.

The above list should be sorted to produce the following results

Solution (Algorithm)

Step 1) Get the value of n which is the total size of the array

Step 2) Partition the list into sorted and unsorted sections. The sorted section is initially empty while the unsorted section contains the entire list

Step 3) Pick the minimum value from the unpartitioned section and placed it into the sorted section.

Step 4) Repeat the process (n – 1) times until all of the elements in the list have been sorted.

Visual Representation

Given a list of five elements, the following images illustrate how the selection sort algorithm iterates through the values when sorting them.

The following image shows the unsorted list

The first value 21 is compared with the rest of the values to check if it is the minimum value.

3 is the minimum value, so the positions of 21 and 3 are swapped. The values with a green background represent the sorted partition of the list.

The value 6 which is the first element in the unsorted partition is compared with the rest of the values to find out if a lower value exists

The value 6 is the minimum value, so it maintains its position.

The first element of the unsorted list with the value of 9 is compared with the rest of the values to check if it is the minimum value.

The value 9 is the minimum value, so it maintains its position in the sorted partition.

The value 33 is compared with the rest of the values.

The value 21 is lower than 33, so the positions are swapped to produce the above new list.

We only have one value left in the unpartitioned list. Therefore, it is already sorted.

The final list is like the one shown in the above image.

Selection Sort Program using Python 3

The following code shows the selection sort implementation using Python 3

def selectionSort( itemsList ): n = len( itemsList ) for i in range( n - 1 ): minValueIndex = i for j in range( i + 1, n ): if itemsList[j] < itemsList[minValueIndex] : minValueIndex = j if minValueIndex != i : temp = itemsList[i] itemsList[i] = itemsList[minValueIndex] itemsList[minValueIndex] = temp return itemsList el = [21,6,9,33,3] print(selectionSort(el))

Run the above code produces the following results

Code Explanation

The explanation for the code is as follows

Here is Code explanation:

1. Defines a function named selectionSort
2. Gets the total number of elements in the list. We need this to determine the number of passes to be made when comparing values.
3. Outer loop. Uses the loop to iterate through the values of the list. The number of iterations is (n – 1). The value of n is 5, so (5 – 1) gives us 4. This means the outer iterations will be performed 4 times. In each iteration, the value of the variable i is assigned to the variable minValueIndex
4. Inner loop. Uses the loop to compare the leftmost value to the other values on the right-hand side. However, the value for j does not start at index 0. It starts at (i + 1). This excludes the values that have already been sorted so that we focus on items that have not yet been sorted.
5. Finds the minimum value in the unsorted list and places it in its proper position
6. Updates the value of minValueIndex when the swapping condition is true
7. Compares the values of index numbers minValueIndex and i to see if they are not equal
8. The leftmost value is stored in a temporal variable
9. The lower value from the right-hand side takes the position first position
10. The value that was stored in the temporal value is stored in the position that was previously held by the minimum value
11. Returns the sorted list as the function result
12. Creates a list el that has random numbers
13. Print the sorted list after calling the selection Sort function passing in el as the parameter.

Time Complexity Of Selection Sort

The sort complexity is used to express the number of execution times it takes to sort the list. The implementation has two loops.

The outer loop which picks the values one by one from the list is executed n times where n is the total number of values in the list.

The inner loop, which compares the value from the outer loop with the rest of the values, is also executed n times where n is the total number of elements in the list.

Therefore, the number of executions is (n * n), which can also be expressed as O(n 2 ).

The selection sort has three categories of complexity namely;

• Worst case – this is where the list provided is in descending order. The algorithm performs the maximum number of executions which is expressed as [Big-O] O(n 2 )
• Best case – this occurs when the provided list is already sorted. The algorithm performs the minimum number of executions which is expressed as [Big-Omega] ?(n 2 )
• Average case – this occurs when the list is in random order. The average complexity is expressed as [Big-theta] ?(n 2 )

The selection sort has a space complexity of O(1) as it requires one temporal variable used for swapping values.

When to use selection sort?

The selection sort is best used when you want to:

• You have to sort a small list of items in ascending order
• When the cost of swapping values is insignificant
• It is also used when you need to make sure that all the values in the list have been checked.

Advantages of Selection Sort

The following are the advantages of the selection sort

• It performs very well on small lists
• It is an in-place algorithm. It does not require a lot of space for sorting. Only one extra space is required for holding the temporal variable.
• It performs well on items that have already been sorted.

Disadvantages of Selection Sort

The following are the disadvantages of the selection sort.

• It performs poorly when working on huge lists.
• The number of iterations made during the sorting is n-squared, where n is the total number of elements in the list.
• Other algorithms, such as quicksort, have better performance compared to the selection sort.

Summary:

• Selection sort is an in-place comparison algorithm that is used to sort a random list into an ordered list. It has a time complexity of O(n 2 )
• The list is divided into two sections, sorted and unsorted. The minimum value is picked from the unsorted section and placed into the sorted section.
• This thing is repeated until all items have been sorted.
• Implementing the pseudocode in Python 3 involves using two for loops and if statements to check if swapping is necessary
• The time complexity measures the number of steps required to sort the list.
• The worst-case time complexity happens when the list is in descending order. It has a time complexity of [Big-O] O(n 2 )
• The best-case time complexity happens when the list is already in ascending order. It has a time complexity of [Big-Omega] ?(n 2 )
• The average-case time complexity happens when the list is in random order. It has a time complexity of [Big-theta] ?(n 2 )
• The selection sort is best used when you have a small list of items to sort, the cost of swapping values does not matter, and checking of all the values is mandatory.
• The selection sort does not perform well on huge lists
• Other sorting algorithms, such as quicksort, have better performance when compared to the selection sort.

Источник

Selection Sort Python – A Quick Tutorial and Implementation Guide

So friends, in Selection Sort Python tutorial, we will learn how to sort data using selection sort method. We will also see selection sort algorithm, complexity and its implementation in python. So let’s start this tutorial.

Before diving into selection sort, we have to understand some basics of sorting. So first of all i am figuring out the most popular topic of data structure i.e., Sorting.

What Is Sorting – A Quick Overview

• Sorting means ordering the data either into ascending or descending order within the array.
• It is one of the most common data structure processing application.
• Sorting can be done on names, numbers and records

Why Sorting Is Effective ?

For understanding the effectiveness of sorting, we will take an example.

• Consider you are searching a phone number from your phone dictionary.
• You will easily get number because the names in the phone book have been sorted into alphabetical order.
• But if in your phone, numbers are not sorted then you can’t find phone numbers easily. And it takes long time.

So the conclusion is that if your numbers are in sorted order then it takes less time for searching. That means sorting greatly improves the efficiency of searching.

Sorting Methods

Sorting can be performed using several methods, they are following:

• Selection sort
• Merge sort
• Insertion sort
• Heap sort
• Bubble sort
• Quick sort
• Radix sort

So guys, we have just learned some basics of sorting, now we will discuss selection sort and see how to implement it in python.

Selection Sort Python Tutorial – Learn With Examples

Selection sort is very simple method. It is in-place comparison based method. In this method, we need to compare the numbers and need to place them in the correct position. So let’s start selection sort in python.

Selection Sort Mechanism ?

Now we will understand the mechanism of selection sort.

• In selection sort, we pick a minimum element from a list and place it in the sorted part of list.
• Initially we consider first element as minimum element and compare it with other elements of list.
• And during comparison, if we find a minimum element then its refers as new minimum element.
• When we complete one full round of comparison then the minimum element is swapped with first element.
• And this process will continued until we sort all the elements.

Selection Sort Algorithm

And now the question is that how we perform selection sort. So this is the answer :

1. Let’s consider the first element as sorted and the rest as unsorted
2. Assume the first element is the smallest element.
3. Checking, if the first element is less than each of the other elements in list, then do:
   1. If yes, do nothing
   2. If no, choose the other smaller element as minimum and repeat step 3

   Selection Sort Working Examples

   Now let us take a example for understanding selection sort mechanism.

   So consider a list which contains some elements.

   Источник