Python Program for Selection Sort

What exactly is sorting? What’s the big deal about it? In this part, we will attempt to answer these questions.

We’ve sorted everything from books in a library to words in a dictionary to database entries and processor instructions on a number of occasions.
This means that when we sort things, we must first determine the criteria by which we will organize the items in the sequence provided to us. For the purposes of this lesson, we’ll suppose that the criteria is a number’s value, and we’ll sort a set of numbers.

The most significant goal of sorting in computer science is to create efficient algorithms. Binary Search is a lightning-fast search algorithm that would be impossible to use in an unsorted set of objects.

On sorted data, almost all set operations are extremely fast.

Apart from creating efficient algorithms, sorting is employed when a program’s sole purpose is to sort things, such as when working with a deck of cards. As a result, sorting algorithms are one of the most important things for a programmer to understand.

Sorting algorithms are programs that reorganize a huge number of elements into a certain order, such as from highest to lowest, or vice versa, or even alphabetically.

These algorithms take an input list, process it (that is, perform operations on it), and then return a sorted list.
The importance of sorting comes from the idea that if data is kept in a sorted fashion, data searching may be greatly improved. Sorting can also be used to display data in a more legible fashion. The instances of sorting in real-life circumstances are as follows:

Telephone Directory :The telephone directory keeps track of people’s phone numbers, which are classified by their names so that they may be quickly found.

Dictionary : The dictionary organizes terms alphabetically so that searching for a specific word is simple.

Examples:

Sorting in Ascending order

Example1:

Input:

givenlist = [8, 132, 22, 34, 57, 2, 1, 9, 45, 87, 63, 80, 26, 65, 132]

Output:

printing the list before sorting :
8 132 22 34 57 2 1 9 45 87 63 80 26 65 132 
printing the list after sorting :
1 2 8 9 22 26 34 45 57 63 65 80 87 132 132

Example2:

Input:

givenlist = ["hello", "this", "is", "BTechGeeeks", "python", "new", "online",
                   "platform", "for", "all", "students", "who", "are", "excited", "about", "coding"]

Output:

printing the list before sorting :
hello this is BTechGeeeks python new online platform for all students who are excited about coding 
printing the list after sorting :
BTechGeeeks about all are coding excited for hello is new online platform python students this who

Sorting in descending order example

Example 3:

Input:

givenlist = [8, 132, 22, 34, 57, 2, 1, 9, 45, 87, 63, 80, 26, 65, 132]

Output:

printing the list before sorting :
8 132 22 34 57 2 1 9 45 87 63 80 26 65 132 
printing the list after sorting :
132 132 87 80 65 63 57 45 34 26 22 9 8 2 1

Example4:

Input:

givenlist = ["hello", "this", "is", "BTechGeeeks", "python", "new", "online",
                   "platform", "for", "all", "students", "who", "are", "excited", "about", "coding"]

Output:

printing the list before sorting :
hello this is BTechGeeeks python new online platform for all students who are excited about coding 
printing the list after sorting :
who this students python platform online new is hello for excited coding are all about BTechGeeeks

Explore more instances related to python concepts from Python Programming Examples Guide and get promoted from beginner to professional programmer level in Python Programming Language.

1)Selection Sort Introduction

Selection Sort is a comparison sorting algorithm that uses a random list of items to sort them in ascending order. The comparison does not necessitate a lot of extra room. It just need one more memory space for the time variable.

This is referred to as in-place sorting. The temporal complexity of the selection sort is O(n^2), where n is the total number of items in the list. The number of iterations necessary to sort the list is measured by the time complexity. The list is separated into two sections: the first contains sorted items, and the second contains unsorted items.

The sorted list is empty by default, but the unsorted list contains all of the entries. The minimal value is then found in the unsorted list and entered into the sorted list. This procedure is repeated until all of the data have been sorted and compared.

2)Working of Selection Sort

To determine if the first item in the unsorted partition is the minimum value, it is compared to all of the values on the right-hand side. Its position is swapped with the minimal value if it is not the minimal value.

3)Algorithm

Determine the value of n, which represents the entire size of the array.
Divide the list into pieces that are sorted and unsorted. The sorted portion begins with an empty list, but the unsorted portion begins with the whole list.
Choose the smallest number from the unpartitioned segment and put it in the sorted portion.
Repeat the method (n – 1) times until all of the list’s elements have been sorted.

4)Implementation

The number of items in the list is represented by the variable n.
Now, I ranges from 0 to n – 2, indicating that it refers from the first to the second-to-last item. The function of I is to constantly point to the location of the next smallest item, thus we will find the smallest item from I to the end of the list and place it at i.
For the time being, we regard the item at I to be the smallest, because if we cannot locate a smaller element after I then I holds the correct item.
Inside, j ranges from I + 1 to n – 1, indicating that j will point to all things after I and will be responsible for locating the smallest item in that range.
Now we compare the item at j to the smallest item we’ve discovered so far, and if the thing at j is smaller, it becomes the smallest item we’ve discovered so far.
Following the inner loop, the smallest item from I to n – 1 is located and swapped with the item at I to return it to its proper location.
The outer loop will choose and sort the next smallest items one by one until the entire list has been sorted.

Below is the implementation of Selection Sort:

Sorting the given list in Ascending Order:

# function which implements the selection_sort  algorithm for givenlist
def selectionSort(givenlist):
    length = len(givenlist)
    for i in range(length):
        # To begin, consider the first element in the unsorted section to be the smallest.
        minValue = i

        for j in range(i+1, length):
            if (givenlist[j] < givenlist[minValue]):
                # If a smaller element is identified, update the position
                # of the minimum element.
                minValue = j

        # Replace the smallest(minValue) element with the first element
        # of the unsorted portion.
        givenlist[i], givenlist[minValue] = givenlist[minValue], givenlist[i]


# given list
givenlist = ["hello", "this", "is", "BTechGeeeks", "python", "new", "online",
             "platform", "for", "all", "students", "who", "are", "excited", "about", "coding"]
# printing the list before sorting
print("printing the list before sorting :")
for i in givenlist:
    print(i, end=" ")
print()
# passing this given list to selectionSort function which sorts the given list
selectionSort(givenlist)
# printing the list after sorting
print("printing the list after sorting :")
for i in givenlist:
    print(i, end=" ")

Output:

printing the list before sorting :
hello this is BTechGeeeks python new online platform for all students who are excited about coding 
printing the list after sorting :
BTechGeeeks about all are coding excited for hello is new online platform python students this who

Explanation : Here we can see that the given list of strings is sorted in Ascending order

Below is the implementation of Selection Sort:

Sorting the given list in Descending Order:

# function which implements the selection_sort  algorithm for givenlist
def selectionSort(givenlist):
    length = len(givenlist)
    for i in range(length):
        # To begin, consider the first element in the unsorted section to be the largest.
        maxValue = i

        for j in range(i+1, length):
            if (givenlist[j] > givenlist[maxValue]):
                # If a larger element is identified, update the position
                # of the larger element.
                maxValue = j

        # Replace the largest(maxValue) element with the first element
        # of the unsorted portion.
        givenlist[i], givenlist[maxValue] = givenlist[maxValue], givenlist[i]


# given list
givenlist = ["hello", "this", "is", "BTechGeeeks", "python", "new", "online",
             "platform", "for", "all", "students", "who", "are", "excited", "about", "coding"]
# printing the list before sorting
print("printing the list before sorting :")
for i in givenlist:
    print(i, end=" ")
print()
# passing this given list to selectionSort function which sorts the given list
selectionSort(givenlist)
# printing the list after sorting
print("printing the list after sorting :")
for i in givenlist:
    print(i, end=" ")

Output:

printing the list before sorting :
hello this is BTechGeeeks python new online platform for all students who are excited about coding 
printing the list after sorting :
who this students python platform online new is hello for excited coding are all about BTechGeeeks

Explanation : Here we can see that the given list of strings is sorted in Descending order

5)Time Complexity

The sort complexity expresses the number of execution times required to sort the list. There are two loops in the implementation.

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

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

As a result, the number of executions is (n * n), which can also be written as O. (n^2).

The difficulty of the selection sort is divided into three categories:

Worst case scenario: the provided list is in descending order. The algorithm executes as many executions as possible, which is denoted as [Big-O] O(n^2)
Best case :When the provided list is already sorted, this is the best case scenario. The algorithm executes the fewest number of times possible, which is denoted as [Big-Omega]? (n^2)
Average case: When the list is in random order, this is the average situation. [Big-theta]?O(n^2) is the average level of complexity
Because it only uses one temporal variable to exchange values, the selection sort has an O(1) space complexity.

6)Conclusion

In this tutorial, we learned how Selection Sort works, how to implement it in Python.

Selection Sort, like Bubble and Insertion Sort, has an O complexity (n^2). This indicates that doubling the input size increases the time it takes to execute the method by four times, making it an inefficient sorting method.

It is less efficient than Insertion Sort in general, but it is considerably easier to understand and apply.
Related Programs: