Selection Sort Algorithm

The selection sort algorithm efficiently arranges elements into two sections: sorted and unsorted sublists. This method simplifies list organization, enhancing sorting efficiency. In this article, we delve into the mechanics of selection sort, explaining its process and effectiveness in sorting various types of lists. Let’s explore what selection sort is and how it works.

Takeaways

• Complexity of Selection sort:
  • Time complexity – O(n²)
  • Space complexity – O(1)

What is Selection Sort?

Selection sort, also known as in-place comparison sort, is a simple sorting algorithm. It works on the idea of repeatedly finding the smallest element and placing it at its correct sorted position.

Selection sort works by dividing the list into two sublists:

1. Sorted sublist – that is built on the left end of the list from left to right.
2. Unsorted sublist – that is the rest of the unsorted list, on the right end.

Initially, the sorted sublist is empty, and we only have the unsorted sublist.

With each iteration of the selection sort, we –

1. Search for the smallest element in the unsorted sublist.
2. Place it at the end of the sorted sublist.

We repeat the above-given steps until we get a sorted list, and there are no more elements left in the unsorted sublist. After every iteration, the size of the sorted sublist increases, and that of the unsorted sublist decreases.

Note – We are searching for the smallest element because we want to sort the list in ascending order. We can also search for the biggest element if we want to sort the list in descending order.

Flowchart of the Selection Sort

A flowchart for the Selection Sort algorithm could be described as follows:

1. Start: Begin the process.
2. Input List: Obtain the list or array to be sorted.
3. Initialize: Set the current index as the starting index. This represents the beginning of the unsorted portion of the list.
4. Find Minimum: Traverse the rest of the unsorted portion to find the smallest element.
5. Swap: Swap the smallest element found with the element at the current index.
6. Increment Index: Increase the current index by one, moving the boundary of the sorted and unsorted portions of the list.
7. Check: Check if the current index is less than the length of the list – 1. If it is, go back to the “Find Minimum” step. If it’s not, all elements have been sorted.
8. End: End the process. The list is now sorted in ascending order.

How Does Selection Sort Work?

Recall the above example of arranging the students in a height-wise order. In that case, we can follow these steps to arrange the students in a height-wise order:

1. Divide the queue of students into two parts – arranged and unarranged.
2. To begin with, place all the students in the unarranged queue.
3. From this unarranged queue, search for the shortest student and place him/her in the list of arranged students.
4. Again, from the unarranged queue, select the second-shortest student. Place this student in the arranged queue, just after the smallest student.
5. Repeat the above-given steps until all the students are placed into the arranged queue. Did you see what we just did here? We used the selection sort algorithm to arrange all the students in a height-wise order.

Now, let us consider that we want to sort a list in ascending order. Here are the steps that the algorithm would follow:

1. Start with the first element. At this point, the entire list is unsorted. And the sorted sublist is empty.
2. Iterate over the list to search for the smallest element in it.
3. Add this element to the sorted sublist, and remove it from the unsorted sublist. In other words, swap the smallest element in the unsorted sublist with the element that is present at its correct sorted position.
4. Repeat the above steps until all the elements from the unsorted sublist are transferred to the sorted sublist.

To better understand selection sort, recall the list that contains the elements 5, 6, 4, 2 initially.

The steps to sort this list would involve –

From the above-given diagram, we can infer the following conclusions about the selection sort algorithm –

1. We had 4 elements with us, and we got the sorted list in 3 swaps. With this, we can conclude that to sort a list of size n, we need to perform n – 1 iterations.
2. In the first step or iteration, the smallest element (2 in this case) was selected and added to the sorted sublist. Similarly, after each iteration, the smallest among the unsorted elements was placed at its position. We selected one specific element in each iteration to sort it. This is the reason why this sorting algorithm is known as selection.
3. In selection sort, with each iteration over the unsorted sublist, only one element is sorted.
4. In the second step, we started our search from element 6 and not 2. This is because we know that 2 is already at its correct position, and starting from there would not make any difference. Same for the third step. In each step, we start our search from the unsorted sublist. This way, we can reduce the number of comparisons and hence the execution time of the program.

Selection Sort Algorithm

We know that to sort a list of n elements using selection sort, we need to perform n – 1 iterations.

The following is the algorithm of selection sort –

begin selectionSort(list)
  for i = 0 to sizeof(list) - 1    
      
       minIndex = i;
      
       for j = i + 1 to sizeof(list)
          
           if list[j] < list[mid_index]
               minIndex = j;
           end if
      
          swap(list[minIndex], list[i])
      
       end for
 
  end for
end selectionSort

Now let us understand the algorithm of selection sort with the following steps –

1. Run a loop from i = 0 till the size of the list. Under the loop –
   • Declare a variable called minIndex. minIndex helps in tracking the index of the next element that will be swapped with the element at the index i.
   • Run a nested for loop from j = i + 1 till the size of the list. We initialize j with i + 1 since it allows us to reduce the number of total comparisons made. Under this loop –
     • Check if the element at the index j is smaller than the element at the index mid_index. If it is, set minIndex equal to j. It helps us in searching for the smallest element in the unsorted sublist.
     • Swap the element at the index i with the element at index minIndex. It allows us to place the smallest element from the unsorted sublist at the end of the sorted sublist. Note that we are updating the value of minIndex each time we find an element smaller than it.

Now that we have understood what selection sort is, let us see how to implement a selection sort algorithm via codes.

Selection Sort Code

1. Selection Sort Code in Java

// Selection Sort in Java
class SelectionSort
{
    void selectionSort(int arr[])
    {       
        int size = arr.length;
 
        // loop to iterate over the entire array
        for (int i = 0; i < size - 1; i++)
        {
            // set minIndex equal to the first unsorted element
            int minIndex = i;
         
          //iterate over unsorted sublist
            for (int j = i+1; j < size; j++)
      //helps in finding the minimum element
                if (arr[j] < arr[minIndex])
                    minIndex = j;
 
            // swapping the minimum element with the element at minIndex to place it at its proper position
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

2. Selection Sort Code in Python

# Selection sort in Python
 
def selectionSort(arr):
 
   # loop to iterate over the array elements
   for i in range(len(arr)):
   
       # set min_index equal to the first unsorted element
       min_index = i
 
       # iterate over unsorted sublist
       for j in range(i+1, len(arr)):
 
    #helps in finding the minimum element
           if arr[min_index] > arr[j]:
               min_index = j
           
       # swapping the minimum element with the element at min_index to place it at its correct position
     
       arr[i], arr[min_index] = arr[min_index], arr[i]

3. Selection Sort Code in C

// Selection Sort in C++
//function to swap elements
void swap(int *xp, int *yp)
{
   int temp = *xp;
   *xp = *yp;
   *yp = temp;
}
void selectionSort(int arr[], int size)
{
   int i, j, minIndex;
   // loop to iterate over the entire array
   for (i = 0; i < size - 1; i++)
   {
       // set minIndex equal to the first unsorted element
       minIndex = i;
 
       //iterate over unsorted sublist
       for (j = i+1; j < size; j++)
 
      //helps in finding the minimum element
         if (arr[j] < arr[minIndex])
           minIndex = j;
       
// swapping the minimum element with the element at minIndex to place it at its correct position
       swap(&arr[minIndex], &arr[i]);
   }
}

4. Selection Sort Code in C++

// Selection Sort in C++
void selectionSort(int arr[], int size)
{
   int i, j, minIndex;
   // loop to iterate over the entire array
   for (i = 0; i < size - 1; i++)
   {
       // set minIndex equal to the first unsorted element
       minIndex = i;
 
       //iterate over unsorted sublist
       for (j = i+1; j < size; j++)
      
    // helps in finding the minimum element
         if (arr[j] < arr[minIndex])
           minIndex = j;
       
// swapping the minimum element with the element at minIndex to place it at its correct position 
// using std::swap() method for swapping
       swap(arr[minIndex], arr[i]);
   }
}

5. Selection Sort Code in JavaScript

// Selection sort in JavaScript
function swap(arr,xp, yp)
{
   var temp = arr[xp];
   arr[xp] = arr[yp];
   arr[yp] = temp;
}
function selectionSort(arr)
{
   var i, j, minIndex;
 
   // loop to iterate over the entire array
   for (i = 0; i < arr.length - 1; i++)
   {
       // set minIndex equal to the first unsorted element
       minIndex = i;
 
       // iterate over unsorted sublist
       for (j = i + 1; j < arr.length; j++)
         if (arr[j] < arr[minIndex])
              minIndex = j;
 
       // swapping the minimum element with the element at minIndex
       swap(arr, minIndex, i);
   }
}

6. Selection Sort Code in C#

// Selection sort in C#
class ScalerTopics
{
   //selection sort function
   static void SelectionSort(int[] arr)
   {
       int size = arr.Length;
       // loop to iterate over the entire array
       for (int i = 0; i < size - 1; i++)
       {
           // set minIndex equal to the first unsorted element
           int minIndex = i;
 
           //iterate over unsorted sublist
           for (int j = i + 1; j < size; j++)
               if (arr[j] < arr[minIndex])
                   minIndex = j;
           // swapping the minimum element with the element at minIndex
           int temp = arr[minIndex];
           arr[minIndex] = arr[i];
           arr[i] = temp;
       }
   }
}

Complexity Analysis of Selection Sort

1. Time complexity

To better understand the time complexity of Selection sort, let us break the selectionSort() function into the following parts:

• Loop to iterate over the entire list
• Part to swap the elements.
• Loop to iterate over the unsorted sublist.

Let the number of elements in the list be n. Now, we know that for part 1, the loop would run for n times.

Under part 1, the number of times the swapping occurs will be equal to n, and each swapping will take constant time. Therefore, for part 1, we can say that time complexity would be O(n).

Part 2 is nested inside the loop that is run in part 1. This loop helps in searching for the smallest number. Under this part, n comparisons are made that take constant time for execution. In other words, for each time part 1 is executed, part 2 will be executed n times. And if part 1 is executed for n number of times, part 2 would be executed for n * n number of times.

From this, we can say that the complexity of the selection sort algorithm is O(n ^ 2).

Now let us discuss the time complexity in the best, average, and worst case.

• Worst Case: O(n²). The worst case occurs when we want to sort a list in ascending order, but it is arranged in descending order.
• Average Case: O(n²). The average case is when the list is arranged in a jumbled order.
• Best Case: O(n). The best-case occurs when the list is already arranged in the desired order. Recall the part where we had concluded to sort a list of n elements. We need to perform n – 1 passes. And for each pass, we need to run a loop to iterate over the list. Now since the complexity of a for loop is O(n), and we are using two nested for loops, the time complexity of selection sort can be explained as –

(n – 1) * (( n – 2) + (n – 3) + (n – 4) +….1 ), which would be equal to n * (n – 1)/2 . And, in Big-Oh notation, this would be O(n²).

2. Space Complexity

The space complexity of the selection sort algorithm is O(1). This is because we have used a fixed number of variables, and we do not need any extra memory space apart from the loop variables and auxiliary variables that include temp, size, and minIndex. It means that we can sort an array containing a thousand elements even without using any extra variable.

Advantages of Selection Sort Algorithm

• Selection sort is efficient at checking if all elements are already sorted. This means it can quickly confirm a sorted list.
• It is an in-place sorting algorithm. This means it sorts the data directly in its original storage without needing extra space for temporary storage. This makes it a good choice when memory space is limited
• Selection sort is easy to understand and implement. Its simplicity makes it a good choice for small datasets.

Selection Sort Applications

• Small Lists: Selection sort is suitable for small lists or arrays where the inefficiency of quadratic time complexity is not a significant concern.
• Memory Usage: In environments with severe memory limitations, selection sort can be a good choice because it is an in-place sorting algorithm, which means it does not require additional storage.
• When Swapping is Costly: If the cost of swapping elements is high (for instance, when dealing with large records and small keys), selection sort can be efficient because it minimizes the number of swaps.
• Checking Sortedness: It can be used in scenarios where it’s beneficial to quickly determine if a list is already sorted, as selection sort is efficient at doing this.

Conclusion

• Selection sort can be good at checking if everything is already sorted.
• Good to use when memory space is limited.