Reading Time: 6 minutes

Sorting is one the most fundamental concepts that highly required when dealing with programming. Initially it just seems like arranging a few numbers in ascending or descending order, but as we dive deeper into understanding the concept of sorting, you will realise the importance of sorting and it’s wide range of applications. Selection Sort is one such sorting technique to arrange your data in a specific order.

For starters, as the name suggests sorting is basically segregating the given data in a specific manner according to the use case. To give context, think of the notifications in your device, they are displayed either based on the time or the application they belong to, and this arrangement makes your life easier right.

So similarly, it becomes crucial for organisations to retrieve their data from the database in an efficient manner, and arranging them in an order is important.

This is just a small example, but it is used almost everywhere in the real world scenarios, may it be finding optimal routes in logistics business, inventory management, task allocation etc. In the context of programming and computer science, search algorithms like binary search, relies on the data being in order to locate the element in an array or list, dynamic programming algorithms, such as greedy algorithms benefit from data prearranged in order.

Let’s delve into some of the most important sorting techniques in the world of programming, in this post we will be understanding the most basic sorting technique, which is Sorting is one the most fundamental concepts that highly required when dealing with programming. Initially it just seems like arranging a few numbers in ascending or descending order, but as we dive deeper into understanding the concept of sorting, you will realise the importance of sorting and it’s wide range of applications.

For starters, as the name suggests sorting is basically segregating the given data in a specific manner according to the use case. To give context, think of the notifications in your device, they are displayed either based on the time or the application they belong to, and this arrangement makes your life easier right?

So similarly, it becomes crucial for organisations to retrieve their data from the database in an efficient manner, and arranging them in an order is important.

This is just a small example, but it is used almost everywhere in the real world scenarios, may it be finding optimal routes in logistics business, inventory management, task allocation etc. In the context of programming and computer science, search algorithms like binary search, relies on the data being in order to locate the element in an array or list, dynamic programming algorithms, such as greedy algorithms benefit from data prearranged in order.

Let’s delve into some of the most important sorting techniques in the world of programming, in this post we will be understanding these concepts in sorting “Selection Sort”.

In this method, the following steps are followed:

1. we employ two loops to iterate over the given unsorted list, and assign a variable named minimum_value to the current index of the first loop, the pointer of the first loop is assigned from the 0th index of the list and the second loop’s pointer will point to the first loop’s pointer+1.
2. Then we check for the least number through the second loop and and assign the index of that number to the minimum_value.
3. Once the secondary loop finishes, an if condition checks whether the minimum_value is same as before, or if it has changed, if there is a change then the values are swapped.

Don’t worry if you couldn’t get the whole idea, you will definetly grasp the logic, once we dive into the code and step by step explanation.

List to sort: [23, 71, 12, 90, 8, 3]

The Program

def sel_sort(lst): # sorting in ascending order
    size = len(lst)
    for i in range(0, size - 1):
        least = i

        for j in range(i + 1, size):
            if lst[j] < lst[least]:
                least = j
        if least ! = i:  # checking if the least's value is same as before the secondary loop (remove the space between the ! and =, as the post's editor is making it !=, I have kept seperate to avoid confusions regaring syntax)
            lst[least], lst[i] = lst[i], lst[least]

    return lst

Just have a glance of the code and run it, you will get a complete picture as you read through visual representation. If you don’t have an python interpreter and python installed, click here to visit the programiz(an online interpreter) website and run the code. Feel free to add print statements of i,j and the list to view how the pictorial representation below is formed.

Iteration 1: (i is 0)

The least number in the iteration is 3 so 3 is swapped with 23.

Iteration 2: (i is 1)

8 is swapped, because it is the smallest number compared to others and the if condition in the second loop won’t get executed as 23 is not lesser than 8.

Iteration 3: (i is initially 2 and then it changes to 3 and 4. As no number less than 12 are found(no swapping is performed when i is 2))

The list is sorted!!!! Before we wrap up, lets talk about complexity.

Time and Space Complexity

The time and space complexity of selection sort is as follows:

Time Complexity:

• Selection sort has a nested loop structure. The outer loop iterates through the entire array, and for each iteration, the inner loop also traverses through the unsorted portion to find the minimum element.
  
• In the worst-case scenario, for each element in the array, the inner loop needs to traverse the remaining unsorted elements to find the minimum. This results in n+(n−1)+(n−2)+…+1 comparisons, which simplifies to n(n−1)/2, leading to a quadratic time complexity of O(n^2).
  
  Detailed explanation: n+(n−1)+(n−2)+…+2+1 is an arithmetic progression series, in which the difference here is -1, if we plug this information into the formula for sum of series of Arithmetic Progression(Sn=n/2(2a+(n-1)d)), we get the result as n(n−1)/2. But this still does not answer to how O(n2^2) came, so here’s the explanation: while calculating time complexity we drop the constant factors and lower-order terms, which results in O(n^2) time complexity.
  
  This indicates that as the input size n grows, the number of comparisons approaches a quadratic relationship with the input size, making the algorithm less efficient for larger datasets.
  
• The time complexity remains O(n^2) in the average and best cases as well because even if the array is partially sorted or completely sorted, the algorithm still performs the same number of comparison and iterations.l

Space Complexity:

• Selection sort has a space complexity of O(1).
  
• This is because it does not require additional space proportional to the input size for its operation. The sorting is done in-place by swapping elements within the array itself, hence it has a constant space complexity regardless of the input size.

Now that you have a good understanding of how the entire concept works, I highly recommend you to sort the same list ([23, 71, 12, 90, 8, 3]) in descending order, but don’t look at the code now, use the same logic of comparing numbers and swapping, and write a program. This will help you reinforce the concepts of selection sort which we have discussed in the post and foster confidence in this topic.

That’s a wrap, thank you for reading all along, your curiosity and engagement are highly valued, post your comments or doubts in the comment section below. Subscribe to sapiencespace and enable notifications to get regular insights.

Click here to view similar insights.